排序算法对比、总结(Python代码)
排序算法对比、总结(Python代码)
排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。
内排序有可以分为以下几类：
1、插入排序：直接插入排序、二分法插入排序、希尔排序。
2、选择排序：直接选择排序、堆排序。
3、交换排序：冒泡排序、快速排序。
4、归并排序
5、基数排序
对比
冒泡排序
1.基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
2.过程：
比较相邻的两个数据，如果第二个数小，就交换位置。
从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
3.平均时间复杂度：O(n2)
4.优化：
针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
5.Python代码实现：
@staticmethoddef bubble_sort(arr): for i in range(len(arr)): not_change = True for j in range(len(arr) - 1, i - 1, -1):
if arr[j] < arr[j - 1]: tmp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = tmp not_change = False if not_change:
break
return arr
选择排序
1.基本思想：
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
2.过程：
image
3.平均时间复杂度：O(n2)
4.python代码实现：
@staticmethoddef select_sort(arr): for index in range(len(arr)): min_index = index
for j in range(index + 1, len(arr)):
if arr[j] < arr[min_index]: min_index = j
if min_index != index: tmp = arr[index] arr[index] = arr[min_index] arr[min_index] = tmp
return arr
插入排序
1.基本思想：
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
2.过程：
image
3.平均时间复杂度：O(n2)
4.python代码实现：
@staticmethoddef insert_sort(arr): for index in range(len(arr) - 1):
for j in range(index + 1, 0, -1):
if arr[j] < arr[j - 1]:
tmp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = tmp
else:
break return arr
希尔排序
1.基本思想：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2.过程：
3.平均时间复杂度：O（n*logn）
4.python代码实现：
def shell_sort(arr): gap = len(arr)
while True: gap = int(gap / 2)
for arr_index in range(gap): print('arr_index:', arr_index)
for element in range(arr_index, len(arr) - 1, gap): print('element:', element)
for j in range(element, arr_index, -gap):
# print('j', j) if arr[j] < arr[element - gap]: tmp = arr[element - gap] arr[element - gap] = arr[j] arr[j] = tmp
else:
break if gap == 1:
break return arr快速排序
1.基本思想：（分治）
先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。
2.过程
1）初始时 i = 0; j = 9; key=72 由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。
2）此时 i = 3; j = 7; key=72 再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将key填入a[5]。
3）可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
3.平均时间复杂度：O(N*logN)
4.Python代码实现：
def quick_sort(self, arr, left, right): if left >= right: return key = arr[left] i = left j = right while i < j:
while i < j and arr[j] >= key: j -= 1 if i < j: arr[i] = arr[j] i += 1 while i < j and arr[i] < key: i += 1 if i < j: arr[j] = arr[i] j -= 1 arr[i] = key self.quick_sort(arr, left, i - 1) self.quick_sort(arr, i + 1, right)
return arr堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序基本思想及步骤
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
假设给定无序序列结构如下
1、此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
2、找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
3、将堆顶元素9和末尾元素4进行交换
4、重新调整结构，使其继续满足堆定义
5、再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
代码实现：
@staticmethoddef heap_sort(arr): # 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） def adjuct_heap(array, index, length): # 先取出当前元素i temp = array[index]
# 从i结点的左子结点开始，也就是2i + 1处开始 k = index * 2 + 1 while k < length:
# 如果左子结点小于右子结点，k指向右子结点 if k + 1 < length and array[k] < array[k + 1]: k += 1 # 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换） if array[k] > temp: array[index] = array[k] index = k
else:
break k = 2 * k + 1 # 将temp值放到最终的位置 array[index] = temp
# 构建最大堆 for i in range(int(len(arr) / 2 - 1), -1, -1):
# 从第一个非叶子节点从下至上，从右至左调整结构 adjuct_heap(arr, i, len(arr))
for j in range(len(arr) - 1, -1, -1): tmp = arr[j] arr[j] = arr[0] arr[0] = tmp adjuct_heap(arr, 0, j)
return arr归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
合并相邻有序子序列
来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
Python代码：
def merge_sort(self, lists): def merge(left, right): i, j = 0, 0 result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]: result.append(left[I]) i += 1 else: result.append(right[j]) j += 1 result += left[I:] result += right[j:]
return result
# 归并排序 if len(lists) <= 1:
return lists num = int(len(lists) / 2) left = self.merge_sort(lists[:num]) right = self.merge_sort(lists[num:])
return merge(left, right)基数排序
不需要直接对元素进行相互比较，也不需要将元素相互交换，你需要做的就是对元素进行“分类”。这也是基数排序的魅力所在，基数排序可以理解成是建立在“计数排序”的基础之上的一种排序算法。在实际项目中，如果对效率有所要求，而不太关心空间的使用时，我会选择用计数排序（当然还有一些其他的条件），或是一些计数排序的变形。
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
如果我们的无序是 T = [ 2314, 5428, 373, 2222, 17 ]，那么其排序的过程就如下两幅所示。
上面这幅图，或许你已经在其他的博客里见到过。这是一个很好的引导跟说明。在基数排序里，我们需要一个很大的二维数组，二维数组的大小是 （10 * n）。10 代表的是我们每个元素的每一位都有 10 种可能，也就是 10 进制数。在上图中，我们是以每个数的个位来代表这个数，于是，5428 就被填充到了第 8 个桶中了。下次再进行填充的时候，就是以十位进行填充，比如 5428 在此时，就会选择以 2 来代表它。
基数排序过程图-1
基数排序过程图-2
python代码：
@staticmethoddef radix_sort(lists, radix=10): # k = int(math.ceil(math.log(max(lists), radix))) k = radix bucket = [[] for i in range(radix)]
for i in range(k):
for j in lists: bucket[int(j / (radix ** (i - 1)) % (radix))].append(j)
# bucket[int(j % (radix))].append(j) del lists[:]
for z in bucket: lists += z
del z[:] print(lists)
return lists参考链接： http://python.jobbole.com/82270/ https://www.jianshu.com/p/ae97c3ceea8d https://www.cnblogs.com/chengxiao/p/6194356.html