排序算法总结

概述

直接插入排序

算法思想

每次将一个待排序的记录插入到已排序好的序列中。

(49) 38 65 97 76 13 27 49
(38 49) 65 97 76 13 27 49
(38 49 65) 97 76 13 27 49
(38 49 65 97) 76 13 27 49
(38 49 65 76 97) 13 27 49
(13 38 49 65 76 97) 27 49
(13 27 38 49 65 76 97) 49
(13 27 38 49 49 65 76 97)

()表示已排好序的部分

代码实现

//直接插入排序
template <typename T>
class Insertion {
public:
    static void sort(vector<T> &nums);
};

template <typename T>
void Insertion<T>::sort(vector<T> &nums) {
    //每次选一个未排序的元素
    for (int i = 1; i < nums.size(); i++) {
        //从后往前，依次检查前面已排序好的元素
        for (int j = i-1; j >= 0 && nums[j] > nums[j+1]; j--) {
            //与待排序的元素对比，如果逆序，则交换
            swap(nums[j], nums[j+1]);
        }
    }
}

性能分析

空间复杂度： $O(1)$
时间复杂度
- 最好时间复杂度（全部有序）：$O(n)$
  
  共 $n-1$ 趟，每趟只需比对一次关键字，不用移动元素。
- 最坏时间复杂度（全部逆序）：$O(n^2)$
  
  共 $n-1$ 趟，每趟（如第 $i$ 趟）对比 $i$ 次，移动 $i$ 次。
- 平均时间复杂度：$O(n^2)$
稳定性

稳定。每次插入元素都是从前往后比较移动，所以不会出现相同元素相对位置变化。

适用性：顺序表和链表

希尔排序

算法思想

希尔排序是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

每轮把记录按下标的一定增量分组 $L[i, i+d, i+2d,…,i+kd]$ ，对每组直接插入排序；
逐渐减少增量，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

49 38 65 13 76 13 27 57 （d = 4）
49 13 27 13 76 38 65 57 （d = 2）
27 13 49 13 65 38 76 57 （d = 1）
13 13 27 38 49 57 65 76

代码实现

//希尔排序
template <typename T>
class Shell {
public:
    static void sort(vector<T> &nums);
};

template <typename T>
void Shell<T>::sort(vector<T> &nums) {
    int N = nums.size();
    //增量d初始为N/2，每次减一半，直到为1
    for (int d = N/2; d >= 1; d /= 2) {
        //增量为d的直接插入排序
        //[0,d-1]在所属子表中已排序好，从d开始，选一个未排序的元素
        for (int i = d; i < N; i++) {
            //[..., i-2d, i-d]已排好序
            //从后往前，依次检测前面已排序好的元素
            for (int j = i-d; j >= 0 && nums[j] > nums[j+d]; j -= d) {
                //与待排序的元素对比，如果逆序，则交换
                swap(nums[j], nums[j+d]);
            }
        }
    }
}

性能分析

空间复杂度： $O(1)$
时间复杂度
- 最坏时间复杂度 $O(n^2)$
- 最好时间复杂度（全部有序）：$O(n)$
- 当n在某个特定范围时，可达 $O(n^{1.3})$
稳定性

不稳定。如果两相同元素划分到不同子表，可能会改变相对位置。
适用性：顺序表

冒泡排序

算法思想

每趟从前往后（或从后往前）两两相邻元素比较，如逆序，则交换
每趟可冒泡出最大的元素到最后

(1)
49 38 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 76 97 13 27 49
38 49 65 76 13 97 27 49
38 49 65 76 13 27 97 49
38 49 65 76 13 27 49 (97)

(2)
38 49 65 76 13 27 49 (97)
38 49 65 76 13 27 49 (97)
…
38 49 65 13 27 49 (76 97)

……

(n-1)
(13 27 38 49 49 65 76 97)

代码实现

//冒泡排序
template <typename T>
class Bubble {
public:
    static void sort(vector<T> &nums);
};

template <typename T>
void Bubble<T>::sort(vector<T> &nums) {
    //冒泡N-1趟
    for (int i = 0; i < nums.size()-1; i++) {
        bool flag = false; //表示发生过交换
        //第i趟冒泡范围[0,N-i-1]，后i个已经排序好
        for (int j = 0; j < nums.size()-i-1; j++) {
            //逆序，则交换
            if (nums[j] > nums[j+1]) {
                swap(nums[j], nums[j+1]);
                flag = true;
            }
        }
        //如该趟未发生交换，则已全部有序，直接返回
        if (!flag) {
            return;
        }
    }
}

