概述

排序算法：将一个列表元素按顺序进行排列的算法，比如我们经常遇到的按数字或字典升序降序。对于排序算法我们要关注它的时间复杂度、稳定性、排序方法等。

时间复杂度是衡量排序算法快慢的重要标准

时间复杂为 $O(n^2)$ 的简单排序：直接插入、直接选择和冒泡排序。
时间复杂为 $O(n\log n)$ 的排序：快速排序、堆排序和归并排序。
时间复杂度为 $O(n)$ 的排序：基数排序，此外还有桶、箱排序。

常见的时间复杂度耗时从小到大：

$O(1)$ < $O(log n)$ < $O(n)$ < $O(n\log n)$ < $O(n ^ 2)$ < $O(n ^ 3)$ < $O(2 ^ n)$ < $O(n !)$ < $O(n ^ n)$

稳定性：相同键值的纪录在排序前后相对位置保持不变，则说明算法具有稳定性。比如下面扑克按照从小到大排序，红桃5在黑桃5左边，稳定排序后它们的相对位置不变，不稳定排序后位置改变。

File:Sorting stability playing cards.svg

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

排序方法：插入、交换、选择、合并、分区等。交换排序包括冒泡排序和快速排序。选择排序包括循环排序和堆排序。

算法比较

虽然有大量的排序算法，但在实际上只有少数算法占主导地位。插入排序广泛用于小型数据集，而对于大型数据集，则使用高效的排序，主要是堆排序、合并排序或快速排序。高效的实现通常使用混合算法，将整体排序的高效算法与递归底部的小列表的插入排序相结合。例如在 Android、Java 和 Python 中使用的Timsort （合并排序、插入排序和附加逻辑），以及在某些C++ 排序中（以变体形式）使用的introsort （快速排序和堆排序）实现和.NET。

对于更受限的数据，例如固定区间的数字，广泛使用计数排序或基数排序等分布排序。冒泡排序和变体在实践中很少使用，但在教学和理论讨论中很常见。

在对对象进行物理排序时（例如按字母顺序排列的论文、测试或书籍），人们直观地通常对小集合使用插入排序。对于较大的集合，人们通常首先进行分组，例如按首字母，并且多个分组允许对非常大的集合进行实际排序。空间通常相对便宜，例如将物体散布在地板上或大面积上，但操作成本很高，尤其是将物体移动很远的距离——参考的位置很重要。合并排序对于物理对象也很实用，特别是因为可以使用两只手，每个要合并的列表一只手，而其他算法，例如堆排序或快速排序，不太适合人类使用。其他算法，如库排序，一种保留空格的插入排序的变体，对于物理使用也很实用。

需要掌握的主流排序算法

表格名词解释

$n$：排序的记录数；

$k$：键值大小；

$d$：数字大小；

$r$：要排序的数字范围；

时间复杂度：最好、平均、最坏；

空间复杂度：列表的存储和排序额外需要的空间；

In-place：固定数量的 $O(1)$ 内存空间，不需要更多额外内存。

比较排序

比较排序的平均性能大于等于 $O ( n \log n )$ 。

算法	最好	平均	最坏	空间	是否稳定性	方法	其它
插入排序	$n$	$n^{2}$	$n^{2}$	1	是	插入
选择排序	$n^{2}$	$n^{2}$	$n^{2}$	1	否	选择
归并排序	$n\log n$	$n\log n$	$n\log n$	$n$	是	合并
堆排序	$n\log n$	$n\log n$	$n\log n$	1	是	选择
快速排序	$n\log n$	$n\log n$	$n^{2}$	$\log n$	否	分区
希尔排序	$n\log n$	${\displaystyle n^{4/3}}$	${\displaystyle n^{3/2}}$	1	否	插入
冒泡排序	$n$	$n^{2}$	$n^{2}$	1	是	交换
梳状排序	$n\log n$	$n^{2}$	$n^{2}$	1	否	交换
交换排序	$n^{2}$	$n^{2}$	$n^{2}$	1	是	交换
树排序	$n\log n$	$n\log n$	$n\log n$	1	是	插入	使用自平衡二叉搜索树时

非比较排序

面的复杂性假设要对 n 个项目进行排序，键的大小为 k，数字大小为d，而 r 是要排序的数字范围。

