常用排序算法的Python实现

Posted on | In |

学习Python的过程中，用Python实现了一下常用的排序算法。其实按照目前的工作感受老说，也不能说常用吧，只能说常见，很多都是大学算法考完之后的久别重逢。

冒泡排序

时间复杂度O(n²) 稳定

1
2
3
4
5
6
7
def bubble_sort(L):
	for x in range(len(L)-1): ##每次最大元素沉到最下面，len(L)-1 次
		for y in range(len(L)-1-x): ##相邻元素比较。次数减去已完成下沉的x个元素
			if L[y]>L[y+1]:
				L[y],L[y+1]=L[y+1],L[y]
		#print(x,":",L)
	return L

选择排序

时间复杂度O(n²) 不稳定

1
2
3
4
5
6
7
8
9
10
def selection_sort(L):
	for x in range(len(L)):
		min_index = x #记录最小元素的索引
		for y in range(x+1,len(L)):#选择出未排序元素里面最小的
			if L[y]<L[min_index]:
				min_index = y
		if min_index != x:
			L[x],L[min_index] = L[min_index],L[x]
		print(x,":",L)
	return L

直接插入排序

时间复杂度O(n²) 稳定

原理：类似于摸牌，左手上是有序的，右手摸一张牌，寻找插入点插入

1
2
3
4
5
6
7
8
9
def insertion_sort(L):
	for x in range(1,len(L)):
		temp = L[x] # 未排序的第一个元素
		y=x-1 # 从已排序的最后一个元素开始查找插入点
		while y>=0 and L[y]>temp: # 循环条件是索引不小于0且元素大于待插入的值
			L[y+1] = L[y] # 元素后移
			y-=1
		L[y+1] = temp # y已经是小于等于待插入值了，y+1处为插入位置
	return L

二分插入排序

时间复杂度O(n²)

元素移动次数与直接插入排序相同。n较大时，比较次数比直接插入排序的最差情况好很多，比直接插入最好情况要差，所以接近升序时，直接插入排序比较好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def insertion_dichotomy_sort(L):
	for x in range(1,len(L)):
		temp = L[x]
		left = 0
		right = x-1
		while (left<right): #通过二分法查找插入的位置
			middle = (left+right)//2
			if L[middle]>temp:
				right = middle-1
			else:
				left = middle+1
		y = x-1
		while y>=left:
			L[y+1] = L[y]
			y-=1
		L[left] = temp
	return L

希尔排序

希尔排序(递减增量排序,直接插入排序的高效版本) 时间复杂度O(nlogn)~O(n²) 不稳定

插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序通过设置一定的增量，这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
def shell_sort(L):
	h = len(L)//2 #设置希尔排序初始增量
	while h>=1:
		for x in range(h,len(L)):
			temp = L[x]
			y=x-h
			while y>=0 and L[y]>temp:
				L[y+h] = L[y]
				y-=h
			L[y+h] = temp
		h = h//2 #递减增量
		#print(L)
	return L

归并排序

时间复杂度O(nlogn) 辅助空间O(n) 稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = len(lists)//2
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)
def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += right[r:]
    result += left[l:]
    #print(left,right,"==>",result)
    return result

原来使用的是另一种不够Pythonic的方式，从C语言的实现中翻译来的写法，遇到了一些问题，知乎网友已协助解答。

快速排序

时间复杂度O(nlogn) 辅助空间O(logn)~O(n) 不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quickSort(L, low, high):
    i = low 
    j = high
    if i >= j:
        return L
    key = L[i] #基准
    while i < j:#把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面
        while i < j and L[j] >= key:
            j = j-1                                                             
        L[i] = L[j]
        while i < j and L[i] <= key:    
            i = i+1 
        L[j] = L[i]
    L[i] = key 
    quickSort(L, low, i-1)
    quickSort(L, j+1, high)
    print(low,high,L)
    return L

堆排序

时间复杂度O(nlogn) 不稳定

测试：

1
2
L=[2,5,2,6,8,1,12,3,5,0]
print(quickSort(L,0,len(L)-1))