姓名：宋子璇
学号：16020199060
转载自：https://zhuanlan.zhihu.com/p/34854599
【嵌牛导读】：排序算法对比
【嵌牛鼻子】：排序 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.过程
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.过程：
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]挖出再填到上一个坑中。
image
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]。
image
3）可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
image
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)，它也是不稳定排序。首先简单了解下堆结构。
堆
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
image
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
image
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序基本思想及步骤
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
image
假设给定无序序列结构如下
1、此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
image
2、找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
image
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
image
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
3、将堆顶元素9和末尾元素4进行交换
image
4、重新调整结构，使其继续满足堆定义
image
5、再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
image
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
501521032602_.pi
再简单总结下堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
