《七大排序算法：原理、实现及性能剖析》

一、七大排序的实现、原理及性能剖析

1. 插入排序

1. 原理：
从待排序数组第 2 个元素开始，依次往前面插入到合适位置。当前插入数会与其前一个数进行比较，若小于比较数，则比较数后移，继续比较下一个数，直到找到插入书的位置。

2. 实现代码：

// 1. 插入排序
void InsertSort(int* arr, int sz)
{// 第二个元素开始往前插入int i;for (i = 1; i < sz; ++i){int cur = arr[i];  // 待插入数int cmpi = i - 1;  // 待比较数的下标// 找到插入的前一个位置while (cmpi >= 0){// 比较if (cur < arr[cmpi]){// 比较数后移arr[cmpi + 1] = arr[cmpi];// 下一个比较数--cmpi;}else{break;}}// 插入arr[cmpi + 1] = cur;}
}

3. 性能剖析：
（1）时间复杂度

最好情况：原数组有序，每个元素只需要比较一次即可，O(1)
最坏情况：原数组逆序，第二个元素比较 1 次，第三个元素比较 2 次，…，第 n 个元素比较 n-1 次，相加得出时间复杂度为 O(n²)

总结得出插入排序的时间复杂度为：O(n²)

（2）空间复杂度
由于没有开辟额外的空间，所以插入排序的空间复杂度为 O(1)

2. 希尔排序

1. 原理： 希尔排序是插入排序的优化版本，它的基础是插入排序。

首先，去一个间隔 gap，把数组中间隔为 gap 的数据分成一组，然后对它们进行插入排序。
gap 的初值可以为 gap / 2 或者 gap / 3 + 1，因为需要保证最后一次是间隔为 1 的插入排序。后续每次都按照上面的方法计算新的 gap。
当 gap 的值比较大的时候，大的数据可以快速跑到的前面，小的数据可以快速跑到后面。而且每进行一次间隔为 gap 的排序都会比之前更加接近有序。
当 gap 较小的时候，数组已经基本上有序，这时候进行插入排序的速度就非常快。

2. 实现代码：

// 2. 希尔排序
void ShellSort(int* arr, int sz)
{// 获得 gapint gap = sz;// 开始排序while (gap > 1){// 计算 gapgap = gap / 3 + 1;// 开始本次间隔为 gap 的插入排序int i;for (i = gap; i < sz; i += gap){int cur = arr[i];  // 待插入数int cmpi = i - gap;  // 待比较数下标// 寻找插入的前一个位置while (cmpi >= 0){// 比较if (cur < arr[cmpi]){// 比较数后移arr[cmpi + gap] = arr[cmpi];// 下一个比较数cmpi -= gap;}else{break;}}// 插入arr[cmpi + gap] = cur;}}
}

3. 性能剖析：
（1）时间复杂度
希尔排序的时间复杂度计算有点复杂，而且到现在也没有计算出一个确切的值。只需要记住希尔排序的时间复杂度在 O(n^1.3) 左右即可

（2）空间复杂度
没有开辟额外空间，希尔排序的空间复杂度为 O(1)

3. 选择排序

1. 原理：
选择排序的原理非常简单，如果排升序，遍历遍数组选出最小值把它放到第一个位置，以此类推，确定所有元素的位置。

2. 实现代码：

// 3. 选择排序
void SelectSort(int* arr, int sz)
{// 确定前 sz - 1 个数的位置int i;for (i = 0; i < sz - 1; ++i){// 最小值的下标int mini = i;// 找到最小值int j;for (j = i + 1; j < sz; ++j){if (arr[j] < arr[mini])mini = j;}// 交换if (mini != i)Swap(&arr[mini], &arr[i]);}
}

3. 性能剖析
（1）时间复杂度
选择排序不管在任何情况下的时间复杂度均为：O(N²)
因为，不管原数据如何排列，比较的总次数均不变

（2）空间复杂度
选择排序没有额外开辟空间，空间复杂度为:O(1)

4. 堆排序

1. 原理
堆排序只要认真学习了数据结构初阶的二叉树部分就很容易理解。堆排序，第一步就是建堆，建堆有两种方法：
（1）从数组第二个元素开始向上调整，一直到数组的最后一个元素
（2）从数组的倒数第一个非子叶节点开始向下调整，直到堆顶
一般使用向下调整建堆，因为向下调整建堆比向上调整建堆快，但是不影响最终堆排序的时间复杂度。

