Python常用排序算法

1.冒泡排序

思路:将左右元素两两相比较，将值小的放在列表的头部，值大的放到列表的尾部

效率:O(n²)

1 def bubble_sort(li):
2     for i in range(len(li)-1):
3         for j in range(len(li)-i-1):
4             if li[j] > li[j+1]:
5                 li[j],li[j+1] = li[j+1],li[j]

View Code

2.选择排序

思路:遍历列表，挑出一个最小的数字，放到列表的第一个索引位。在一趟遍历剩余列表中的最小数，继续放置。

效率:O(n²)

1 def select_sort(li):
2     for i in range(len(li)-1):
3         mim_loc = i
4         for j in range(i+1,len(li)):
5             if li[j] < li[mim_loc]:
6                 mim_loc = j
7         if mim_loc != i:
8             li[i],li[mim_loc] = li[mim_loc],li[i]

View Code

3.插入排序

思路：列表分为有序区和无序区两个部分，最初有序区只有一个元素。每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空

效率:O(n²)

1 def insert_sort(li):
2     for i in range(1,len(li)):
3         tmp = li[i]
4         j = i - 1
5         while j >= 0 and tmp < li[j]:
6             li[j+1] = li[j]
7             j= j-1
8         li[j+1] = tmp

View Code

4.快速排序

思路:取一个元素P,使元素P归位,列表被P分为两个部分,左边的比P小,右边比P大,递归完成排序。

效率:O(nlogn)

 1 def quick_sort(li,left,right):
 2     if left < right:
 3         mid = partition(li,left,right)
 4         quick_sort(li,left,mid-1)
 5         quick_sort(li,mid+1,right)
 6 
 7 def partition(li,left,right):
 8     tmp = li[left] #随机取出一个数
 9     while left < right:
10 　　　　 #如果遇到比tmp大的数,右指针向左移动,否则将右边的值放到左边
11         while left < right and li[right] >= tmp:
12             right -= 1
13         li[left] = li[right]
14 　　　　 #如果遇到比tmp小的数,左指针向右移动,否则将左边的值放到右边　
15         while left < right and li[left] <= tmp:
16             left += 1
17         li[right] = li[left]
18     li[left] = tmp #将原先的数回填
19     return left

View Code

5.堆排序

思路:建立堆,得到堆顶元素为最大元素,去掉堆顶元素,将堆的最后一个元素放到堆顶,此时通过一次调整使得堆有序.堆顶元素为第二大元素,重复步骤直到堆变空

效率:O(nlogn)

 1 def sift(data,low,high):
 2     i = low #根节点下标
 3     j = 2 * i +1 #左子节点的下标
 4     tmp = data[i]
 5     while j <= high:
 6         if j < high and data[j] < data[j+1]:
 7             j += 1
 8         if tmp < data[j]:
 9             data[i] = data[j]
