四类（七种）排序算法总结

一、插入排序

基本思想：
每次将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。

基本操作——有序插入：

• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加；
• 起初，$a[0]$是长度为1的子序列。然后，逐一将$a[1]$至$a[n-1]$插入到有序子序列中。

基本操作——有序插入方法

• 在插入$a[i]$前，数组a的前半段（$a[0]$～$a[i-1]$）是有序段，后半段（$a[i]$～$a[n-1]$）是停留于输入次序的无序段；
• 插入$a[i]$使$a[0]$～$a[i]$有序，也就是要为$a[i]$找到有序位置$j$($0⩽j⩽i$)，将$a[i]$插入在$a[j]$的位置上。

1. 直接插入排序

基本思想：
  采用顺序查找法查找插入位置；
性能分析：
  算法的时间复杂度为$O(n^2)$，空间复杂度$O(1)$；
稳定性：
  稳定。

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	直接插入排序
* @param v: 待排序序列引用
*/
void insertSort(vector<int>& v)
{int temp;	// 辅助空间：用于记录每次要插入的元素值for (int i = 1; i < v.size(); i++)	// 认定v[0]已经有序，所以i从1开始{temp = v[i];int j;for (j = i - 1; j >= 0; j--)	// 在[0, i-1]中找temp应该插入的位置{if (v[j] > temp){v[j + 1] = v[j];	// 记录后移一位}else	// 说明v[0...j]的值都比temp小，无需再比{break;}}v[j + 1] = temp;	// j+1就是temp要插入的位置	}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 0,5,3,4,6,2 };cout << "排序前：" << endl;printVec(v);// 排序insertSort(v);cout << "排序后：" << endl;printVec(v);
}

2. 二分插入排序

基本思想：
  采用折半查找法查找插入位置；
性能分析：
  算法的时间复杂度为$O(n^2)$，空间复杂度$O(1)$；
稳定性：
  稳定。

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;/*
* @brief:	二分插入排序
* @param v: 待排序序列引用
*/
void BinsertSort(vector<int>& v)
{int temp;	// 辅助空间：用于记录每次要插入的元素值for (int i = 1; i < v.size(); i++)	// 认定v[0]已经有序，所以i从1开始{temp = v[i];// 利用二分法在[0, i-1]中找temp应该插入的位置int low = 0, high = i - 1;while (low <= high){	int mid = (low + high) / 2;if (v[mid] > temp){high = mid - 1;}else{low = mid + 1;}}	// low就是该插入的位置// 将[low, i-1]处的元素依次向后移动一位for (int j = i - 1; j >= low; j--){v[j + 1] = v[j];}v[low] = temp;	// low就是temp要插入的位置	}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序BinsertSort(v);cout << "排序后：" << endl;printVec(v);
}

3. 希尔排序

基本思想：
  先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序；
性能分析：
  算法的时间复杂度为$O(n^{1.3})$，空间复杂度$O(1)$；
稳定性：
  不稳定。

特点：

• 缩小增量
• 多遍插入排序

思路：

• 定义增量序列$D_k：D_M>D_{M-1}>...>D_1=1$
• 对每个$D_k$进行“$D_k-间隔$”插入排序（k=M, M-1, …1）

特点：

• 一次移动，移动位置较大，跳跃式地接近排序后的最终位置
• 最后一次只需要少量移动
• 增量序列必须时递减的，最后一个必须是1

注：关于 $D_k$ 如何选择还没有明确定义

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	希尔排序
* @param v: 待排序序列引用
*/
void ShellSort(vector<int>& v)
{int temp;						// 辅助空间int increment = v.size() / 2;	// 初始增量while (increment >= 1)	// 最后一步的插入排序增量一定是1{for (int i = increment; i < v.size(); i++){temp = v[i];int j;for (j = i - increment; j >= 0; j -= increment){if (v[j] > temp){v[j + increment] = v[j];	// 记录后移increment位}else	// 说明v[0...j]的值都比temp小，无需再比{break;}}v[j + increment] = temp;	// j+increment就是temp要插入的位置}increment /= 2;	// 更新缩小增量}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序ShellSort(v);cout << "排序后：" << endl;printVec(v);
}

• 比较希尔排序和直接插入排序的代码发现，二者的相似程度非常高，原因在于希尔排序就是每次以一定的增量 $increment$ 间隔对序列中的元素进行排序，让序列变得基本有序，当 $increment=1$ 时，最后一步就是直接插入排序，由于此刻序列已基本有序，最后一步的排序中需要交换位置的元素已经不多了；
• 速记方法：将直接插入排序代码中的 $1$ 用$increment$替换，并在最外层加上以 $increment$ 为条件的循环。

二、交换排序

基本思想：
  两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

1. 冒泡排序

基本思想：
  每趟不断将记录两两比较，并按“前小后大”规则交换；
性能分析：
  算法的时间复杂度为$O(n^2)$，空间复杂度$O(1)$；