第二步就是仿照堆的删除，一直删除到堆只剩最后一个元素为止。如：建大堆排升序，每次删除当前堆中的最大值就跑到最后面去了。

总结：排升序建大堆，排降序建小堆

2. 实现代码：
下面的代码向上调整和向下调整均给出，本人推荐向下调整。

// 向上调整
void AdjustUp(int* arr, int child)
{// 找父亲int parent = (child - 1) / 2;// 开始调整while (child > 0){// 比较if (arr[child] > arr[parent]){// 交换Swap(&arr[child], &arr[parent]);// 下一组child = parent;parent = (parent - 1) / 2;}else{break;}}
}// 向下调整
void AdjustDown(int* arr, int sz, int parent)
{// 计算左孩子下标int child = parent * 2 + 1;// 开始调整while (child < sz){// 找大孩子if ((child + 1) < sz && arr[child + 1] > arr[child]){++child;}// 比较if (arr[child] > arr[parent]){// 交换Swap(&arr[child], &arr[parent]);// 下一组parent = child;child = child * 2 + 1;}else{break;}}
}// 4. 堆排序
void HeapSort(int* arr, int sz)
{ 向上调整//int i;//for (i = 1; i < sz; ++i)//{//	// 向上调整//	AdjustUp(arr, i);//}// 向下调整建堆int i;for (i = (sz - 2) / 2; i >= 0; --i){// 向下调整AdjustDown(arr, sz, i);}// 删除堆中元素，直到剩一个for (i = 1; i < sz; ++i){// 交换堆顶和堆底Swap(&arr[0], &arr[sz - i]);// 堆顶向下调整AdjustDown(arr, sz - i, 0);}
}

3. 性能剖析：
（1）时间复杂度
在这里插入图片描述

（2）空间复杂度
堆排序没有使用额外的空间，空间复杂度为：O(1)

5. 冒泡排序

1. 原理：
冒泡排序的原理是从第一个数开始，两两往后比较，如果排升序，那么前者大于后者就交换。这样一趟排序下来就可以确定最大值，然后最大值不参与比较，在来一趟就可以确定第二大的值，以此类推，就可以确定所有位置，然后排成升序。

此冒泡排序还可优化，如果本躺排序中没有进行数据的交换，那么证明数据已经有序，则跳出排序。

2. 实现代码：

// 5. 冒泡排序
void BubbleSort(int* arr, int sz)
{// 进行 sz-1 躺排序int i;for (i = 0; i < sz - 1; ++i){// 判断本躺排序是否进行交换int flag = 0;// 每趟排序比较 sz-i-1 次int j;for (j = 0; j < sz - i - 1; ++j){// 前后两两比较if (arr[j] > arr[j + 1]){// 交换Swap(&arr[j], &arr[j + 1]);flag = 1;}}// 判断if (!flag)break;}
}

3. 性能剖析
（1）时间复杂度

最好情况：当数据已经有序，第一轮比较之后就退出排序，时间复杂度为：O(1)
最坏情况：当数据逆序，需要进行 sz - 1 躺排序，并且每次比较都需要交换，时间复杂度为：O(n²)

总结：冒泡排序的时间复杂度为：O(n²)

（2）空间复杂度
冒泡排序没有开辟额外的空间，空间复杂度为：O(1)

6. 快速排序

1. 原理：

首先，选取一个数作为基准，一般选择最左边或者最右边，然后把小于基准的数排在前面，把大于基准的数排在后面，最后让基准在中间。
然后按照基准的位置，把数组分为两个区间，继续对这两个区间按照前面的方法排序，以此类推，直到区间只有一个元素或者非法为止。
由上述方法，可以联想到二叉树的前序遍历，先排序当前区间，然后再排序左区间，最后排序右区间。二叉树是直到空树，这里是直到区间只有一个元素或者区间不合法。
但是，当数据有序时，快速排序的时间复杂度会达到 O(N²)，而且空间复杂度也会达到 O(N)，因为每次递归只能去掉一个数，还剩下 N-1 个，还需要递归 N-1 次
有大佬想出了一个三数取中的办法，就是把当前排序的区间的最边上的加上最中间的一起三个元素选择值在中间的那个元素作为基准，这样可以保证快速排序在大多数情况下，接近理想的运行情况。
后面又有大佬发现，在区间元素为 10 左右的时候使用插入排序更加迅速。

当然，即使满足了上面的条件也不是最优的快速排序，但是也没差多少了，有兴趣的读者可以自己了解一下。（因为作者也就学了这么多）

