排序算法总结

知乎参考地址

最近在刷Leetcode过程中，部分题目需要手写排序算法。发现很多之前学习过的排序算法，均已经玩的差不多啦。特将常见的排序算法思想与算法实现总结如下：

准备工作

这里直接采用LeetCode回答所采用的准备工作，用于测试或算法部件

• 生成算法需要的数列：随机数列
• 对于一些极端情况，考虑算法的效率，需要生成基本有序的数列
• 测试算法性能的函数
• 判断数列是否有序
• 数列中元素相互交换
• 数列的拷贝

生成随机数列

#coding=utf-8
from random import randint
def generateRandomArray(n, min, max):
    arr = []
    arr = [randint(min, max) for x in range(n)]
    return arr

生成基本有序的数列

def generateNearlyOrderedArray(n, swapTimes):
    arr = []
    for i in range(n):
        arr.append(i)
    for j in range(swapTimes):
        posx = randint(0, n-1)
        posy = randint(0, n-1)
        arr[posx], arr[posy] = arr[posy], arr[posx]
    return arr

判断数列是否有序

def isSorted(alist):
    for i in range(0, len(alist)-1):
        if alist[i] > alist[i+1]:
            return False
    return True

测试算法性能

t1 = timeit.Timer('testSort("某种排序算法函数", alist)', 'from __main__ import testSort, 某种排序算法函数, alist')
print('某种排序算法：%s s' %t1.timeit(number=1))

# func表示要检测的算法函数，alist为传入的数列
def testSort(func, alist):
    alist =  func(alist)
    assert isSorted(alist), "排序算法错误\n"

数列中元素互换

alist[i], alist[j] = alist[j], alist[i]

数列拷贝

# 直接使用切片
# list = [8,6,2,3,1,5,7,4]
alist=list[:]

比较类排序

指通过比较元素间的相对次序，来完成排序的算法，但其时间复杂度无法超过$O(n\log(n))$,也称为非线性时间比较类排序。

交换排序

冒泡排序（Bubble Sort）

算法思想

冒泡排序要对一个列表多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对 列表实行一次遍历，就有一个最大项排在了正确的位置。

大体上讲，列表的每一个数据项都会在 其相应的位置 “冒泡”。如果列表有 n 项，第一次遍历就要比较 n-1 对数据。最不理想的情况下（逆序）：需要遍历 $n-1$ 次，最理想的情况下：需要遍历$1$ 次

算法图解

代码实现

def bubbleSort(alist):
    n = len(alist)
    exchange = False
    for i in range(n-1, 0, -1):
        for j in range(0, i):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
                exchange = True
        # 如果发现整个排序过程中没有交换，提前结束
        if not exchange:
            break
    return alist

算法分析

• 时间复杂度：$O(n^2)$

  • 最理想$O(n)$

• 空间复杂度：$O(1)$

• 稳定

快速排序

算法思想

很经典的排序算法。通过一趟排序将数据分割为两部分，一部分的数据均比另一部分的数据要小；再按照此方法对两部分数据分别进行快速排序，可利用递归方式实现。通常步骤：

1. 从数列中挑选一个基准；
2. 重新排序数列，所有比基准小的元素放在基准前面，所有比基准大的放在基准后面（基准本身已排好）；
3. 递归的把左右两区进行上述两步骤。

算法图解

代码实现

def quickSort(alist, l, r):

    #当数列的大小比较小的时候，数列近乎有序的概率较大
    # if (r - l <= 15):
    #     insertionSortHelp(alist, l, r)
    #     return

    if l >= r:
        return
    # p = partition(alist, l, r)
    p = partition(alist, l, r)

    quickSort(alist, l, p-1)
    quickSort(alist, p+1, r)

# 在alist[l...r]中寻找j,使得alist[l...j] <= alist[l], alist[j+1...r] >alist[l]
def partition(alist, l, r):
    pos = randint(l, r)
    alist[pos], alist[l] = alist[l], alist[pos]
    v = alist[l]
    # v = alist[l]
    # j 表示v值所应当在的位置
    j = l
    i = l + 1
    while i <= r:
        if alist[i] <= v:
            alist[j+1],alist[i] = alist[i],alist[j+1]
            j += 1
        i += 1
    alist[l], alist[j] = alist[j], alist[l]
    return j

算法分析

• 时间复杂度：$n\log(n)$
• 空间复杂度：$n\log(n)$

手写上面的快排

def quickSort(nums , l , r):
	if l >= r :
        return 
   	p = partition(nums , l , r)
    
    quickSort(nums , l , p-1)
    quickSort(nums , p+1 , r)
def partition(nums , l , r):
    v = nums[l]
    # 表示V值所在的位置
    j = l
    # 工作指针
    i = l + 1
    while i <= r:
        if nums[i] < v:
          j += 1
          nums[i] , nums[j+1] = nums[j+1] , nums[i]
        i += 1
    nums[j] , nums[l] = nums[l] , nums[j]
	return j

上面partition函数中需要仔细分辨，例如一开始工作指针与V值所在位置的理解，以及最后的变化；

插入排序

简单插入排序

算法思想

它总是保持一个位置靠前的 已排好的子表，然后每一个新的数据项被 “插入” 到前边的子表里，排好的子表增加一项。我们认为只含有一个数据项的列表是已经排好的。每排后面一个数据（从 1 开始到 n-1），这 个的数据会和已排好子表中的数据比较。比较时，我们把之前已经排好的列表中比这个数据大的移到它的右边。当子表数据小于当前数据，或者当前数据已经和子表的所有数据比较了时，就可 以在此处插入当前数据项。