稳定性：
  稳定。

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	冒泡排序
* @param v: 待排序序列引用
*/
void bubbleSort(vector<int>& v)
{int temp;	// 辅助空间int n = v.size();for (int i = 1; i < n; i++)	// 每次找出一个最大的，n个元素要比较n趟{for (int j = 0; j < n - i; j++){if (v[j] > v[j + 1])	// 比较相邻两个元素大小{// 交换元素temp = v[j];v[j] = v[j + 1];v[j + 1] = temp;}}	}
}/**
* @brief:	冒泡排序优化
* @param v: 待排序序列引用
*/
void bubbleSortOpt(vector<int>& v)
{int temp;int n = v.size();bool flag = true;	// 记录某一趟中是否交换了元素位置for (int i = 1; i < n && flag; i++){flag = false;	// 先将当前趟元素交换标记设为falsefor (int j = 0; j < n - i; j++){if (v[j] > v[j + 1])	// 比较相邻两个元素大小{// 交换元素temp = v[j + 1];v[j + 1] = v[j];v[j] = temp;flag = true;	// 发生了元素交换}}}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序// bubbleSort(v);bubbleSortOpt(v);cout << "排序后：" << endl;printVec(v);
}

2. 快速排序

基本思想：

• 任取一个元素（如：第一个）为中心（pivot：枢轴、中心点）；
• 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
• 对各子表重新选择中心元素并依此规则调整（递归思想）；
• 直到每个子表的元素只剩一个。

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

具体实现：
  选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。

每一趟子表的形成是采用从两头向中间交替式逼近法；
由于每趟中对各子表的操作都相似，可采用递归算法。

（枢轴）中间数：
  可以是第一个数、最后一个数、最中间一个数、任选一个数等。

性能分析：
  算法的时间复杂度为$O(nlogn)$，空间复杂度$O(logn)$（递归需要使用栈）；
稳定性：
  不稳定。

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	快速排序
* @param v: 待排序序列引用
*/
void quickSort(vector<int>& v, int start, int end)
{if (start >= end)return;int low = start, high = end;int pivot = v[low];	// 枢轴while (low < high){while (low < high && v[high] >= pivot)	// 将比枢轴小的放到左边high--;v[low] = v[high];while (low < high && v[low] <= pivot)	// 将比枢轴大的放到右边low++;v[high] = v[low];	// 将枢轴放置中间某个位置}v[low] = pivot;// 递归左右子表quickSort(v, start, low - 1);quickSort(v, low + 1, end);
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序quickSort(v, 0, v.size() - 1);cout << "排序后：" << endl;printVec(v);
}

三、选择排序

1. 简单选择排序

基本思想：
  在待排序的数据中选出最大（小）的元素放在其最终的位置。

基本操作：

• 首先通过 $n-1$ 次关键字比较，从 $n$ 个记录中找出关键字最小的记录，将它与第一个记录交换；
• 再通过 $n-2$ 次比较，从剩余的 $n-1$ 个记录中找出关键字次小的记录，将它与第二个记录交换；
• 重复上述操作，共进行 $n-1$ 趟排序后，排序结束。

性能分析：
  算法的时间复杂度为$O(n^2)$，空间复杂度$O(1)$；
稳定性：
  不稳定。

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	选择排序
* @param v: 待排序序列引用
*/
void selectSort(vector<int>& v)
{int temp;	// 辅助空间int n = v.size();for (int i = 0; i < n; i++){int minIdx = i;for (int j = minIdx + 1; j < n; j++)	// 找出[i...n-1]中最小元素对应index{if (v[j] < v[minIdx]){minIdx = j;	// 更新minIdx}}if (minIdx != i){// 交换v[i]和v[minIdx]temp = v[i];v[i] = v[minIdx];v[minIdx] = temp;}}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序selectSort(v);cout << "排序后：" << endl;printVec(v);
}

2. 堆排序