2. 实现代码：

// 6. 快速排序
void QuickSort(int* arr, int left, int right)
{// 非法区间if (left >= right)return;// 递归判断if (right - left > 9){// 三数取中int mid = GetMidInThree(arr, left, right);if (mid != right)Swap(&arr[mid], &arr[left]);// 前后指针法int pre = left;int cur = left + 1;// 以左边为基准，进行本区间排序while (cur <= right){// cur 找小，且 ++pre != cur 交换if (arr[cur] < arr[left] && ++pre != cur){// 交换Swap(&arr[cur], &arr[pre]);}++cur;}// 基准归位Swap(&arr[left], &arr[pre]);// 继续排序左右区间QuickSort(arr, left, pre - 1);QuickSort(arr, pre + 1, right);}else{// 插入排序InsertSort(arr + left, right - left + 1);}
}

3. 性能剖析：
（1）时间复杂度
本来快速排序应该需要考虑一些最坏的情况，但是经过一些大佬的优化过后（如：三数取中等），快速排序几乎趋于最好的情况的排序速度，那我们就按照最好的情况来进行说明。
在这里插入图片描述

（2）空间复杂度
熟悉二叉树结构的读者应该能发现，快速排序的排序顺序好像二叉树的前序遍历，也就是深度优先，上图中也给出了数据的层数为 logN，所以最多递归 logN 层，也就是开辟 logN 个栈帧空间，所以快速排序的空间复杂度为：O(N*logN)

7. 快速排序（非递归）

1. 原理：

只要是递归都需要开辟栈帧空间，只要带排序的数据量太大，那么递归的层数就可能会深到栈溢出。
所以，一般涉及递归的算法都需要掌握其非递归方式。
快速排序的非递归需要借助数据结构栈来进行辅助。
首先排序给定的数组区间，然后把右区间压入栈中，左区间压入栈中，因为栈后进先出，所以顺序需要颠倒。
往后每次取出一个区间进行排序，都需要把它的左右区间压入栈中。
每次把区间压入栈中之前需要检查区间是否合法，如果不合法或者只有一个元素，那么就不做压栈处理。
直到栈为空，快速排序的非递归就完成了。

2. 代码实现：
C 语言没有栈，需要大家手搓一个。我前面栈和队列的博客里面讲述了如何实现一个栈，有兴趣的读者可以看看。

// 插入排序
void InsertSort(int* arr, int sz)
{int i;for (i = 1; i < sz; ++i){int cur = arr[i];  // 插入数int cmpi = i - 1;  // 比较数下标// 找到插入位置的前一个位置while (cmpi >= 0){// 比较if (cur < arr[cmpi]){// 比较数后移arr[cmpi + 1] = arr[cmpi];// 下一个比较数--cmpi;}else{break;}}// 插入arr[cmpi + 1] = cur;}
}// 三数取中
int GetMidInThree(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[left] > arr[right]){if (arr[mid] > arr[left])return left;else if (arr[mid] > arr[right])return mid;elsereturn right;}else{if (arr[mid] > arr[right])return right;else if (arr[mid] > arr[left])return mid;elsereturn left;}
}// 交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}// 1. 快速排序（非递归）
void QuickSort(int* arr, int left, int right)
{// 非法区间if (left >= right)return;// 创建栈Stack sk;// 初始化栈StackInit(&sk);// 最初排序区间入栈（先右后左，因为先进后出）StackPush(&sk, right);StackPush(&sk, left);// 开始快速排序while (!StackEmpty(&sk)){// 取出带排序区间left = StackTop(&sk);StackPop(&sk);right = StackTop(&sk);StackPop(&sk);// 递归判断if (right - left > 9){// 三数取中int mid = GetMidInThree(arr, left, right);if (mid != left)Swap(&arr[mid], &arr[left]);// 前后指针法int cur = left + 1;int pre = left;// 以左边为基准，开始本区间排序while (cur <= right){// cur 找小，且 ++pre != cur，交换if (arr[cur] < arr[left] && ++pre != cur)Swap(&arr[cur], &arr[pre]);++cur;}// 基准归位Swap(&arr[left], &arr[pre]);// 如果左右区间合法，那么入栈if (pre+1 < right){StackPush(&sk, right);StackPush(&sk, pre+1);}if (left < pre - 1){StackPush(&sk, pre - 1);StackPush(&sk, left);}}else{// 插入排序InsertSort(arr + left, right - left + 1);}}
}

