十大排序算法的总结、图解、对比与Python 实现

• 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1、插入排序

• 描述

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n²)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

如果数据序列基本有序，使用插入排序会更加高效。

• 代码实现

def insert_sort(lists):
    # 插入排序
    if len(lists) == 1:
    	return lists 
    for i in range(1, len(lists)):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

2、希尔排序

• 描述

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把数字串按下标的一定增量（间距）分组，即每组各个数据间的下标距离相同，这个距离即称为增量，对每组使用直接插入排序算法排序；随着增量逐渐减少（step一般为2），每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

• 代码实现

def shell_sort(lists):
    # 希尔排序
    count = len(lists)
    step = 2
    group = count / step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = lists[j]
                while k >= 0:
                    if lists[k] > key:
                        lists[k + group] = lists[k]
                        lists[k] = key
                    k -= group
                j += group
        group /= step
    return lists

3、冒泡排序

• 描述

它重复地走访过要排序的数列，每次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

• 在每一趟中临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换；

• 这样第1趟过去后,最大或最小的数字被交换到了最后1位。冒泡排序每趟归位一个最大值；

• 然后再从头开始第i趟，进行两两比较交换,直到倒数第i位时结束。

• 代码实现

def bubble_sort(lists):
    # 冒泡排序
    count = len(lists)
    for i in range(0, count):
        for j in range(i + 1, count):
            if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
    return lists

4、快速排序

• 描述

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

• 基本思想：（分治）

1. 先从数列中取出一个数作为key值，并保存；
2. 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边，（基准值在左则右侧哨兵先挪动）：

• 方法一
  • 右侧设立一个哨兵j，从右向左遍历，寻找一个比key小的值；
  • 左边设立一个哨兵i，从左向右遍历，寻找一个比key大的值；
  • 交换两个哨兵找到的值，并继续移动重复上述交换过程;
  • 当两个哨兵相遇时，在相遇未知与key值交换位置，此时key归位，产生左右两个子数列;
• 方法二：上述交换过程可用一个三次的挖坑填数罚来替代。
  • 将选定的基准值保存为key值，基准值位置为空；
  • 右侧设立一个哨兵j，从右向左遍历，寻找一个比key小的值，将此值赋给基准值的位置
  • 左边设立一个哨兵i，从左向右遍历，寻找一个比key大的值，将此值赋给右哨兵的位置
  • 将key值赋给左哨兵的位置

4. 对左右两个子数列重复第二步，直至各区间只有1个数。
   
   建议阅读详细图解：
   挖坑填数
   基准数与两个哨兵

• 代码实现

def quick_sort(lists, left, right):
    # 快速排序
    if left >= right: #子区间长度为1，结束排序
        return lists
    key = lists[left] #选择左侧作为基准值，定义左右哨兵
    low = left 
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right] #右哨兵找到小于key的值或哨兵相遇
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

5、选择排序

• 描述

  • 第1趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r1交换；
  • 第2趟，在待排序记录r3 ~ r[n]中选出最小的记录，将它与r2交换；
  • 以此类推，第i趟在待排序记录r[i+1] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到第n-1趟全部排序完毕。

• 代码实现

def select_sort(lists):
    # 选择排序
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        lists[min], lists[i] = lists[i], lists[min]
    return lists

6、堆排序

• 描述

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。 在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
对堆中的结点按层进行编号，该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

• 基本思路：

  • a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
  • b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
  • c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

详细请参考：图解堆排序

• 在大量数据（eg：5000）中将少部分数据（eg:10）排序的任务一般使用堆排序，因为只需要维护一个k=10的堆，空间效率和时间效率较高。
  
  
• 代码实现

#判断每个叶子节点与其父节点顺序是否正确，i为父节点
def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2: #记录max并交换
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)

#构造大根堆，其中最后一个非叶子节点为size/2-1，从后向前循环
def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)

def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

7、归并排序

• 描述

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

• 将数组分成2组A，B，如果这2组组内的数据都是有序的，那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了？
  可以将A，B组各自再分成2组。依次类推，当分出来的小组只有1个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的2个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

• 归并(有序数组合并)过程为：

  • 比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
  • 否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，
  • 如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

• 代码实现

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

def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

8、基数排序（radix sort）

• 描述

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

• BinSort

BinSort想法非常简单，首先创建数组A[MaxValue]；然后将每个数放到相应的位置上（例如17放在下标17的数组位置）；最后遍历数组，即为排序后的结果。

问题：当序列中存在较大值时，BinSort 的排序方法会浪费大量的空间开销。

• RadixSort

  基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销。

（1）首先确定基数为10，数组的长度也就是10.每个数34都会在这10个数中寻找自己的位置。
（2）不同于BinSort会直接将数34放在数组的下标34处，基数排序是将34分开为3和4，第一轮排序根据最末位放在数组的下标4处，第二轮排序根据倒数第二位放在数组的下标3处，然后遍历数组即可。

• 代码实现

import math
def radix_sort(lists, radix=10):
    k = int(math.ceil(math.log(max(lists), radix)))
    bucket = [[] for i in range(radix)]
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        for z in bucket:
            lists += z
            del z[:]
    return lists

9、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

• 描述
  找出待排序的数组中最大和最小的元素；
  统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
  反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

• 复杂度
  计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

• 这一算法为JAVA实现

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

10、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

• 描述
  设置一个定量的数组当作空桶；
  遍历输入数据，并且把数据一个一个放到对应的桶里去；
  对每个不是空的桶进行排序；
  从不是空的桶里把排好序的数据拼接起来。

• 图片演示
  

• 这一算法为JAVA实现

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

参考1
参考2