算法图解

代码实现

# 插入排序
def insertionSort(alist):
    for i in range(1,len(alist)):
        currentvalue=alist[i]
        position=i
        while alist[position-1]>currentvalue and position>0:
            alist[position]=alist[position-1]
            position=position-1
        alist[position]=currentvalue
    return alist 

算法分析

• 时间复杂度：$O(n^2)$
• 空间复杂度:$O(1)$

希尔排序

算法思想

这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。

算法图解

代码实现

def shellSort(alist):
    n = len(alist)
    gap = n // 2
    while gap > 0:
        for i in range(gap):
            gapInsetionSort(alist, i, gap)
        gap = gap // 2
    return alist
def gapInsetionSort(alist,startpos,gap):
    #希尔排序的辅助函数
    for i in range(startpos+gap,len(alist),gap):
        position=i
        currentvalue=alist[i]

        while position>startpos and alist[position-gap]>currentvalue:
            alist[position]=alist[position-gap]
            position=position-gap
        alist[position]=currentvalue

算法分析

• 时间复杂度：$n\log (n)$

选择排序

简单选择排序

算法思想

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 初始状态：无序区为R[1..n]，有序区为空；

• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

• n-1趟结束，数组有序化了。

算法图解

代码实现

def selectionSort(alist):
    n = len(alist)

    for i in range(n - 1):
        # 寻找[i,n]区间里的最小值
        min_index = i
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist

算法分析

• 时间复杂度：$O(n^2)$
• 空间复杂度:$O(1)$

堆排序

算法思想

堆排序是一种基于二叉堆（Binary Heap）结构的排序算法，所谓二叉堆，我们通过完全二叉树来对比，只不过相比较完全二叉树而言，二叉堆的所有父节点的值都大于（或者小于）它的孩子节点，像这样：

首先需要引入最大堆的定义：

• 最大堆中的最大元素值出现在根结点（堆顶）
• 堆中每个父节点的元素值都大于等于其孩子结点

算法图解

代码实现

#建立堆函数：

void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // 将最大元素设置为堆顶元素
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 
  
    // 如果 left 比 root 大的话
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    // I如果 right 比 root 大的话
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        // 递归地定义子堆
        heapify(arr, n, largest); 
    } 
} 

堆排序的方法如下，把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

void heapSort(int arr[], int n) 
{ 
    // 建立堆
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    // 一个个从堆顶取出元素
    for (int i=n-1; i>=0; i--) 
    { 
        swap(arr[0], arr[i]);  
        heapify(arr, i, 0); 
    } 
} 

算法分析

归并排序

二路归并排序

算法思想

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

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

算法图解

代码实现

#之前copy了一份归并排序的算法，但那份代码包含太多优化行，导致算法思路不清晰
def mergeSort(arr,l,r):
    # l == r 时，不做任何处理，单独有序
    if l < r :
        m = int((l + r) / 2)
        mergeSort(arr,l,m)
        mergeSort(arr , m+1 , r)
        merge(arr , l ,m , r)

def merge(arr , l , m , r):
    copyl = arr[l:m+1]
    copyr = arr[m+1:r+1]
    lenl = len(copyl)
    lenr = len(copyr)
    i = 0
    j = 0
    k = l
    while i < lenl and j < lenr :
        if copyl[i] < copyr[j]:
            arr[k] = copyl[i]
            k += 1
            i += 1
        else:
            arr[k] = copyr[ j]
            k += 1
            j += 1
    while i < lenl :
        arr[k] = copyl[i]
        k += 1
        i += 1
    while j < lenr:
        arr[k] = copyr[j]
        k += 1
        j += 1

注意：这里进行小的优化，当数列的长度小于等于15的时候，我们一般认为数列此时基本有序，这时候采用直接插入排序非常快。

# 自底向上的归并算法
def mergeBU(alist):
    n = len(alist)
    #表示归并的大小
    size = 1
    while size <= n:
        for i in range(0, n-size, size+size):
            merge(alist, i, i+size-1, min(i+size+size-1, n-1))
        size += size
    return alist

# 合并有序数列alist[start....mid] 和 alist[mid+1...end]，使之成为有序数列
def merge(alist, start, mid, end):
    # 复制一份
    blist = alist[start:end+1]
    l = start
    k = mid + 1
    pos = start

    while pos <= end:
        if (l > mid):
            alist[pos] = blist[k-start]
            k += 1
        elif (k > end):
            alist[pos] = blist[l-start]
            l += 1
        elif blist[l-start] <= blist[k-start]:
            alist[pos] = blist[l-start]
            l += 1
        else:
            alist[pos] = blist[k-start]
            k += 1
        pos += 1

算法分析

多路归并排序

这里没有写

非比较排序

非比较排序打破了时间复杂度$n\log n$ 的限制

计数排序

算法思想

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

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

算法图解

代码实现

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;
}

算法分析

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

桶排序

算法思想

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

桶排序的原理是将数组分到有限数量的桶中，再对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。

排序过程：

1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3. 将各个桶中的数据有序的合并起

算法图解

代码实现

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;
}

算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序

算法思想

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

算法图解

代码实现

var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

算法分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。