排序算法经过很长时间的演化,产生了很多不同的方法。虽然每一种的算法在时间和空间复杂度上各有不同,但是各种算法也都有不同的应用场景,并不是效率最高的算法就适应所有的使用场景。
下面我们来归纳一下我们常见的一些排序算法,已经这些算法的时间复杂度和空间复杂度,以及这些排序算法的稳定性。
按照大的分类,排序可以分为内排序和外排序。内排序是值在排序过程中,全部记录都是存放在内存中的。而外排序则是在排序过程中需要使用到外部存储。
我们下面总结的是内排序算法:
插入排序
选择排序
冒泡排序
快速排序
归并排序
希尔排序
基数排序
堆排序
插入排序
排序思想
插入排序是思想很简单,就是最初先把一个序列的第一个元素看成一个有序序列,然后把后面的序列看作无序序列。将后面无序序列中的元素逐个放到前面的有序序列中的合适位置。
排序过程示例
现有一个待排序的序列:
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|
5 | 4 | 8 | 3 | 7 | 3 | 6 |
首先,我们把[5,] 看作一个单独的有序序列,后面的[4,8,3,7,3,6]看作一个无序序列。
有序序列 = [5,],
无序序列 = [4, 8, 3, 7, 3, 6]
然后选择将后面无序序列,现在我们把无序序列中的第一个元素放到有序序列的合适位置,然后
有序序列 = [4, 5,],
无序序列 = [8, 3, 7, 3, 6]
经过一次排序后,序列变为:
4 | 5 | 8 | 3 | 7 | 3 | 6 |
---|
然后再把前面继续前面类似的操作,将后面无序序列中的元素逐一加到有序序列中。最终完成排序过程。
python实现
# 插入排序算法 def insert_sort(array): for i in range(1, len(array)): j = i - 1 # array[0:j]是有序序列, array[i:]是无序序列 temp = array[i] # temp暂存待存入有序序列的数字 while j >= 0 and array[j] > temp: # 寻找有序序列中的合适位置 array[j+1] = array[j] # 如果当前数字大于待存入的temp,则把该数字后移一位 j -= 1 array[j+1] = temp # 将待排序的数字存到有序序列中的合适位置 return array
算法复杂度
时间复杂度:
最好的情况下,如果序列本来就是有序的,则不会进入到内部循环中,只有一层循环,时间复杂度是O(n);最坏情况下,序列是反序的,则要完全运行两层循环,时间复杂度为O(n2)。平均时间复杂度为O(n2)。
空间复杂度:O(1)
算法稳定性
在排序过程中,是从无序序列的开始到结尾,一个一个与前面的有序序列中的元素做比较,因此该排序是稳定的。
选择排序
排序思想
从待排序的序列中找出最小的元素与第一个元素交换,然后再在剩下的序列中找出最小的元素与第二个元素交换,以此类推。。。直到最后一个元素
排序过程示例
现有一个待排序的序列
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|
首先,从头到尾找到最小的元素3;
然后,将3与第1个元素交换。
经过1次排序后,序列变为:
3 | 4 | 8 | 5 | 7 | 3 | 6 |
---|
然后,在剩下的序列中找出最小的,也是3,与第2个元素交换,
经过2次排序后,序列变为:
3 | 3 | 8 | 5 | 7 | 4 | 6 |
---|
然后,在剩下的序列中找出最小的,是4,与第3个元素交换。
经过2次排序后,序列变为:
3 | 3 | 4 | 5 | 7 | 8 | 6 |
---|
。。。。。。
python实现
# 选择排序算法 def select_sort(array): array_len = len(array) for i in range(array_len): k = i for j in range(i, array_len): # 从头到尾找出最小的 if array[k] > array[j]: k = j array[i], array[k] = array[k], array[i] # 交换位置 return array
算法复杂度
时间复杂度:
排序的两层循环都需要走一遍,因此该算法安的最好的情况,最坏情况下和平均情况下的时间复杂度均为O(n2)。
空间复杂度:O(1)
算法稳定性
不稳定,比如序列[3,4,3,1,],第1次排序时候,首尾两个数字交换,序列中两个3的相对位置就发生变化了。
冒泡排序
排序思想
排序思想是从第1个元素到第n个元素遍历,如果前一个元素大于后一个元素,则调换两者位置。这样经过一次排序后,最大的元素就排到了最后面。然后再从第1个元素到第n-的元素进行下一轮的冒泡排序
排序过程示例
现有一个待排序的序列
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|
首先,冒泡一次,第1个元素和第2个元素交换位置:
4 | 5 | 8 | 3 | 7 | 3 | 6 |
---|
然后,一直相互对比,直到最后,
经过一轮冒泡之后,序列变为:
4 | 5 | 3 | 7 | 3 | 6 | 8 |
---|
然后再继续第2轮的冒泡。
python实现
# 冒泡排序 def bubble_sort(array): array_len = len(array) for i in range(array_len): for j in range(array_len-i-1): if array[j] > array[j+1]: array[j], array[j+1] = array[j+1], array[j] return array
算法复杂度
时间复杂度:
冒泡排序与选择排序类似,无论序列情况,都需要完全走完两层for循环,最好,最坏和平均的时间复杂度都为O(n2)。
空间复杂度:O(1)
算法稳定性
冒泡排序时,相同的元素不会出现位置的调换,排序是稳定的。
快速排序
排序思想
先选取一个基准元素base,一般我们选择第1个元素,然后分别找两个指针left和right分别指向序列的第一个和最后一个元素,然后right往前面去找,找到一个小于基准元素的的元素,将该元素赋值给left所在位置;然后再从left位置继续往后找,找到一个大于基准元素的元素,然后将该元素赋值给right所在位置,然后再right往前。。。。。就这样left以此交替,直到left和right两者相遇。相遇后,则将原来标记的基准元素base赋值到该位置。
这样就将序列以base为界分为了前后两个部分,前一部分是小于基准元素的,后一部分是大于基准元素的。然后我们再分别对base前后的两个子序列按照以上相同的方式递归。最后整个序列就完成了排序了。
排序过程示例
现有一个待排序的序列
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|
首先,我们选取第1个元素为基准元素,赋值给变量base。然后分别定义两个指针left, right指向第一个元素和最后一个元素:
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|---|---|---|---|---|---|
base left | - | - | - | - | - | right |
然后,先从right指针开始,判断指向的元素是否小于基准元素base,如果满足条件,则一个一个元素地持续向左移动,直到找到元素满足条件。如下:
base = 5
5 | 4 | 8 | 3 | 7 | 3 | 6 |
---|---|---|---|---|---|---|
base left | - | - | - | - | right | - |
然后把right指向的元素赋值给base指向的元素。
base = 5
3 | 4 | 8 | 3 | 7 | 3 | 6 |
---|---|---|---|---|---|---|
base left | - | - | - | - | right | - |
然后再从左向右移动left指针,直到找到一个大于base的元素:
base = 5
3 | 4 | 8 | 3 | 7 | 3 | 6 |
---|---|---|---|---|---|---|
base | - | left | - | - | right | - |
然后将left指向的元素赋值给right指向的元素:
base = 5
3 | 4 | 8 | 3 | 7 | 8 | 6 |
---|---|---|---|---|---|---|
base | - | left | right | - | - | - |
接下来,再去移动right指针,寻找小于base的元素,如果有,则赋值给此时left指向的元素:
base = 5
3 | 4 | 3 | 3 | 7 | 8 | 6 |
---|---|---|---|---|---|---|
base | - | left | right | - | - | - |
然后再移动left指针,寻找大于base的元素,如果有,赋值给right指向的元素。此时,对于我们的例子,left和right指针已相遇,则停止移动:
base = 5
3 | 4 | 3 | 3 | 7 | 8 | 6 |
---|---|---|---|---|---|---|
base | - | - | right left | - | - | - |
相遇后,则将base赋值给此时相遇的位置的元素:
base = 5
3 | 4 | 3 | 5 | 7 | 8 | 6 |
---|---|---|---|---|---|---|
base | - | - | right left | - | - | - |
于是,序列被base给分割成了两个部分,左边的全部小于5, 右边的全部大于5,然后,我们再继续对左半和右半边的元素按照相同的方式递归,直到最终完成所有元素的排序。
python实现
# 快速排序1 def partition(array, left, right): base = array[left] while left < right: while left < right and array[right] >= base: # 从右边找到第一个小于base的元素 right -= 1 array[left] = array[right] # 找到后,赋值给left所指位置 while left < right and array[left] <= base: # 从左边找到第一个大于base的元素 left += 1 array[right] = array[left] # 找到后,赋值给right所指的位置 array[left] = base # left和right相遇时,将base赋值到它们相遇的位置 return left # 返回中间分界点,此时左边的都小于base, 右边的都大于base def quick_sort(array, left, right): if left < right: mid = partition(array, left, right) quick_sort(array, left, mid-1) quick_sort(array, mid+1, right) return array
改进一下,可以将以上两个函数合并为一个,原理是一样的:
# 快速排序2 def quick_sort_2(array, left, right): if left >= right: return base = array[left] l, r = left, right while l < r: while l < r and array[r] >= base: r -= 1 while l < r and array[l] <= base: l += 1 if l < r: array[l], array[r] = array[r], array[l] array[left], array[l] = array[l], array[left] quick_sort_2(array, left, l-1) quick_sort_2(array, l+1, right)
另外,在网上看到一个很简短的快排的python实现:
def qsort(lst): if not lst: return [] return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])
算法复杂度
时间复杂度:
最好的情况下,每次都能将序列平均分为两份,这种情况下的时间复杂度就是O(N*log2N);最坏情况下,每次划分都是一半是1个元素,另一半是n-1个元素,这种极端情况下的时间复杂度为O(n2)。平均时间复杂度为O(n2)。
空间复杂度:
每次都分出一半进行单独的排序,比较占用内存,最好情况下,空间复杂度为O(log2N),最差情况下,空间复杂度为O(n)
算法稳定性
不稳定,比如[3,4,1,1]排序,可能会使原来两个1元素的相对位置发生变化。
归并排序
排序思想
归并排序的思想是将一个序列根据二分法分为两个序列,然后再将这两个序列一直二分下去,直到最后是单个元素,然后再对分出来的两个序列做合并,合并成一个局部有序的子序列,然后再继续向上合并,直到最终所有子序列合并,变成一个完全有序的序列。
排序过程示例
现有一个待排序的序列
5 | 8 | 4 | 3 | 7 | 3 | 6 |
---|
首先,该序列有7个元素,可以分为
5 | 8 | 4 |
---|
和
3 | 7 | 3 | 6 |
---|
两个列表,再将前一个继续二分下去得到
5 |
---|
和
8 | 4 |
---|
然后,
8 | 4 |
---|
继续二分得到
8 |
---|
和
4 |
---|
现在已经二分到了最小的单元,然后再进行归并排序
8 |
---|
和
4 |
---|
归并排序得到
4 | 8 |
---|
得到的序列再和之前分出来的
5 |
---|
进行归并排序得到
4 | 5 | 8 |
---|
同样的,前面分出的另一半也通过上述归并排序得到
3 | 3 | 6 | 7 |
---|
现在这两个子序列也都是局部有序的,再进行一个归并即可得到:
3 | 3 | 4 | 5 | 6 | 7 | 8 |
---|
python实现
# 归并排序 def merge(left, right): i, j = 0, 0 merged_array = [] while i < len(left) and j < len(right): # 将两个序列中元素从前面开始依次比较,从小到大归并进新序列 if left[i] <= right[j]: merged_array.append(left[i]) i += 1 else: merged_array.append(right[j]) j += 1 merged_array.extend(left[i:]) # 将序列中剩余的元素也归并进去 merged_array.extend(right[j:]) # 将序列中剩余的元素也归并进去 return merged_array def merge_sort(array): array_len = len(array) if array_len == 1: return array mid = array_len//2 # 将序列二分为两个部分 left = array[:mid] right = array[mid:] return merge(merge_sort(left), merge_sort(right)) # 递归调用
算法复杂度
时间复杂度:
始终需要对序列进行二分,然后合并,因此时时间复杂度在最好,最坏和平均情况下都为O(N*log2N)。平均时间复杂度为O(n2)。
空间复杂度:O(n), 序列越长,二分需要占用的内存越大。
算法稳定性
归并排序的算法是稳定的。
希尔排序
排序思想
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据,所以小数据只需进行少数比较和交换即可到正确位置。
排序过程示例
例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的插入排序了)。
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为普通插入排序,这就保证了数据一定会被排序。
python实现
def shell_sort(array): array_len = len(array) step = array_len//2 while step >= 1: # 步长一直减半到1 for i in range(step, array_len): # 从第二行序列开始,以步长step为间隔进行插入排序 j = i - step temp = array[i] while j >= 0 and array[j] > temp: array[j+step] = array[j] j = j - step array[j+step] = temp step = step//2 # 步长减半 return array
算法复杂度
时间复杂度:
它的最好及最差时间复杂度和简单插入排序一样,分别是是O(n)和O(n2),平均时间复杂度试增量选取规则而定,一般认为介于O(n)和O(n2)之间
空间复杂度:O(1),不需要额外空间
算法稳定性
与直接插入排序不同,希尔排序是不稳定的。
基数排序
排序思想
基数排序是一种典型的空间换时间的排序方法。现在所有排序数字中找到最大的数字,确定它的位数,然后将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。接下来,依次从最低位到最高位,将该位的数字按照从小到大分配该数位的位置,然后再将这些数字依次收集回到待排序序列中,然后再对下一个位数进行如上操作,直到最高位。
排序过程示例
现有一个待排序的序列
17 | 254 | 34 | 3 | 22 | 5213 | 6 | 1000 |
---|
首先,确定最大数字位5213,位数为4
然后,先从个位数开始,将这些数字存入到0-10的容器中:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1000 | 22 | 0003 5213 | 254 034 | 6 | 17 |
然后将这些数字再依次收集回来,得到的序列为:
1000 | 22 | 3 | 5213 | 254 | 34 | 6 | 17 |
---|
经过这一轮的分配和收集之后,序列元素就按照最低位的数字从小到大排列了。
然后再根据第2位(十位)进行分配:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1000 0003 0006 | 5213 0017 | 22 | 34 | 254 |
然后再将这些元素收集:
1000 | 3 | 6 | 5213 | 17 | 22 | 34 | 254 |
---|
重复上述步骤,直到最高位。即可完成序列的排序。
python实现
# 基数排序 def radix_sort(array): # 找到序列中最大的数 max_num = max(array) # 最大数的位数 bit_num = 0 while max_num > 0: bit_num += 1 max_num = max_num//10 # 最外层循环,每次循环按照位数分配并取回一次 for i in range(bit_num): # 建一个列表(列表元素也是一个列表),存储分配过来的数字 container = [[] for x in range(20)] # 将所有数字分配到列表中 for item in array: # 获取元素相应位数的数字 x = item % (10**(i+1))// (10**(i)) container[x].append(item) array = [] # 从0到10,依次将container列表中的元素取出来 for j in range(10): array.extend(container[j]) return array
算法复杂度
时间复杂度:
基数排序的最好,最好、最坏和平均时间复杂度都是O(n*r),其中n是数据大小,r是所选基数。
空间复杂度:
O(n+r)的额外空间。它是稳定的。
算法稳定性
基数排序的算法是稳定的。
堆排序
排序思想
堆排序利用的是二叉树的思想,所谓堆就是一个完全二叉树,完全二叉树的意思就是,除了叶子节点,其它所有节点都有两个子节点,这样子的话,完全二叉树就可以用一个一块连续的内存空间(数组)来存储,而不需要指针操作了。堆排序分两个流程,首先是构建大顶堆,然后是从大顶堆中获取按逆序提取元素。
首先是大顶堆,大顶堆即一个完全二叉树,的每一个节点都大于它的所有子节点。大顶堆可以按照从上到下从左到右的顺序,用数组来存储,第i个节点的父节点序号为(i-1)/2,左子节点序号为2i+1,右子节点序号为2(i+1)。构建大顶堆的过程即从后向前遍历所有非叶子节点,若它小于左右子节点,则与左右子节点中最大的交换,然后递归地对原最大节点做同样的操作。
排序过程示例
现有一个待排序的序列
5 | 4 | 8 | 3 | 7 | 3 | 9 | 6 | 1 |
---|
首先,列表以完全二叉树的形式如下图:
然后,从最后一个根节点开始,将它的左右子节点和根节点的值作比较,将最大的值放到根节点,如下:
接下来,按照上述调整方法,从后往前依次调整各个根节点,直到调整到最后:
这样,经过一轮后,最大的就被排到了最前面。
9 | 7 | 8 | 6 | 4 | 3 | 5 | 3 | 1 |
---|
然后将该元素交换到序列末尾,序列就变成了:
1 | 7 | 8 | 6 | 4 | 3 | 5 | 3 | 9 |
---|
最大的元素被排到了最后。
调换顺序之后,第一个元素的最大堆特征被破坏,然后对其进行调整。
重复以上步骤,直至元素全部调整为有序。
python实现
# 堆排序 def heap_sort(array): def heap_adjust(array, x, length): ''' 调整序列中的某个节点,array为待调整序列,x为待调整节点,length为序列长度 ''' left_chl, right_chl = 2*x + 1, 2*x + 2 # 节点x的左右子节点 max = x if left_chl < length and array[left_chl] > array[max]: max = left_chl if right_chl < length and array[right_chl] > array[max]: max = right_chl if max != x: array[x], array[max] = array[max], array[x] # 将较大的节点和父节点交换 # 交换后可能造成该节点下的子节点序列错乱,再次调整一下 heap_adjust(array, max, length) def build_heap(array): ''' 构建一个最大堆 ''' # 找出序列array指定长度length的切片的子序列中的最后一个根节点 # last_root_num = (length-1)//2 # For循环,从最后一个根节点以此往前调整,直到根节点 array_len = len(array) for i in range((array_len-1)//2, -1, -1): heap_adjust(array, i, array_len) array_len = len(array) # 构建最大堆 build_heap(array) for i in range(array_len-1, 0, -1): # 将构建好的最大堆中的第一个元素(最大)交换到最后一个位置。 array[i], array[0] = array[0], array[i] # 交换之后,调整剩下的序列为一个最大堆 heap_adjust(array, 0, i+1) return array
算法复杂度
时间复杂度:
在最好,最坏和平均情况下的时间复杂度都为O(N*log2N)
空间复杂度:O(1)
算法稳定性
不稳定
各个排序算法比较
下面对这几种排序算法的特点进行总结和比较:
排序算法 | 时间复杂度(最好) | 时间复杂度(最坏) | 时间复杂度(平均) | 空间复杂度 | 稳定性 | 复杂性 |
---|---|---|---|---|---|---|
插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 | 简单 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | 简单 |
冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 | 简单 |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(1) | 不稳定 | 复杂 |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 复杂 |
希尔排序 | O(n) | O(n2) | O(n)~O(n2)(与步长有关) | O(1) | 不稳定 | 简单 |
基数排序 | O(n+r) | O(n+r) | O(n+r) | O(n) | 稳定 | 复杂 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 复杂 |
下面,在序列长度不同的情况下,分别验证了各种排序算法耗时情况。
测试代码如下:
import datetime def test_sort_time(func, num=1000): import random test_list = [x for x in random.sample([x for x in range(num)], num)] start_time = datetime.datetime.now() func(test_list) end_time = datetime.datetime.now() print("%s 排序耗时: %s" %(func.__name__, (end_time - start_time))) num = 10000 test_sort_time(insert_sort, num) test_sort_time(select_sort, num) test_sort_time(bubble_sort, num) # test_sort_time(quick_sort, num) # 快排的传参与其它的几个不同,我们测试快排时,需要稍微修改一下上述测试代码。 test_sort_time(merge_sort, num) test_sort_time(shell_sort, num) test_sort_time(radix_sort, num) test_sort_time(heap_sort, num)
最终测试,得到如下数据:
序列长度 | 插入排序 | 选择排序 | 冒泡排序 | 快速排序 | 归并排序 | 希尔排序 | 基数排序 | 堆排序 |
---|---|---|---|---|---|---|---|---|
1000 | 0.039222 | 0.057428 | 0.083083 | 0.002998 | 0.0 | 0.015638 | 0.0 | 0.004994 |
10000 | 4.845310 | 4.377964 | 9.359449 | 0.039283 | 0.063264 | 0.056017 | 0.028226 | 0.078919 |
100000 | 7:49.454265 | 7:36.097941 | 16:11.984410 | 0.363053 | 0.727779 | 0.902417 | 0.346637 | 1.036951 |
1000000 | -- | -- | -- | 4.852743 | 9.156494 | 14.213323 | 4.633675 | 13.360319 |
从测试数据对比来看,基数排序在最终的排序耗时上表现是最好的。
既然基数排序效果这么好,为什么没有其它的排序算法(比如快排)应用更广泛呢?我觉得应该是基数排序的使用范围有限,并不是所有的排序都能使用基数排序。能用于基数排序需要序列中的元素都是有基数的(整数和浮点数)。
转载请注明:禅思 » 常见排序算法的Python实现,及其复杂度和稳定性分析?