排序算法

概述

排序是将无序的序列变成有序的序列的计算过程，是计算机程序设计中最基础算法之一。

分类

排序算法一般分为两大类：

比较类排序：通过比较操作来实现，其时间复杂度不能突破$O(nlogn)$，故也称为非线性时间比较类排序。
非比较类排序：不通过比较操作实现，可突破基于比较排序的时间下界，可以线性时间运行，代价往往需要额外的空间；

分类	排序方法	时间复杂度(Avg/Max/Min)	空间复杂度	稳定性
比较	冒泡排序	$O(n^2)$/$O(n^2)$/$O(n)$	$O(1)$	稳定
	插入排序	$O(n^2)$/$O(n^2)$/$O(n)$	$O(1)$	稳定
	选择排序	$O(n^2)$/$O(n^2)$/$O(n^2)$	$O(1)$	不稳定
	希尔排序	$O(n^{1.3})$/$O(n^2)$/$O(n)$	$O(1)$	不稳定
	归并排序	$O(nlog{{n}})$/$O(nlog{{n}})$/$O(nlog{{n}})$	$O(n)$	稳定
	堆排序	$O(n{log}n)$/$O(nlog{{n}})$/$O(nlog{{n}})$	$O(1)$	不稳定
	快速排序	$O(n{log}n)$/$O(n^2)$/$O(nlog{{n}})$	$O(nlog_2n)$	不稳定
非比较	基数排序	$O(nk)$/$O(nk)$/$O(n*k)$	$O(n+k)$	稳定
	计数排序	$O(n+k)$/$O(n+k)$/$O(n+k)$	$O(n+k)$	稳定
	桶排序	$O(n+k)$/$O(n^2)$/$O(n)$	$O(n+k)$	稳定

比较排序

冒泡排序（Bubble Sort）

冒泡排序是一种比较排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/// # 冒泡排序

pub fn bubble_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd
{
    for i in 1..nums.len() {        // 外层控制遍历的次数
        let mut sorted = true;      // 提前判断是否有序
        for j in 0..nums.len()-i {  // 内存控制每次遍历比较的次数
            if nums[j] > nums[j+1] {
                nums.swap(j, j+1);
                sorted = false;
            }
        }
        if sorted {  //如果一次遍历中, 所有前面的元素都<后面元素, 则表明遍历的序列有序
            break;   
        }
    }
}

鸡尾酒排序

鸡尾酒排序是一种双向冒泡排序；
从两个方向（低到高、高到低）同时冒泡排序，效率更高；

算法描述

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// # 鸡尾酒排序
pub fn cocktail_shaker_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd
{
    let L = nums.len();
    let mut i = 0;
    while i + 1 < L - i {
        let mut sorted = true;
        for k in i..(L-1-i) {
            if  nums[k] > nums[k+1] {
                nums.swap(k, k+1);
                sorted = false;
            }
            if  nums[L-1-k] < nums[L-1-k-1] {
                nums.swap(L-1-k, L-1-k-1);
                sorted = false;
            }
        }
        if sorted {
            break;
        }
        i += 1;
    }
}

选择排序（Selection Sort）

选择排序(Selection-sort)是一种比较排序算法；
它通过将数组分为前后2个部分：
- 前面已排序部分(初始大小为0)；
- 后面未排序部分(初始大小为nums.len())；
然后依次从未排序部分中选择(Select)剩下的最小元素，将其放到前面已排序部分的末尾；
如此重复, 直到所有后面部分元素都被加入到前面, 则排序完成；

算法描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为 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 趟结束，数组有序化了。

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/// # 选择排序
pub fn select_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd
{
    for i in 0..nums.len() {                 
        let mut mi = i;                 // 未排序部分最小元素初始下标
        for j in i+1..nums.len() {      // 遍历未排序部分, 寻找最小元素下标
            if nums[j] < nums[mi] {     //
                mi = j;
            }
        }
        nums.swap(i, mi);                // 将最小元素和未排序部分最前面元素交换,
                                         // 即紧接已排序部分之后
    }
}

算法分析

选择排序是最稳定的排序算法之一，无论什么数据进去都是$O(^2)$的时间复杂度，
当数据规模小时有优势；
不占用额外的内存空间；

插入排序（Insertion Sort）

