python实现常用排序算法

所谓排序，就是将数据分为有序区和无序区，通过对无序区元素的调整并扩展有序区，最后达到所有元素都有序的状态。
在排序界，常见（或者说常用）的算法主要有冒泡排序、直接插入排序、选择排序、希尔排序、堆排序、快速排序、归并排序。一些不太常用但是比较有技巧性的排序有：堆排序、桶排序、基数排序、位图排序、外部排序（一般结合hash然后多路归并）等。

一、早期排序算法

特点
时间复杂度都是O(N²)，只适合小数据集

1、冒泡排序（Bubble Sort）

对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。

def BubbleSort(ds):
    '''
    冒泡排序
    '''
    Length = len(ds)
    for i in range(0, Length):
        for j in range(i+1, Length):
            if ds[i] > ds[j]:
                ds[i], ds[j] = ds[j], ds[i]
    return ds

后来有人就想，每一次比较都要交换，那么可不可以先不交换元素位置，直到找到无序区中的最小元素的时候，再把最小元素放到有序区的末尾的位置呢？这样就减少了交换的次数，岂不是能节省很多不必要的交换，有了这个思想，于是有了选择排序。

2、选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。选择排序的基本思想是每一趟排序只找到无序区元素中最小的元素位置，然后将该元素放到有序区中的末尾位置，达到扩展有序区的目的。由于减少了交换的次数，所以选择排序是较冒泡排序优越的排序算法。

def SelectionSort(ds):
    '''
    选择排序
    '''
    Length = len(ds)
    for i in range(0, Length):
        ds_min = i  # 最小元素下标标记
        for j in range(i+1, Length):
            if ds[j] < ds[ds_min] :
                ds_min = j  # 找到最小值的下标
        ds[ds_min], ds[i] = ds[i], ds[ds_min]
    return ds

但是呢，每一次都要去无序区中找最小元素的位置，麻烦。既然都已经把整个待排序的数组划分为了有序区和无序区，那么为何不在访问无序区元素的过程中，将当前访问的元素在有序区中找到一个合适的位置放下不就好了么？于是有了插入排序。

2、插入排序（Insertion Sort）

想象打扑克时抓牌和整理牌的情形，当手中的牌已经有序时，再次抓起来的牌只需要找一个合适的位置放好即可。在插入排序中，假设第一个元素是有序的，从第二个起依次找到有序区合适的位置插入即可。插入排序中需要移动元素的位置，当数组基本有序（小的基本在前边，大的基本在后边）的时候，插入排序的效率最高。
概括来说就是每一步将一个待排序的记录，在已排序序列中从后向前扫描，找到相应位置并插入，直到插完所有元素为止。

def InsertionSort(ds):
    '''
    插入排序
    '''
    Length = len(ds)
    for i in range(1, Length):
        if ds[i] < ds[i-1]:
            temp = ds[i]
            index = i   # 待插入的下标
            for j in range(i-1, -1, -1):  #从i-1 循环到 0 (包括0)
                if ds[j] > temp :
                    ds[j+1] = ds[j]
                    index = j   # 记录待插入下标
                else :
                    break
            ds[index] = temp
    return ds

但是，很多情况下是很难满足基本有序的情况。既然插入排序在基本有序的情况下性能相对较好，那人们就想办法达到这样已终止状态。于是有人想出了跳跃分割的方式：将相距某个增量的数据组成一个子序列，这样就能保证在子序列内分别进行插入排序后得到的结果基本有序，这就是希尔排序。

二、中期排序算法

特点
时间复杂度冲破了O(N²)的瓶颈

希尔排序（Shell Sort）

希尔排序（该算法也被称为：缩小增量排序/分组插入排序）是直接插入排序算法的一种更高效的改进版本，它是一个里程碑式的排序算法。在希尔排序之前，人们一直认为数组的排序时间复杂度不可能超越O(N²)，希尔排序时间复杂度达到了大概O(N^3/2)。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
有了希尔排序的进步才有了后来的快速排序、堆排序、归并排序等一系列的O(NlogN)算法出现。

def ShellSort(ds):
    '''
    希尔排序
    '''
    Length = len(ds)
    gap = round(Length/2)  #初始步长,用round四舍五入取整
    while gap > 0 :
        for i in range(gap, Length):  # 每一列进行插入排序,从gap 到 n-1
            temp = ds[i]
            j = i
            while ( j >= gap and ds[j-gap] > temp ):  # 插入排序
                ds[j] = ds[j-gap]
                j = j - gap
            ds[j] = temp
        gap = round(gap/2)   # 重新设置步长
    return ds

三、后期排序算法

特点
时间复杂度约O(NlogN)

1、堆排序（Heat Sort）

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。时间复杂度O(NlogN)
基本思路：
a.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;(升序方法)
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

def HeatSort(ds):
    '''
    堆排序
    '''
    def siftdown(ds, start, end):  
        root = start  
        while True:  
            child = 2*root + 1  
            if child > end:break  
            if child+1<=end and ds[child] < ds[child+1]:  
                child += 1  
            if ds[child] > ds[root]:  
                ds[child],ds[root] = ds[root],ds[child]  
                root=child  
            else:  
                break  
    for start in range((len(ds)-2)//2, -1, -1):  
        siftdown(ds, start,len(ds)-1)  
    for end in range(len(ds)-1, 0, -1):  
        ds[end], ds[0] = ds[0], ds[end]  
        siftdown(ds, 0, end - 1)  
    return ds

2、快速排序（Quick Sort）

快速排序思想是对冒泡排序的改进，采用了分治思想。时间复杂度是O(NlogN)
基本思路：
a.先从数列中取出一个数作为基准数。
b.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
c.再对左右区间重复第二步，直到各区间只有一个数。
d.每次划分得到，枢椎的左边比它小，右边比它大。

def QuickSort(ds):
    '''
    快速排序
    '''
    if len(ds) < 2:
        return ds
    # 选取基准
    mid = ds[len(ds) // 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    ds.remove(mid)
    for item in ds:
        if item >= mid:
            # 大于基准值放右边
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
     # 使用迭代进行比较
    return quick_sort(left) + [mid] + quick_sort(right)

b = [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
print(QuickSort(b))

3、归并排序（Merge Sort）

归并排序也采用了分治思想，将问题分成一些小的问题然后递归求解，然后将得到的各答案"修补"在一起，即分而治之。时间复杂度是O(NlogN)

def MergeSort(ds):
    '''
    归并排序
    '''
    def merge(left, right):
        res = []
        while left and right:
            if left[0] < right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        res = res + left + right
        return res
    if len(ds) <= 1:
        return ds
    mid = len(ds)//2
    left = MergeSort(ds[:mid])
    right = MergeSort(ds[mid:])
    return merge(left,right)

各种排序算法对比：

	平均情况	最好情况	最坏情况	是否稳定
冒泡排序	O(n2)	O(n2)	O(n2)	YES
选择排序	O(n2)	O(n2)	O(n2)	NO
插入排序	O(n2)	O(n)	O(n2)	YES
希尔排序	O(n1.5)	O(n)	O(n1.5)	NO
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	NO
快速排序	O(nlogn)	O(nlogn)	O(n2)	NO
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	YES