堆的定义：
若 $n$ 个元素的序列 {$a_1$, $a_2$, …, $a_n$} 满足
$\{\begin{array}{l}{a}_i⩽a_{2i}\\ a_i⩽a_{2i+1}\end{array}$ 或 $\{\begin{array}{l}{a}_i⩾a_{2i}\\ a_i⩾a_{2i+1}\end{array}$
则分别称该序列 {$a_1$, $a_2$, …, $a_n$} 为小根堆和大根堆。
从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子节点均小于（大于）它的孩子节点。

堆排序定义：
  若在输出堆顶的最小值（最大值）后，使得剩余 $n-1$ 个元素的序列重新又建成一个堆，则得到 $n$ 个元素的次小值（次大值）… 如此反复，便能得到一个有序序列，这个过程称之为堆排序。

实现堆排序需解决两个问题：

• 如何由一个无序序列建成一个堆？
• 如何在输出堆顶元素后，调整剩余元素为一个新的堆？

堆的调整——小根堆：

• 输出堆顶元素后，以堆中最后一个元素替代之；
• 然后将根节点值与左、右子树的根节点值进行比较，并与其中小者进行交换；
• 重复上述操作，直至叶子节点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。

堆的建立：

• 单节点的二叉树是堆；
• 在完全二叉树中所有以叶子节点（序号$i⩾n/2$）为根的子树是堆；
• 这样，只需依次将以序号为 $n/2,n/2-1,...,1$ 的节点为根的子树均调整为堆即可，即：对应由 $n$ 个元素组成的无序序列，“筛选”只需从第 $n/2$ 个元素开始。

性能分析：

• 初始堆化所需时间不超过$O(n)$；
• 排序阶段（不含初始堆化）
  一次重新堆化所需时间不超过$O(logn)$;
  $n-1$ 次循环所需时间不超过$O(nlogn)$；
  $$Tw(n)=O(n)+O(nlogn)=O(nlogn)$$

稳定性：
  不稳定。

#include <iostream>
#include <vector>
using namespace std;/*
* @brief:	将v[start~end]的记录调整为一个大顶堆
*			已知v[start~end]中的记录除v[start]外均满足堆的定义
* @param v: 待调整序列引用
*/
void heapAdjust(vector<int>& v, int start, int end)
{int temp = v[start];for (size_t j = 2 * start; j <= end; j *= 2)	// 沿关键字较大的孩子节点向下筛选{if (j < end && v[j] < v[j + 1])	// j:左孩子	j+1:右孩子{++j;	// 右孩子较大，将j增1}if (temp >= v[j]){break;	// temp的值比左右孩子值都大，不需要调整}v[start] = v[j];	// 将较大的孩子节点上调至父节点start = j;// j *= 2：继续对较大孩子节点进行调整}v[start] = temp;
}/*
* @brief:	堆排序
* @param v: 待排序序列引用
*/
void heapSort(vector<int>& v)
{int length = v.size() - 1;	// 完全二叉树、堆顶元素从1开始编号，所以我们对v// 这里减1是为了不考虑v[0]，只对v[1~length]排序// 初始堆化for (size_t i = length / 2; i > 0; i--){heapAdjust(v, i, length);}for (size_t i = length; i > 1; i--){// 将堆顶元素与最后一个元素交换int temp = v[1];v[1] = v[i];v[i] = temp;// 将v[1~i-1]再调整称大顶堆heapAdjust(v, 1, i - 1);}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 1; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 0,81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序heapSort(v);cout << "排序后：" << endl;printVec(v);
}

四、归并排序

基本思想：
  将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序，即：将两个位置相邻的有序子序列$R[l...m]$和$R[m+\mathrm{1...}n]$归并为一个有序序列$R[l...m]$。

性能分析：

• 时间效率：$O(nlogn)$;
• 空间效率：$O(n)$；

稳定性：
  稳定。

#include <iostream>
#include <vector>
using namespace std;/**
* @brief:		将有序序列vSrc[s...m]和vSrc[m+1...t]合并到vDst[s...t]
* @param vSrc:	源数组引用
* @param vDst:	目标数组引用
* @param s:		start index
* @param m:		'middle' index, s < m < t
* @param t:		end index
*/
void merge(vector<int>& vSrc, vector<int>& vDst, int s, int m, int t)
{int i = s, j = m + 1;int k = s;while (i <= m && j <= t){if (vSrc[i] < vSrc[j]){vDst[k++] = vSrc[i++];}else{vDst[k++] = vSrc[j++];}}while (i <= m){vDst[k++] = vSrc[i++];}while (j <= t){vDst[k++] = vSrc[j++];}	
}/*
* @brief:		归并排序，将vSrc[s...t]归并排序为vDst[s...t]
* @param vSrc:	待排序序列引用
* @param vDst:	排序结果序列引用
* @param s:		start index
* @param t:		end index
*/
void mergeSort(vector<int>& vSrc, vector<int>& vDst, int s, int t)
{if (s == t){vDst[s] = vSrc[s];return;}else{int m = (s + t) / 2;vector<int> vTemp(vSrc.size());mergeSort(vSrc, vTemp, s, m);mergeSort(vSrc, vTemp, m + 1, t);merge(vTemp, vDst, s, m, t);}
}/*
* @brief:	打印元素
* @param v: 待排序序列引用
*/
void printVec(vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << "\t";}cout << endl;
}int main(int argc, char* argv[])
{vector<int> v = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };cout << "排序前：" << endl;printVec(v);// 排序int length = v.size();vector<int> vRes(length);cout << "aa" << endl;mergeSort(v, vRes, 0, length - 1);cout << "排序后：" << endl;printVec(vRes);
}

五、各种排序方法比较

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(nlogn)$~$O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快速排序	$O(nlogn)$	$O(nlogn)$	$O(n^2)$	$O(logn)$~$O(n)$	不稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定

参考链接

青岛大学数据结构-王卓