3. 性能剖析
快速排序非递归形式和递归形式的性能差不多，时间复杂度和空间复杂度最好最坏情况均相同。只是递归需要开辟栈帧空间，而非递归不需要。

8. 归并排序

1. 原理：
如果说快速排序是把一个大区间不断地二分，那么归并排序就是把一个个小区间进行合并。

归并排序的思路和归并两个有序数组一样，把带排序区间从中间分成两个，然后按照归并两个有序数组一样进行归并。
但是左右区间并不有序，所以就需要按照上面的方法继续拆开左右区间然后归并，一直到区间不合法，或者区间只有一个元素时，停止。
然后递归返回，开始合并左右区间，因为当左右区间只有一个元素时，那必然符合有序条件，接着层层返回，每个子区间均有序。
最后完成整体归并

2. 代码如下：

// 归并
void _MergeSort(int* arr, int* tmp, int left, int right)
{// 非法区间if (left >= right)return;// 去中间，分区间int mid = (left + right) / 2;// 归并左右区间_MergeSort(arr, tmp, left, mid);_MergeSort(arr, tmp, mid + 1, right);// 合并左右区间int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int begin = left, end = right;// 合并到临时数组 tmpwhile (begin1 <= end1 && begin2 <= end2){// 比较if (arr[begin1] < arr[begin2])tmp[begin++] = arr[begin1++];elsetmp[begin++] = arr[begin2++];}// 接上剩下元素while (begin1 <= end1)tmp[begin++] = arr[begin1++];while (begin2 <= end2)tmp[begin++] = arr[begin2++];// 把归并后的结果拷贝回原数组begin = left;while (begin <= end){arr[begin] = tmp[begin];++begin;}
}// 2. 归并排序
void MergeSort(int* arr, int sz)
{// 申请临时数组int* tmp = (int*)malloc(sizeof(int) * sz);if (NULL == tmp){perror("MergeSort::malloc: ");return;}// 开始归并_MergeSort(arr, tmp, 0, sz - 1);// 释放临时数组free(tmp);
}

3. 性能分析
（1）时间复杂度
可以看到，归并排序每次都把区间均分成两份，如果元素个数为 N，那么递归高度就是 logN，每层都需要两两进行归并，也就相当于遍历了一遍整个数组，时间复杂度为 O(N)，那么总得时间复杂度就是 O(N*logN)

（2）空间复杂度
归并排序的递归最大深度为 logN，所以空间复杂度为：O(logN)

9. 归并排序（非递归）

1. 原理：

归并排序的递归可以直接转换为迭代，因为归并排序的递归方式是每次二分，分到每组只有一个元素之后开始两两归并，然后逐层返回。
那么，迭代就直接从每组一个元素开始进行两两归并，然后每组两个元素、四个元素…，直到每组的元素个数超过数组元素总个数。
因为这里是两两进行归并，所以需要对最后一组的情况进行判定，如果最后的元素刚好一组或者不足一组，那么不需要归并，如果刚好两组或者超过一组但是不足两组，那么需要进行归并。

2. 实现代码：

// 归并
void _MergeSortNonR(int* arr, int* tmp, int sz)
{// 每组元素个数int size = 1;// 开始归并while (size < sz){// 开始本组元素个数为 size 的归并int i;for (i = 0; i < sz; i += 2*size){// 获取两组区间int begin1 = i, end1 = i + size - 1;int begin2 = i + size, end2 = i + 2 * size - 1;// 判断// 刚好一组或者不足一组if (end1 >= sz - 1)break;else if (end2 >= sz - 1)  // 刚好两组或者不足两组但是超过一组end2 = sz - 1;// 归并int begin = i, end = end2;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[begin++] = arr[begin1++];elsetmp[begin++] = arr[begin2++];}// 剩下的元素while (begin1 <= end1)tmp[begin++] = arr[begin1++];while (begin2 <= end2)tmp[begin++] = arr[begin2++];// 拷贝回原数组begin = i;while (begin <= end){arr[begin] = tmp[begin];++begin;}}// 每组元素个数翻倍size *= 2;}
}// 3. 归并排序（非递归）
void MergeSortNonR(int* arr, int sz)
{// 创建临时数组int* tmp = (int*)malloc(sizeof(int) * sz);if (NULL == tmp){perror("MergeSortNonR::malloc: ");return;}// 开始归并_MergeSortNonR(arr, tmp, sz);// 释放临时数组free(tmp);
}