插入排序算法是一种比较排序算法；
其基本过程和选择排序类似，都将原序列看成前后两个部分：
- 前面：已排序部分(初始长度为1)；
- 后面：未排序部分(初始长度为nums.len()-1)；
不同之处在于遍历操作时，将后面未排序部分的最前面元素插入(Insert)到前面部分的合适位置；
每次插入时，插入点后面还有已排序的元素，则需要将其这些都后移一位；

算法描述

将待排序数组分为前后两个部分:
- 前面: 已排序部分;
- 后面: 未排序部分;
开始已排序部分长度为1, 未排序部分长度为nums.len()-1;
将未排序部分的头元素插入到前面已排序部分的正确位置(按大小顺序). 插入时，要将已排序部分插入点后面的元素依次往后移1位;
重复步骤3, 当所有未排序部分都插入到已排序部分后, 排序完成;

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/// # 插入排序
pub fn insert_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd + Copy + Clone
{
    for i in 1..nums.len() {
        let mut j = i;
        let n = nums[i];               // `未排序部分`头元素
        while j > 0 && nums[j-1] > n { // 从后往前将`已排序部分`中大于未排序部分头元素的元素
            nums[j] = nums[j-1];       // 后移动一位
            j -= 1;
        }
        nums[j] = n;                   // 将头元素插入到正确位置
    }
}

算法分析

插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序）；
在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

高级比较排序算法

希尔排序（Shell Sort）

ShellSort是第一个突破$O(n^2)$的排序算法，1959年由Shell发明；
是简单插入排序的改进版，与插入排序的不同之处在于，它会优先比较距离较远的元素；
希尔排序又叫缩小增量排序；

算法描述

先将整个待排序的序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/// # 希尔排序 
pub fn shell_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd + Copy
{
    // 带间隔的插入排序
    fn _insert_sort_with_gap<T: PartialOrd + Copy>(nums: &mut Vec<T>, start: usize, gap: usize) {
        for i in (start+gap..nums.len()).step_by(gap) {
            let mut j = i;
            let n = nums[i];               // `未排序部分`头元素
            while j >= gap && nums[j-gap] > n { // 从后往前将`已排序部分`中大于未排序部分头元素的元素
                nums[j] = nums[j-gap];       // 后移动gap位
                j -= gap;
            }
            nums[j] = n;                   // 将头元素插入到正确位置
        }
    }

    let mut gap = nums.len() / 2;
    while gap > 0 {
        for start in 0..gap {
            _insert_sort_with_gap(nums, start, gap);
        }
        gap /= 2;
    }
}

算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的。

归并排序（Merge Sort）

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

算法描述

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

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/// # 归并排序
pub fn merge_sort<T>(nums: &mut Vec<T>) 
    where T: PartialOrd + Copy + Clone
{
    // 将数组左右两个有序的部分合并, 使整体有序
    fn _merge<T>(nums: &mut Vec<T>, start: usize, mid: usize, end: usize)
         where T: PartialOrd + Copy + Clone
    {
        let nums1 = nums[start..mid].iter().cloned().collect::<Vec<_>>();
        let nums2 = nums[mid..end].iter().cloned().collect::<Vec<_>>();
        let (mut l, mut r) = (0, 0);
        while l < nums1.len() || r < nums2.len() {
            if r == nums2.len() || (l < nums1.len() && nums1[l] < nums2[r]) {
                nums[start+l+r] = nums1[l];
                l += 1;
            } else {
                nums[start+l+r] = nums2[r];
                r += 1;
            }
        }
    }

    // 递归归并排序
    fn _merge_sort<T>(nums: &mut Vec<T>, start: usize, end: usize)
         where T: PartialOrd + Copy + Clone
    {
        if start + 1 >= end {
            return;
        }
        let m = (start + end ) / 2;
        _merge_sort(nums, start, m);
        _merge_sort(nums, m, end);
        _merge(nums, start, m, end);
    }

    _merge_sort(nums, 0, nums.len())
}

算法分析

