常见排序算法的时间复杂度和空间复杂度及稳定性分析：
一、冒泡排序
我们接触的第一个排序算法想必就是冒泡排序了，一般常见的排序算法中最简单的也就是冒泡排序了，它的核心思想在于从前往后开始冒泡，逐一比较两个数的大小。
具体思路：比较相邻元素元素的大小，如果前一个比后一个大，就彼此交换位置，重复以上的步骤，最后将会得到一个升序的数组。
代码示例：
void BubbleSort(vector<int>& v) {
int len = v.size();
for (int i = 0; i < len - 1; ++i)
for (int j = 0; j < len - 1 - i; ++j)
if (v[j] > v[j + 1])
swap(v[j], v[j + 1]);
}
冒泡排序优化版
冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说。
假如数组原本就是有序，根本不需要排序，它仍然是双层循环一个不少的把数据遍历，这其实就是做了没必要做的事情，属于浪费资源。
针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。
void BubbleSort_orderly(vector<int>& v) {
int len = v.size();
bool orderly = false;
for (int i = 0; i < len - 1 && !orderly; ++i) {
orderly = true;
for (int j = 0; j < len - 1 - i; ++j) {
if (v[j] > v[j + 1]) { // 从小到大
orderly = false; // 发生交换则仍非有序
swap(v[j], v[j + 1]);
}
}
}
}
二、快速排序
要说排序算法中用的最多的就要属快速排序了，它的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。
快速排序的思想非常重要，大家一定要理解。此外，快速排序的时间复杂度是O(n log n)，空间复杂度为 O(1)。但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，需要切分 n – 1 次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了 O(n^2)，当然极端情况出现的概率也是比较低的。
代码示例：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
三、归并排序
归并算法的核心思想也是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。
具体思路：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。归并排序的核心思想是分治，分而治之，将一个大问题分解成无数的小问题进行处理，处理之后再合并，这里我们采用递归来实现：
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
四、堆排序
堆是是一棵完全二叉树，堆上面的每个节点满足父节点的值大于子节点。若根节点的值比所有节点的值都大， 称为最大堆；根节点的值比所有节点的值都小， 称为最小堆；
具体思路：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1和序列重新构造成一个堆，这也就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。?
// 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。
void max_heapify(int arr[], int start, int end) {
int dad = start;
int son = dad * 2 + 1;
while (son <= end) {
if (son + 1 <= end && arr[son] < arr[son + 1])
son++;
if (arr[dad] > arr[son])
return;
else {
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
五、桶排序
桶排序将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。
具体思路：先设置一个定量的数组当作空桶子；寻访序列，并且把项目一个一个放到对应的桶子去；对每个不是空的桶子进行排序；从不是空的桶子里把项目再放回原来的序列中。
代码示例：
void insert_sort(vector<int>& arr) {
int n = arr.size();
int j = 0, cur = 0;
for (int i = 1; i < n; i++) {
cur = arr[i];
j = i - 1;
//进行比较，插入
while (j >= 0 && arr[j] > cur) {
arr[j + 1] = arr[j];
j--;
}
arr[j+1] = cur;
}
}
void bucket_sort(vector<int>& arr) {
if (arr.size() == 0) return;
int minvalue = arr[0];
int maxvalue = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] < minvalue) {
minvalue = arr[i]; // 输入数据的最小值
}
else if (arr[i] > maxvalue) {
maxvalue = arr[i]; // 输入数据的最大值
}
}
//桶进行初始化
int DEFAULT_BUCKET_SIZE = 5; // 桶的大小的默认为5
int bucketCount = (maxvalue - minvalue) / DEFAULT_BUCKET_SIZE + 1; //计算桶的数量
vector<vector<int>> buckets(bucketCount, vector<int>());
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.size(); i++) {
buckets[(arr[i] - minvalue) / DEFAULT_BUCKET_SIZE].push_back(arr[i]);
}
int index = 0;
for (int i = 0; i < buckets.size(); i++) {
insert_sort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}