插入排序：
详细算法描述
整理插入排序算法描述如下：
枚举序列中第2~n个元素。
当枚举元素i时，前i-1个元素已经有序。将第i个元素插入到前i-1个元素的有序序列中，形成长度为i的有序序列。
枚举过程结束后，整个序列有序。
所以，我们总结一下插入操作的算法描述：
假设序列1~(i-1)已经有序, 从i到1枚举分界线的下标j;
如果分界线前面的元素a[j-1]大于x，说明a[j-1]应该在分界线后面。所以将a[j-1]移动到a[j]，分界线前移变成j-1。
如果分界线前面没有元素（j=1），就将x放在数组第1位。否则如果碰到一个j-1号元素小于等于x，说明分界线位置正确，就将x插到j位。
完整代码：
#include <bits/stdc++.h> #define N 1550 using namespace std; int a[N], n; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; // 插入排序 for (int i = 2; i <= n; ++i) { // 按照第2个到第n个的顺序依次插入 int j, x = a[i]; // 先将i号元素用临时变量保存防止被修改。 // 插入过程，目的是空出分界线位置j，使得所有<j的部分<=x，所有>j的部分>x。 // 循环维持条件，j>1，并且j前面的元素>x。 for (j = i; j > 1 && a[j - 1] > x; --j) { // 满足循环条件，相当于分界线应向前移， // 分界线向前移，就等于将分界线前面>x的元素向后移 a[j] = a[j - 1]; } // 找到分界线位置，插入待插入元素x a[j] = x; } // 输出 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; return 0; }
快速排序：
快速排序的基本思想：
当需要将1到n的n个数排序时，我们通过分解，将该问题分解为两个将n/2个数排序的子问题;
在每个子问题中，我们继续分解，直到最后子问题长度为1;
此时，整个序列就完成排序了。
所以该算法的总复杂度变成了n^2/4 + 2nn2/4+2n。可以发现，在该算法中，多分解了一层，而复杂度也进一步减少了。
由此我们可以产生一个感觉，分解得越复杂度越小。所以，我们完全可以进一步分解，直到最后每个单位排序的长度为1。
任意长度为n的序列排序
当然快速排序也可用来给任意n个数的序列排序。但是与和1~n排序不同的是，对于任意n个数的序列，我们在划分子段的时候并不能很容易找到整个序列的“中位数”。所以只能在序列中任意取一个数。比如
取整个序列中最左边的数。
取整个序列中最右边的数。
在整个序列中随机一个位置并取该位置上的数。
都是常见的取数策略。
但由于不能保证每次取的数字都刚好是中位数，所以每次划分时也不能保证左边子段长度和右边子段长度非常平均。如果“不幸”选到不合适的数（比如整个子段中最小的数或最大的数），整个算法的效率会降低很多。
在此，我们详细描述一下给任意n个数排序的快速排序算法：
假设我们要对数组a[1..n]排序。初始化区间[1..n]。
令l和r分别为当前区间的左右端点。下面假设我们对l到r子段内的数字进行划分。取pivot = a[l]为分界线，将<pivot的数字移到左边，>pivot的数字移到右边，然后将pivot放在中间。假设pivot的位置是k。
如果左边区间[l..k-1]长度大于1，则对于新的区间[l..k-1]，重复调用上面的过程。
如果右边区间[k+1..r]长度大于1，则设置新的区间[k+1, r]，重复调用上面的过程。
当整个过程结束以后，整个序列排序完毕。
递归函数实现快速排序：
// 该代码参考 https://www.geeksforgeeks.org/quick-sort/ #include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N]; void quick_sort(int l, int r) { // l和r分别代表当前排序子段在原序列中左右端点的位置 // 设置最右边的数为分界线 int pivot = a[r]; int k; /* 此处省略了元素移动和确定分界线新位置k的过程 */ if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1，排序 if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1，排序 // 上面的过程结束后，到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作 // 保证了左子段中的元素都小于等于分界线，右子段中的元素都大于分界线。所以整个序列也是有序的。 } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 快速排序 quick_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
快速排序完整代码：
// 该代码参考 https://www.geeksforgeeks.org/quick-sort/ #include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N]; void quick_sort(int l, int r) { // 设置最右边的数为分界线 int pivot = a[r]; // 元素移动 int k = l - 1; for (int j = l; j < r; ++j) if (a[j] < pivot) swap(a[j], a[++k]); swap(a[r], a[++k]); if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1，排序 if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1，排序 // 上面的过程结束后，到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作 // 保证了左子段中的元素都小于等于分界线，右子段中的元素都大于分界线。所以整个序列也是有序的。 } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 快速排序 quick_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
复杂度分析
空间复杂度
首先该算法的空间复杂度是O(n)O(n)，具体来说，在整个排序过程中，元素的移动都在原始数组中进行。所以快速排序是一种原地排序算法。
时间复杂度
可以看出，在「详细算法描述」中，我们的算法分为若干层。每一层中都是分治法的三个步骤：我们首先进行问题拆分，然后进入下一层，下一层的问题解决后，我们返回这一层进行子问题解的合并。
我们首先分析对1~n的n个数字进行快速排序的情况。
在每一层中，问题拆分的复杂度是O(n)O(n)，因为我们移动数组元素的时候，需要将每个子段扫一遍。那么把所有层的子段一起看，就相当于在每一层都把整个序列完整扫了一遍。对于子段解的合并，其复杂度是O(1)O(1)，因为有分界线的存在，当我们把左边和右边都排好序后，它们和分界线元素一起天然形成了原序列的完整排序。
那么一共有多少层呢？因为每次我们都知道当前子段的中位数，所以可以保证每次划分，两个字段长度比较平衡，所以下一层子段的长度都比上一层减少了一半，直到长度为1算法停止。所以整个算法有\log nlogn层。
那么我们分析出在这种情况下，算法的复杂度是O(n\log n)O(nlogn)。这样，在1秒之内，计算机能非常轻松地排序10^6106及以上的数据。
但对于任意n个数的排序，每次划分情况取决于选取的分界线情况。如果每次分界线刚好取到最小值或者最大值，会导致划分时所有数字都会移动到同一边，整个算法的复杂度也会下降为O(n^2)O(n2)。如下图：
我们很容易想到两种尽量避免出现这种情况的方法：
在排序之前，先把整个数组随机打乱顺序。
在选取分界线时，与之前固定选取某个位置的方法相比，我们换成随机选择分界线的位置。
这两种方法都能极大概率避免上面提到的极端情况的发生。
分治思想：
快速排序用到的一个很重要的思想就是分治思想，也是分治法运用在排序中的很重要的实例。
分治思想是一种“分而治之”的思想，反应在解决问题当中，就是将一个复杂问题不断分解为规模更小、更容易解决的问题，从而提升解决问题的效率。而分治法就是基于分治思想得到的解决问题的方法，它分为下面三个步骤：
问题的拆分。例如在快速排序中，我们以某个元素为分界线，将待排序的数字分为两部分。
解决子问题。例如在快速排序中，如果子问题的规模为1，我们就直接解决它，否则，我们就使用和划分主问题同样的办法继续划分子问题直到子问题规模达到很容易直接解决为止。
合并子问题的解。例如在快速排序中，我们将左边右边分别排序后，将前后排好序的部分与中间的分界线连接，形成主问题的解。
分治思想在算法领域有非常广泛的应用，在很多分解和合并都非常容易的问题上，分治法都能够提升其算法效率。
总结
快速排序是一种基于分治法的排序。其基本思想在于固定一个分界线，将整个序列按照小于分界线和大于分界线划分，然后再分别对划分好的子段进行排序。
快速排序的时间复杂度在理想情况下是O(n \log n)O(nlogn)，但如果选取分界线每次都是子段中的最大值或最小值的话，时间复杂度可能会退化到O(n^2)O(n2)。在内存使用上，因为整个移动过程都在原数组中进行的，所以属于原地排序。
sort函数是C++标准模板库（STL）中一种对快速排序的优化实现，可以通过传入头指针、尾指针和比较函数来对数组中的对象进行排序。
快速排序示例：
将数组{2, 3, 1, 5, 4}从小到大排列。
不使用sort函数
将「整体框架」和「移动元素」进行合并，我们得到快速排序完整代码：
// 该代码参考 https://www.geeksforgeeks.org/quick-sort/ #include <bits/stdc++.h> #define N 100010 using namespace std; int n; int a[N]; void quick_sort(int l, int r) { // 设置最右边的数为分界线 int pivot = a[r]; // 元素移动 int k = l - 1; for (int j = l; j < r; ++j) if (a[j] < pivot) swap(a[j], a[++k]); swap(a[r], a[++k]); if (l < k - 1) quick_sort(l, k - 1); // 如果序列的分界线左边的子段长度>1，排序 if (k + 1 < r) quick_sort(k + 1, r); // 如果序列的分界线右边的子段长度>1，排序 // 上面的过程结束后，到这里左子段和右子段已经分别排好序。又因为确定分界线以后的移动操作 // 保证了左子段中的元素都小于等于分界线，右子段中的元素都大于分界线。所以整个序列也是有序的。 } int main() { // 输入 scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 快速排序 quick_sort(1, n); // 输出 for (int i = 1; i <= n; ++i) printf("%d ", a[i]); return 0; }
使用sort函数
sort函数有三个参数，分别为头指针、尾指针和比较函数，其中如果排序对象定义了小于号的话，比较函数可省略。例如对于一个长为n的数组排序：
#include <bits/stdc++.h> using namespace std; int a[10] = {2, 3, 1, 5, 4}; int n = 5; int main() { sort(a, a + n); //sort函数的两个参数，头指针和尾指针 for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
例题：