性能分析

空间复杂度： $O(1)$
时间复杂度
- 最好时间复杂度（全部有序）：$O(n)$
  
  只需冒泡一趟，比较 $n$ 次，交换 $0$ 次，时间复杂度为$O(n)$
- 最坏时间复杂度（全部逆序）： $O(n^2)$
  - 共冒泡 $n-1$ 趟
  - 第 $i$ 趟，比较 $n-i-1$ 次，交换 $n-i-1$ 次
  - 比较次数 = 交换次数 = $(n-1)+(n-2)+…+1 =n(n-1)/2$
  - 时间复杂度 $O(n^2)$
- 平均时间复杂度： $O(n^2)$
稳定性

稳定。只在相邻逆序时交换，不改变相同元素的相对位置。
适用性：顺序表和链表

快速排序

算法思想

每趟排序确定一个元素 $x$ 的最终位置，将数据分为$x$ 两个部分。再对这两个部分递归进行排序。

(1)：确定49的位置，与49比较，左边部分小于49，右边部分大于49

49	38	65	97	76	13	27	49
49
	38	65	97	76	13	27	49
low							high
49
	38	65	97	76	13	27	49
low						high
						49
27	38	65	97	76	13		49
low						high
						49
27	38	65	97	76	13		49
	low					high
						49
27	38	65	97	76	13		49
		low				high
		49
27	38		97	76	13	65	49
		low				high
		49
27	38		97	76	13	65	49
		low			high
					49
27	38	13	97	76		65	49
		low			high
					49
27	38	13	97	76		65	49
			low		high
			49
27	38	13		76	97	65	49
			low		high
			49
27	38	13		76	97	65	49
			low	high
			49
27	38	13		76	97	65	49
			l=h
27	38	13	49	76	97	65	49
		<49	l=h	>49

再分别对左右两边 $[27, 38, 13]$ 、 $[76, 97, 65, 49]$ 进行递归排序。

代码实现

//快速排序
template <typename T>
class Quick {
public:
    static void sort(vector<T> &nums);

private:
    static void sort(vector<T> &nums, int low, int high);
    static int partition(vector<T> &nums, int low, int high);
};

//排序函数
template <typename T>
void Quick<T>::sort(vector<T> &nums) {
    sort(nums, 0, nums.size()-1);
}

//对[low, high]部分排序
template <typename T>
void Quick<T>::sort(vector<T> &nums, int low, int high) {
    if (low >= high) {
        return; //跳出递归
    }

    int pivot_pos = partition(nums, low, high); //切分
    sort(nums, low, pivot_pos-1); //排序左边部分
    sort(nums, pivot_pos+1, high); //排序右边部分
}

//快速排序划分
template <typename T>
int Quick<T>::partition(vector<T> &nums, int low, int high) {
    T pivot = nums[low]; //第一个元素为枢轴
    
    //low和high比较交换，直到 low >= high
    while (low < high) {
        //high左移，直到第一个小于pivot的出现
        while (nums[high] >= pivot && low < high) {
            high--;
        }
        nums[low] = nums[high]; //小于pivot的high与low交换
        
        //low右移，直到第一个大于pivot的出现
        while (nums[low] <= pivot && low < high) {
            low++;
        }
        nums[high] = nums[low]; //大于pivot的low与high交换
    }
    
    //pivot填入中间位置
    nums[low] = pivot;
    return low;
}

性能分析

空间复杂度

需要调用递归栈，相当于分别用n个枢轴建立一个二叉树，空间复杂度即为递归层数，也就是二叉树高度。
- 最好空间复杂度：$O(log_2n)$
  
  枢轴划分均匀，二叉树为完全二叉树，高度为 $log_2n$
- 最坏时间复杂度 $O(n)$
  
  枢轴划分极不均匀，如每个都划分成只有大于pivot或小于pivot，二叉树每个节点的度都为1，高度为 $n$
时间复杂度

时间复杂度为 $O(n*递归层数)$
- 最好时间复杂度（划分均匀）：$O(nlog_2N)$
- 最坏时间复杂度（划分极不均匀）： $O(n^2)$
- 平均时间复杂度： $O(nlog_2N)$
稳定性

不稳定。交换时，可能把相对位置更后的元素交换到更前的位置。