10             i = j
11             j = 2 * i +1
12         else:
13             break
14     data[i] = tmp
15     
16 def heap_sort(data):
17     n = len(data)
18     for i in range(n//2-1,-1,-1):
19         sift(data,i,n-1)
20     for i in range(n-1,-1,-1):
21         data[0],data[i] = data[i],data[0]
22         sift(data,0,i-1)
23 
24 
25  6.归并排序
26 
27 思路:将列表越分越小,直到分成一个元素,此时一个元素是有序的.然后将两个有序的列表合并
28 
29 def merge(data,low,mid,high):
30     i = low #左指针
31     j = mid+1 #右指针
32     tmp = []#临时列表
33     #如果列表还有值
34     while i <= mid and j <= high:
35         #如果左边的值比右边的值小,则放入到tmp中
36         if data[i] <= data[j]:
37             tmp.append(data[i])
38             i+=1
39         else:#否则将右边的值放入到tmp中
40             tmp.append(data[j])
41             j-=1
42     #如果左边还有剩下的值,则一起放入到tmp中的左边
43     while i <= mid:
44         tmp.append(data[i])
45         i+=1
46     #如果右边还有剩下的值,则一起放入到tmp中的右边
47     while j <= high:
48         tmp.append(data[j])
49         j+=1
50     data[low:high+1] = tmp
51 
52 def merge_sort(data,low,high):
53     if low< high:
54         mid = (low+high)//2
55         merge_sort(data,low,mid)
56         merge_sort(data,mid+1,high)
57         merge(data,low,mid,high)

View Code

6.归并排序

思路：使用递归的方式，将列表越分越小，直至一个元素，然后将列表组合成一个有序的列表

 1     def merge(self,data,low,mid,high):
 2         i = low
 3         j = mid +1
 4         ltmp = []
 5         while i <= mid and j <= high:
 6             if data[i] <= data[j]:
 7                 ltmp.append(data[i])
 8                 i+=1
 9             else:
10                 ltmp.append(data[j])
11                 j+=1
12 
13             while i <= mid:#如果左边还有数据继续将左边的数据放入临时列表中
14                 ltmp.append(data[i])
15                 i+=1
16 
17             while j <= high:#如果右边还有数据继续将右边的数据放入临时列表中
18                 ltmp.append(data[j])
19                 j+=1
20         data[low:high+1] =ltmp #将新列表的值替换原列表的值
21 
22     def merge_sort(self,data,low,high):
23         if low< high:
24             mid = (low+high)//2
25             self.merge_sort(data,0,mid)
26             self.merge_sort(data,mid+1,high)
27             self.merge(data,low,mid,high)

View Code

7.希尔排序

思路:首先取一个整数d1=n/2,将列表中的元素分成d1个组,每组相邻两元素的之间的距离为d1,在各组内直接进行插入排序.取第二个整数d2=d1/2,重复上述的分组过程,直到di=1,

然后在同一组内进行插入排序

效率:O(1.3n)

 1 def shell_sort(data):
 2 　　#获取步长
 3     gap = len(data)//2
 4     while gap > 0:
 5         #根据步长gap进行插入排序
 6         for i in range(gap,len(data)):
 7             tmp = data[i]
 8             j = i - gap
 9             while j >= 0 and tmp < data[j]:
10                 data[j+gap] = data[j]
11                 j-=gap
12             data[j+gap] = tmp
13         gap/=2

View Code

排序总结

练习:

1.给定一个升序列表和一个整数,返回该整数在列表中的下标范围.例如:列表[1,2,3,3,3,4,4,5],若查找3,则返回(2,4),查找1,返回(0,0)

思路:利用二分查找,如果查到3,在看看3的左边和右边是否有相等的元素,有则返回下标

 1 def binary_list_search(data,val):
 2     low = 0
 3     high = len(data)-1
 4     while low <= high:
 5         mid = (low+high)//2
 6         #如果找到val的值
 7         if data[mid] == val:
 8             #创建两个指针
 9             left=mid
10             right=mid
11             #如果左边指针的值等于val,则指针向左移
12             while left >= 0 and data[left] == val:
13                 left -= 1
14             #右边指针的值等于val,则指针向右移    
15             while right <= high and data[right] == val:
16                 right += 1
17             #如果都找到则返回val在列表中的下标范围    
18             return (left,right)
19         elif data[mid] < val:
20             low = mid + 1
21         else:
22             high = mid-1

View Code

2.给定一个列表和一个整数,设计算法找到两个数的下标,使得两个数之和为给定的整数,保证仅有一个结果.例如列表[1,2,5,4]与目标整数3,结果为(0,1)

思路: 1.使用两重循环进行查找匹配,时间复杂度O(n²)

　　 2.使用二分查找进行匹配,时间复杂度O(nlogn)

3.使用列表下标倒序进行匹配,时间复杂度O(n)

1 1.双重for循环
2 def sum_list1(data,val):
3     for i in range(len(data)):
4         for j in range(i+1,len(data)):
5             if data[i] + data[j] == val:
6                 return (i,j)

View Code

 1 2.利用二分法查找进行返回
 2 import copy
 3 def bin_search(data,val,low,high):
 4     while low<=high:
 5         mid = (low + high) // 2
 6         if data[mid] == val:
 7             return mid
 8         elif data[mid] < val:
 9             low = mid+1
10         else:
11             high = mid-1
12 
13 def sum_list2(data,val):
14     data2 = copy.deepcopy(data)
15     data2.sort()
16     for i in range(len(data2)):
17         a = i
18         b = bin_search(data2,val-data[a],i+1,len(data2)-1)
19         if b:
20             return (data.index(data2[a]),data.index(data2[b]))

View Code

1 3.反向下标,必须提供查找的范围
2 def sum_list3(data,val,max_val):
3     a = [None for i in range(max_val)]
4     for i in range(len(data)):
5         a[data[i]] = i
6         if a[val-data[i]]:
7             return (a[data[i]],a[val-data[i]])

View Code

3.现在有一个列表,列表中数的范为在0-100之间,列表的长度大概为100万,设计算法在O(n)的复杂度内将列表进行排序

思路:创建一个新列表,用来存放每个数字出现的次数,元素出现几次就遍历输出几次,完成O(n)的复杂度

 1 def count_sort(li,max_val):
 2     #统计每个数出现的次数
 3     count = [0 for i in range(max_val+1)]
 4     for num in li:
 5         count[num] += 1
 6     i = 0
 7     #找出下标,值,通过遍历把每一个次数对应的值重新赋值给li
 8     #因为count和n的值不同,所以虽然是两重for,count表示每个数出现的次数,n表示列表但复杂度依然是O(n)
 9     for num,n in enumerate(count):
10         for j in range(n):
11             li[i] = num
12             i += 1
13     return li

View Code

4.现在有n个数(n>10000),设计算法,按照大小顺序得到前10大的数

思路:创建长度为10的临时列表来存放目标数据,然后通过插入排序来调整列表中数的顺序

 1 def insert(li,i):
 2     tmp = li[i]
 3     j = i-1
 4     while j>=0 and li[j]>tmp:
 5         li[j+1]=li[j]
 6         j-=1
 7     li[j+1]=tmp
 8 
 9 def insert_sort(li):
10     for i in range(1,len(li)):
11         insert(li,i)
12 
13 def topk(li,k):
14     top=li[0:k+1]
15     insert_sort(li)
16     for i in range(k+1,len(li)):
17         top[k] = li[i]
18         insert(top,k)
19     return top[:-1]

View Code