归并排序是一种稳定的排序方法。
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。
代价是需要额外的内存空间；

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

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

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pub fn quick_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd
{
    // 将nums划分为前后两个部分, 使前一部分都小于后一部分, 返回划分点
    fn partition<T: PartialOrd>(nums: &mut [T]) -> usize {
        let mut m = 0;              // 划分点
        let p = nums.len() - 1;     // 基准元素下标
        for i in 0..p {             // 依次遍历所有非基准元素
            if nums[i] <= nums[p] { // 如果当前元素<基准元素
                nums.swap(i, m);    // 将其和划分点元素交换
                m += 1;             // 往后移动划分点
            }
        }
        nums.swap(m, p);            // 最后, 将基准元素和划分点元素交换
        m                           // 返回划分点
    }

    // 递归快排
    fn _quick_sort<T: PartialOrd>(nums: &mut [T]) {
        if nums.len() < 2 {
            return;
        }
        let m = partition(nums);        // 将nums划分为前后两部分
        _quick_sort(&mut nums[..m]);    // 
        _quick_sort(&mut nums[m+1..]);  //
    }

    _quick_sort(&mut nums[..]);
}

堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆(heap)的性质:
- 堆是一个完全二叉树；
- 每个非叶子结点值均大于(大顶堆)/小于(小顶堆)其左右子节点值；
- 根节点为所有节点中的最大值(大顶堆)/最小值(小顶堆)；

算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/// # 堆排序
pub fn heap_sort<T>(nums: &mut Vec<T>)
    where T: PartialOrd
{
    // 以nums[top]为顶调整为堆
    fn heapify<T: PartialOrd>(nums: &mut [T], top: usize) {
        let mut m = top;
        let (l, r) = (2 * top + 1, 2 * top + 2);
        if l < nums.len() && nums[l] >= nums[m] {
            m = l;
        }
        if r < nums.len() && nums[r] >= nums[m] {
            m = r;
        }
        if m != top {
            nums.swap(m, top);
            heapify(nums, m);
        }
    }

    // 从最后一个非叶子节点开始, 往上依次调整所有以该节点为根的子树，使之成为大顶堆
    for i in (0..nums.len()/2).rev() {
        heapify(&mut nums[..], i);
    }

    // 依次取出堆顶元素, 和尾部元素交换
    for i in (0..nums.len()).rev() {
        nums.swap(0, i);
        heapify(&mut nums[..i], 0)
    }
}

非比较排序

计数排序（Counting Sort）

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

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/// 计数排序
pub fn count_sort(nums: &mut Vec<i32>) {
    if nums.len() == 0 {
        return;
    }
    let mi = *nums.iter().min().unwrap();
    let ma = *nums.iter().max().unwrap();
    let mut count = vec![0; (ma - mi + 1) as usize];
    // 统计每个数字出现的次数
    for n in nums.clone() {
        count[(n-mi) as usize] += 1;
    }
    // 统计每个数字出现的次数累加值
    for i in 1..count.len() {
        count[i] += count[i-1];
    }
    // 按累加值重新排序
    for n in nums.clone() {
        nums[count[(n - mi) as usize]-1] = n;
        count[(n-mi) as usize] -= 1;
    }
}

算法分析

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

桶排序（Bucket Sort）

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

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/// # 桶排序
/// ## 基本思想
/// - 计数排序的变种
/// 1. 桶是一个二级数组;
/// 2. 通过一个映射函数, 先将待排序序列中的各个元素映射到不同的桶中;
/// 3. 然后再分别对桶中的元素进行排序;
/// 4. 最后依次将各个桶中的元素合并, 得到完整有序的序列;
pub fn bucket_sort(nums: &mut Vec<i32>) {
    if nums.len() == 0 {
        return;
    }
    let l = nums.len();
    let (mi, ma) = (*nums.iter().min().unwrap(), *nums.iter().max().unwrap());  
    if mi == ma {  
        // 所有元素大小相等, 则不用排序
        return;  
    }
    // 分配桶空间
    let mut buckets = vec![Vec::<i32>::new(); l+1];
    // 分桶, 将nums各个元素分到相应的桶中
    for &n in nums.iter() {
        let i = ((n - mi) as usize) * l / ((ma - mi) as usize);
        buckets[i].push(n);
    }
    // 将各桶中元素排序, 然后按顺序放回原数组
    let mut i = 0;
    for mut b in buckets {
        b.sort();
        for n in b {
            nums[i] = n;
            i += 1;
        }
    }
}

算法分析

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

基数排序（Radix Sort）

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

算法描述

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

代码实现

算法分析

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

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

排序算法

相关文章：