| 49 | 38 | 65 | 16 | 76 | 13 | 57 | 16 |
|——|——|——|:—-|:—-|:—-|:—-|:—————|
| 49 | | | | | | | |
| | 38 | 65 | 16 | 76 | 13 | 27 |16|
| low| | | | | | | high |
| | | | | | | | 49 |
| 16 | 38 | 65 | 16 | 76 | 13 | 27 | |
| low| | | | | | | high |
适用性：顺序表

简单选择排序

算法思想

最简单的一种排序方法。每次找到最小的那个元素，和第一个元素交换。

49 38 65 97 76 13 27 49
(13) 38 65 97 76 49 27 49
(13 27) 65 97 76 49 38 49
(13 27 38) 97 76 49 65 49
(13 27 38 49) 76 97 65 49
(13 27 38 49 49) 97 65 76
(13 27 38 49 49 65) 97 76
(13 27 38 49 49 65 76) 97
(13 27 38 49 49 65 76 97)

代码实现

//简单选择排序
template <typename T>
class Selection {
public:
    static void sort(vector<T> &nums);
};

template <typename T>
void Selection<T>::sort(vector<T> &nums) {
    for (int i = 0; i < nums.size()-1; i++) {
        int min_pos = i;
        for (int j = i; j < nums.size(); j++) {
            if (nums[j] < nums[min_pos]) {
                min_pos = j;
            }
        }
        swap(nums[i], nums[min_pos]);
    }
}

性能分析

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

无论是有序、无序、乱序，都需要 $n-1$ 趟选出最小值，第i趟选最小值都需要对比 $n-i$ 次。即 $(n-1)+(n-2)+…+1 = n(n-1)/2$
稳定性

不稳定。交换时，可能把相对位置更前的元素换到后面去。

2 2 1
1 2 2
1 2 2
适用性：顺序表和链表

堆排序

算法思想

先建立大根堆/小根堆，再基于大根堆/小根堆进行排序。

二叉树的顺序存储

完全二叉树可以顺序存储为序列，如下面序列和完全二叉树的对应

t[0]	t[1]	t[2]	t[3]	t[4]	t[5]	t[6]	t[7]	t[8]	t[9]
	1	2	3	4	5	6	7	8	9

graph TD
    A((1))
    B((2))
    C((3))
    D((4))
    E((5))
    F((6))
    G((7))
    H((8))
    I((9))

    A---B;
    A---C;
    B---D;
    B---E;
    C---F;
    C---G;
    D---H;
    D---I;

对于共有 $n$ 个结点完全二叉树，序号为 $i$ 结点

$i$ 的左孩子： $2i$
$i$ 的右孩子： $2i+1$
$i$ 的父结点： $\lfloor i/2 \rfloor$
$i$ 所在层次： $\lfloor log_2(n+1) \rfloor$
$i$ 是否有左孩子： $2i \le n?$
$i$ 是否有右孩子： $2i+1 \le n?$
$i$ 是否是叶子结点： $i \ge \lfloor n/2 \rfloor?$

堆的定义

堆分为大根堆/小根堆，即更大的为根/更小的为根

大根堆：根 >= 左、右

| | 87 | 45 | 78 | 32 | 17 | 65 | 53 | 9 |
|—-|—-|—-|—-|:—|:—|:—|:—|:—|

<pre class="mermaid">    graph TD
    A((87))
    B((45))
    C((78))
    D((32))
    E((17))
    F((65))
    G((53))
    H((9))

    A---B;
    A---C;
    B---D;
    B---E;
    C---F;
    C---G;
    D---H;</pre>

小根堆：根 <= 左、右

| | 9 | 45 | 17 | 65 | 53 | 32 | 87 | 78 |
|—-|—-|—-|—-|:—|:—|:—|:—|:—|

<pre class="mermaid">    graph TD
    A((9))
    B((45))
    C((17))
    D((65))
    E((53))
    F((32))
    G((87))
    H((78))

    A---B;
    A---C;
    B---D;
    B---E;
    C---F;
    C---G;
    D---H;</pre>

堆的建立

以大根堆为例，

把所有的非叶子结点检查一遍，如果不满足大根堆要求，则进行调整。

排序

概述

直接插入排序

算法思想

代码实现

性能分析

希尔排序

算法思想

代码实现

性能分析

冒泡排序

算法思想

代码实现

性能分析

快速排序

算法思想

代码实现

性能分析

简单选择排序

算法思想

代码实现

性能分析

堆排序

算法思想

二叉树的顺序存储

堆的定义

堆的建立

基于堆进行排序

代码实现

性能分析

归并排序

算法思想

代码实现

性能分析

参考