很久以前整理的,先放着这里
排序算法在面试或者刷题的时候经常遇到,这些算法就是数据结构的基础,这里整理了一些经典的排序算法,包括冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序等。使用Python来实现。
一、冒泡排序
原理:
重复地走访要排序的数列,一次比较两个元素。如果它们顺序错误就将它们交换。
步骤:
1、比较相邻的元素。如果第一个比第二个大,就交换它们(升序)。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3、针对所有元素重复以上步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
(概念来自维基百科)
复杂度:
时间复杂度:
最好情况: 排序表本身是顺序的,根据优化后的代码,则只需要进行n-1次比较,故时间复杂度为O(n);
最差情况: 排序表本身是逆序的,则比较次数为 1+2+...+(n-1) = n*(n-1)/2 , 并作等数量级的移动操作;
平均情况: 时间复杂度为 O(n^2)
空间复杂度:
最好情况=最坏情况=平均情况=O(n), 辅助空间为O(1)。
代码:
def bubble_sort(array):
length = len(array)
for i in range(length):
for j in range(1, length-i):
# 第一个数大于第二个,则交换它们,目的是把最大数那个不断移到array末端
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
if __name__ == '__main__':
array = [23, 45, 67, 2, 4, 24]
result = bubble_sort(array)
该算法还可以继续优化。
优化1:
1、某一趟遍历如果没有数据交换,说明已经排好序了,不用继续排序了。因此使用一个标志位来判断是否继续遍历。
例子:
- 例如[2,1,3,4,5,6,7]这个数组,在第一次交换1和2之后,已经是排好序了,但是冒泡排序还是继续比较下去,浪费了时间。
优化代码:
def bubble_sort(array):
length = len(array)
for i in range(length):
flag = True # 标志位,用来判断如果没有交换就退出循环
for j in range(1, length-i):
# 第一个数大于第二个,则交换它们,目的是把最大数那个不断移到array末端
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
flag = False
if flag:
break
return array
array = [23, 45, 67, 2, 4, 24]
result = bubble_sort(array)
print(result)
二、选择排序
原理:
首先在未排序序列中找到最大(小)值,存放在排序序列的起始位置,然后,再从剩余未排序序列元素中继续寻找最小(大)值元素,然后放到已经排序的序列末尾,以此类推,直到所有元素均排序完毕。
步骤:
......
排序演示:
select_sort.png其中红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。
复杂度:
比较次数 O(n * n),比较次数与关键字的初始状态无关,总的比较次数N = (n-1) + (n - 2) + ... + 1 = n * (n -1) / 2 。
交换次数 O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换 n-1次。交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
时间复杂度:
最坏情况:O(n * n)
最好情况:O(n * n)
平均情况:O(n * n)
空间复杂度:
O(n),O(1)辅助空间
代码:
def select_sort(array):
length = len(array)
for i in range(length):
min = i
for j in range(i+1, length):
if array[j] < array[min]:
min = j
array[min], array[j] = array[j], array[min]
return array
if __name__ == '__main__':
array = [23, 45, 67, 2, 4, 24]
result = select_sort(array)
print(result)
三、插入排序
原理:
插入排序的工作原理是,对于每个未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
步骤:
1、从第一个元素开始,该元素可以认为已经被排序。
2、取出下一个元素,在已经排序的元素序列中从后往前扫描。
3、如果该元素(已排序)大于新元素,将该元素移到下一位置。
4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
5、将新元素插入到该位置后。
6、重复步骤2~5。
排序演示:
insert_png复杂度:
最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需n-1 次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n * (n -1) / 2次.
时间复杂度:
最坏情况:O(n * n)
最好情况:O(n)
平均时间:O(n * n)
空间复杂度:
总共O(n),辅助空间O(1)
代码:
def insert_sort(array):
length = len(array)
if length == 1:
return array
for i in range(1, length):
# 对已经排序的序列进行该元素的插入适当位置操作
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
return array
def insert_sort_v2(array):
length = len(array)
if length == 1:
return array
for i in range(1, length):
temp = array[i]
j = i - 1
while j >= 0 and temp < array[j]:
array[j+1] = array[j]
j -= 1
array[j+1] = temp
return array
if __name__ == '__main__':
array = [23, 45, 67, 2, 4, 24]
result = insert_sort(array)
print(result)
四、快速排序
原理:
快速排序,又称划分交换排序。在平均状况下,排序n个数据要Ο(n log n)次比较。快速排序使用了分治法的思想。
步骤:
1、在待排序数组中选取一个基准。
2、重新排列数组,使得比基准数小的都排在基准数前面,比基准数大的都排在基准数后面。
3、递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
排序演示:
quick_sort.png复杂度:
空间复杂度:O(logn), 最坏情况下O(n).
平均或最优时间复杂度:O(nlgn).
最差时间复杂度:O(n^2)
在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。
代码:
# 解法一
def quick_sort(array):
if not array:
return []
else:
pivot = array[0]
less = [i for i in array if i < pivot]
more = [i for i in array[1:] if i >= pivot]
return quick_sort(less) + [pivot] + quick_sort(more)
# 解法二
def quick_sort1(array):
less = []
more = []
pivot_list = []
if len(array) <= 1:
return array
pivot = array[0]
for data in array:
if data < pivot:
less.append(data)
elif data > pivot:
more.append(data)
else:
pivot_list.append(data)
less = quick_sort1(less)
more = quick_sort1(more)
return less + pivot_list + more
array = [23, 45, 65, 2, 6, 34, 67, 34]
res = quick_sort(array)
print(res)
五、归并排序
原理:
归并排序是创建在归并操作上的一种有效的排序算法。使用分治法的思想,并且且各层分治递归可以同时进行。
步骤:
1、分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
2、使用归并排序递归地排序两个子序列。
3、合并两个已排序的子序列成为排序后的序列。
参考:维基百科:归并排序
排序图示:
merge_sort.png复杂度:
空间复杂度:O(n)
时间复杂度:O(nlogn)
代码:
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
result = []
l = 0 # left下标
r = 0 # right下标
while l < len(left) and r < len(right):
if left[l] > right[r]:
result.append(right[r])
r += 1
else:
result.append(left[l])
l += 1
result += left[l:]
result += right[r:]
return result
五、希尔排序
原理:
希尔排序也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
步骤:
1、将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。
2、假设有这样一组数[ 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步长进行排序(此时就是简单的插入排序了)。
参考:维基百科:希尔排序
复杂度:
代码:
一、堆排序
说明:
堆排序算法在获取最大或者最小k个数这类型题目上使用比较多。堆排序是采用二叉堆的数据结构来实现的,近似完全二叉树的结构。
二叉堆有以下性质:
父节点的键值总是大于或等于(小于或等于)任何子节点的键值。
每个子节点同样都是一个二叉堆(最大堆或者最小堆)。
堆的操作
1、构造最大堆: 将堆所有数据重新排序.
2、堆排序:
3、最大堆调整: 这个步骤是提供给上面两个步骤调用的。目的是将堆的末端子节点做调整后,使得子节点永远小于父节点
代码:
def heap_sort(array):
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 < end and array[child] < array[child+1]:
child += 1
if array[child] > array[root]:
array[child], array[root] = array[root], array[child]
root = child
else:
break
length = len(array)
for i in range((length-2) // 2, -1, -1):
sift_down(i, length-1)
for j in range(length-1, 0, -1):
array[j], array[0] = array[0], array[j]
sift_down(0, j-1)
return array
array = [23, 12, 45, 23, 456, 23, 567, 23, 56, 234]
result = heap_sort(array)
print(result)
网友评论