算法	最好	平均	最坏	空间	是否稳定
计数排序	无	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	是
桶排序（唯一键）	无	$n+k$	$n^{2}\cdot k$	$n\cdot k$	是
桶排序（整数键）	无	$n+r$	$n+r$	$n+r$	是
LSD 基数排序	$n$	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	是
MSD 基数排序	无	$n\cdot {\frac {k}{d}}$	$n\cdot {\frac {k}{d}}$	$n+2^{d}$	是
MSD 基数排序 (in-place)	无	${\displaystyle n\cdot {\frac {k}{1}}}$	${\displaystyle n\cdot {\frac {k}{1}}}$	$2^{1}$	否

简单排序

两种最简单的排序是插入排序和选择排序，它们的优点是开销低，很适合在小列表排序，但在大列表上效率不高，对于大列表可以使用希尔排序，它是插入排序的一种变体。插入排序在实践中比选择排序快，所以是首选，不过当插入操作（写入数据）有性能限制时，可以使用选择排序。

插入排序

插入排序（Insertion sort）是一种简单的排序算法。它的工作原理是依次取未排序元素，从后向前扫描已排序序列，找到相应位置并插入。

算法步骤

首先将第一个元素作为有序序列，后面元素是未排序列；
依次取未排序列元素，将其插入到有序序列的适当位置，如果元素相等则插入相等元素的后面。

代码实现-java

public class InsertSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}

代码实现-go

func insertionSort(arr []int) []int {
    for i := range arr {
        preIndex := i - 1
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]
            preIndex -= 1
        }
        arr[preIndex+1] = current
    }
    return arr
}

代码实现-Javascript

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

代码实现- python

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex+1] = arr[preIndex]
            preIndex-=1
        arr[preIndex+1] = current
    return arr

选择排序

选择排序（Selection sort）的时间复杂度固定为 $O ( n^2 )$ ，通常比类似的插入排序更差。在交换操作昂贵的情况下可以使用它，因为它不超过 $n$ 次交换。

算法步骤：

首先在未排序列中找到最小（大）元素，存放到有序序列的起始位置；
再从剩余未排序列中继续寻找最小（大）元素，然后放到有序序列的末尾；
重复第二步，直到所有元素均排序完毕。

代码实现-java

public class SelectionSort{

    public static int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

代码实现-go

func selectionSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length-1; i++ {
        min := i
        for j := i + 1; j < length; j++ {
            if arr[min] > arr[j] {
                min = j
            }
        }
        arr[i], arr[min] = arr[min], arr[i]
    }
    return arr
}

代码实现-javascript

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

代码实现-python

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

高效排序

归并排序

归并排序（Merge sort）是一种高效、通用且基于比较的排序算法，它是约翰·冯·诺依曼在 1945年发明的一种分而治之的算法。大体过程就是递归把当前列表平分成两个子列表，然后进行归并操作，归并操作（merge），就是将两个已经排序的列表合并成一个列表的操作。

归并操作有两种实现方法：递归法（自上而下）和迭代法（自下而上）。

递归法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤3直到某一指针到达序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

迭代法步骤

将序列每相邻两个数字进行归并操作，形成${\displaystyle ceil(n/2)}{\displaystyle ceil(n/2)}$ 个序列，排序后每个序列包含两/一个元素；
若此时序列数不是1个则将上述序列再次归并，形成 ${\displaystyle ceil(n/4)}{\displaystyle ceil(n/4)}$ 个序列，每个序列包含四/三个元素；
重复步骤2，直到所有元素排序完毕，即序列数为1；

分治算法：递归将一个问题分解为两个或多个相同的子问题，直到这些子问题变得简单到可以直接解决。然后将子问题的解决方案组合起来形成原始问题的解决方案。

代码实现递归版-java

public class MergeSort {
    public static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start, end1 = mid;
        int start2 = mid + 1, end2 = end;
        merge_sort_recursive(arr, result, start1, end1);
        merge_sort_recursive(arr, result, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2)
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        while (start1 <= end1)
            result[k++] = arr[start1++];
        while (start2 <= end2)
            result[k++] = arr[start2++];
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }
    public static void merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        merge_sort_recursive(arr, result, 0, len - 1);
    }
}

代码实现迭代版-java

public class MergeSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

代码实现递归版-go

package main

import (
	"fmt"
)

func merge(data []int) []int {
	sum := len(data)
	if sum <= 1 {
		return data
	}
	left := data[0 : sum/2]
	lSize := len(left)
	if lSize >= 2 {
		left = merge(left)
	}
	right := data[sum/2:]
	rSize := len(right)
	if rSize >= 2 {
		right = merge(right)
	}
	j := 0
	t := 0
	arr := make([]int, sum)
	fmt.Println(left, right, data)
	for i := 0; i < sum; i++ {
		if j < lSize && t < rSize {
			if left[j] <= right[t] {
				arr[i] = left[j]
				j++
			} else {
				arr[i] = right[t]
				t++
			}	
		}  else if j >= lSize{
			arr[i] = right[t]
			t++
		}  else if t >= rSize{
			arr[i] = left[j]
			j++
		}
	}
	return arr
}

代码实现迭代-go

func mergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}
	middle := length / 2
	left := arr[0:middle]
	right := arr[middle:]
	return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
	var result []int
	for len(left) != 0 && len(right) != 0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	for len(left) != 0 {
		result = append(result, left[0])
		left = left[1:]
	}

	for len(right) != 0 {
		result = append(result, right[0])
		right = right[1:]
	}

	return result
}

代码实现递归版-javascript

function merge(left, right){
  var result = [];
  while(left.length > 0 && right.length > 0){
    if(left[0] < right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}

function mergeSort(arr){
  if(arr.length <=1) return arr;
  var middle = Math.floor(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

代码实现迭代版-javascript

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;

代码实现迭代版-python

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点，分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

将待排序列表构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。

代码实现- Java

public class HeapSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

代码实现-go

func heapSort(arr []int) []int {
    arrLen := len(arr)
    buildMaxHeap(arr, arrLen)
    for i := arrLen - 1; i >= 0; i-- {
        swap(arr, 0, i)
        arrLen -= 1
        heapify(arr, 0, arrLen)
    }
    return arr
}

func buildMaxHeap(arr []int, arrLen int) {
    for i := arrLen / 2; i >= 0; i-- {
        heapify(arr, i, arrLen)
    }
}

func heapify(arr []int, i, arrLen int) {
    left := 2*i + 1
    right := 2*i + 2
    largest := i
    if left < arrLen && arr[left] > arr[largest] {
        largest = left
    }
    if right < arrLen && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        swap(arr, i, largest)
        heapify(arr, largest, arrLen)
    }
}

func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

代码实现-javascript

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

代码实现-python

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1
        heapify(arr, 0)
    return arr

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。快速排序又是分治算法的另一个应用。快速排序和归并排序的平均时间复杂度都是${\displaystyle n\log n}$，但快速排序在大多数情况下都比平均复杂度为 ${\displaystyle n\log n}$ 的排序算法表现要更好。

归并排序与快速排序对比

归并排序是将列表递归分解成只有一个元素的子列表然后再合并，核心算法是合并函数（merge）。快速排序是任意选择一个元素进行分区（分为小于，等于，大于三部分），然后依次对小于和大于部分递归排序，核心算法是分区函数（partition）。

最坏情况下快速排序时间复杂度 $O(n^2)$ 超过归并排序的 ${\displaystyle O(n\log n)}$，但从空间复杂度来看归并排序就算最佳情况下也需要${\displaystyle \Omega (n)}$额外的空间。

实际执行时间要考虑常量时间因素$c$，快速排序不用创建辅助数组来保存临时值，而归并排序需要分配和取消分配辅助数组，所以归并需要的常量时间要比快速多，这就是快速排序在大多数情况下都比平均复杂度为 ${\displaystyle n\log n}$ 的排序算法表现要更好原因。 $$ {\displaystyle T(n)=n\log n + c} $$ 快速排序性能优势在于随机存取的cheap，当排序结构为链表时候就显得比较糟糕（链接列表单元通常散布在整个内存中，它只在相邻元素查找具有优势而随机存取效率很低），此时归并排序反而会更高效。

快速排序算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码实现-java

public class QuickSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

代码实现-go

func quickSort(arr []int) []int {
    return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
    if left < right {
        partitionIndex := partition(arr, left, right)
        _quickSort(arr, left, partitionIndex-1)
        _quickSort(arr, partitionIndex+1, right)
    }
    return arr
}

func partition(arr []int, left, right int) int {
    pivot := left
    index := pivot + 1

    for i := index; i <= right; i++ {
        if arr[i] < arr[pivot] {
            swap(arr, i, index)
            index += 1
        }
    }
    swap(arr, pivot, index-1)
    return index - 1
}

func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

代码实现-javascript

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

代码实现-python

def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

希尔排序

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

shell_sort

代码实现-java

public class ShellSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }
}

代码实现-go

func shellSort(arr []int) []int {
	length := len(arr)
	gap := 1
	for gap < length/3 {
		gap = gap*3 + 1
	}
	for gap > 0 {
		for i := gap; i < length; i++ {
			temp := arr[i]
			j := i - gap
			for j >= 0 && arr[j] > temp {
				arr[j+gap] = arr[j]
				j -= gap
			}
			arr[j+gap] = temp
		}
		gap = gap / 3
	}
	return arr
}

代码实现-javascript

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

代码实现-python

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

冒泡排序

冒泡排序以及希尔排序和鸡尾酒排序等变体是简单、效率极低的排序算法。这种算法的优点就在于简单吧，一般指出现在教材中，很少用于实践。

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复遍历未排数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现- Java

public class BubbleSort {

    public static int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

代码实现- go

func bubbleSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        for j := 0; j < length-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

代码实现- javascript

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

代码实现- python

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

梳排序

梳排序（Com bsort）是冒泡排序和快速排序的一种改良版，主要是消除在数组尾部的小数值，这些数值是造成冒泡排序缓慢的主因

代码实现-java

public static <E extends Comparable<? super E>> void sort(E[] input) {
    int gap = input.length;
    boolean swapped = true;
    while (gap > 1 || swapped) {
        if (gap > 1) {
            gap = (int) (gap * 0.8);
        }
        int i = 0;
        swapped = false;
        while (i + gap < input.length) {
            if (input[i].compareTo(input[i + gap]) > 0) {
                E t = input[i];
                input[i] = input[i + gap];
                input[i + gap] = t;
                swapped = true;
            }
            i++;
        }
    }
}

代码实现-go

func comb_sort(data sort.Interface) {
	n := data.Len()
	shrinkFactor := 0.8
	gap := n
	swapped := true

	for gap > 1 || swapped {
		if gap > 1 {
			gap = int(float64(gap) * shrinkFactor)
		}

		// 冒泡排序
		swapped = false
		for i := 0; i < n - gap; i++ {
			if data.Less(i + gap, i) {
				data.Swap(i + gap, i)
				swapped = true
			}
		}
	}
}

代码实现-javascript

Array.prototype.comb_sort = function() {
	var shrink_factor = 0.8;
	var gap = this.length, swapped = 1, i;
	var temp;
	while (gap > 1 || swapped) {
		if (gap > 1)
			gap = Math.floor(gap * shrink_factor);
		swapped = 0;
		for (i = 0; gap + i < this.length; i++)
			if (this[i] > this[i + gap]) {
				temp = this[i];
				this[i] = this[i + gap];
				this[i + gap] = temp;
				swapped = 1;
			}
	}
	return this;
};

分布排序

分布排序的算法，可以将数据切割分布到多个中间结构进行排序，然后再收集合并。它可以运行在单处理器上和分布式计算机上。并支持对于海量外部排序。

外部排序算法通常分为两种类型，分布排序，类似于快速排序，外部归并排序，类似于归并排序。后者通常使用混合排序合并策略。在排序阶段，读取、排序并写入临时文件的小到足以放入主内存的数据块。在合并阶段，将排序后的子文件合并为一个更大的文件。

计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组 ${\displaystyle C}$ ，其中第 $i$ 个元素是待排序数组${\displaystyle A}$ 中值等于 ${\displaystyle i}$ 的元素的个数。然后根据数组 ${\displaystyle C}$ 来将 ${\displaystyle A}$ 中的元素排到正确的位置。

算法步骤

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

代码实现-java

public class CountingSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

}

代码实现-go

func countingSort(arr []int, maxValue int) []int {
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen) // 初始为0的数组

    sortedIndex := 0
    length := len(arr)

    for i := 0; i < length; i++ {
        bucket[arr[i]] += 1
    }

    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }

    return arr
}

代码实现-javascript

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

代码实现-python

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再进行排序（有可能使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

算法步骤：

设置一个定量的数组当作空桶子；
遍历序列，并且把项目一个一个放到对应的桶子去；
对每个不是空的桶子进行排序；
从不是空的桶子里把项目再放回原来的序列中。

bucket_sort_2

代码排序-java

public class BucketSort{

    private static final InsertSort insertSort = new InsertSort();

    public static int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

代码实现- javascript

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

基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序不局限于整数排序。

基数排序可以实现方式有：从最高有效位(MSD) 或最低有效位(LSD) 开始。例如，对于1234，可以从 1 (MSD) 或 4 (LSD) 开始。

计数排序、桶排序、基数排序都利用了桶，但对桶的使用方法上有明显差异：

计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值；
基数排序：根据键值的每位数字来分配桶；

代码实现-java

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

代码实现- javascript

//LSD Radix Sort
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;
}