DS几大常见排序讲解和实现(中)(14)
文章目录
- 前言
- 一、希尔排序( 缩小增量排序 )
- 基本思想
- 实现思路
- 时间空间复杂度分析
- 总结
- 二、选择排序
- 基本思想
- 实现思路
- 时间空间复杂度分析
- 总结
- 三、堆排序
- 四、冒泡排序
- 基本思想
- 实现思路
- 总结
- 五、归并排序
- 基本思想
- 实现思路
- 总结
- 六、计数排序
- 基本思想
- 总结
- 总结
前言
承上启下，正文开始！
一、希尔排序( 缩小增量排序 )
希尔排序是一种基于插入排序的算法，通过引入增量的概念来改进插入排序的性能
基本思想
通过预排序使得无序接近有序序列，大体流程:先选定一个整数gap，将待排序序列中所有记录分组，所有距离为gap记录分在同一组，并对每一组记录进行排序，重复上述分组和排序的工作(gap不断缩小)，当gap到达1，此时记录已经接近有序，最后整体进行插入排序，使得记录排好序
gap为1的时候，其实就已经退化为直接插入排序
实现思路
gap就是增量，我们发现根据当前增量，数组被分为gap个子序列，这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序，因为gap一开始很大，最后才慢慢变回1，说明一开始如果升序且小数据在后面，能被很快的移动到前面，从而达到降低时间复杂度的目的，这也是我们优化的一种体现
在合理设置增量的前提下，一个数组一共可以分裂成增量个子序列，且每个子序列上相邻元素之差为增量
我们以上图为例子，5个子序列分别是：
子序列1: 9，4
子序列2: 1，8
子序列3: 2，6
子序列4: 5，3
子序列5: 7，5
然后对每个子序列进行独立的插入排序：
子序列1排序后：4，9
子序列2排序后：1，8
子序列3排序后：2，6
子序列2排序后：3，5
子序列3排序后：5，7
一趟排序之后的数组：
4 1 2 3 5 9 8 6 5 7
我们发现走了一轮希尔排序后，数组并不是完全有序，但是已经更接近有序了，接着就可以减小增量了！
但是如何减小增量？一般有两种处理方式：
gap /= 2，保证了无论gap初始值多少，最后都能变为1，完成直接插入排序
gap = gap / 3 + 1; 因为如果gap为2的时候，在/3就直接等于0了，没有完成直接插入排序
所以单独一个子序列排序：
int gap;
int end;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end-=gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
与直接插入代码不同的是，这里对end所加减的均为gap
如若不理解，请画图！！
单趟排序实现：
//这里for循环的条件为 i < n-gap 防止数组越界
int gap;
for (int i = 0; i < n-gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
全部子序列排序：
//外层循环（for (int j = 0; j < gap; j++)）意在对每个以gap为间隔的分组进行遍历
int gap;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
上述代码的三层循环着实不太美观，于是我们换一种思路，不再排完一个子序列再排另外一个子序列，因为每个子序列之间不会产生交互，于是我们把 i += gap，改为i++，并且脱去最外层的循环
//这时候就变成了统一排完每个子序列的同一个位置的元素后，再排下一个位置的元素
//比如n为10，gap为5，那么有5个子序列，这里就是统一排完5个子序列的第二个元素后，完成循环跳出
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
那么我们还要思考这个gap应该如何取值？
首先，还是要有这个意识：
gap越大，大的值更快调到后面，小的值更快调到前面，越不接近有序。
gap越小，大的值更慢调到后面，小的值更慢调到前面，越接近有序。
当gap为1，就是直接插入排序。
因此，gap的值应该不是固定的，应该随着n的值而变化，这里我建议先设计为n，进入循环后再 gap /= 2，循环条件为gap > 1
void ShellSort(int* arr, int n)
{
// 预排序，接近有序
// 直接插入排序，有序
// 越大的数越快跳到后面，越小的数越快跳到前面
int gap = n;
while (gap > 1){
gap /= 2;
for (int i = 0 ; i < n - gap ; i++){ // 减少for循环的个数,每次对不同组进行预排序
int end = i;
int tmp = arr[end + gap];
while (end >= 0){
if (arr[end] > tmp){
arr[end + gap] = arr[end];
end -= gap;
}
else {
break;
}
arr[end + gap] = tmp;
}
}
}
}
时间空间复杂度分析
希尔排序的时间复杂度并不固定，它依赖于所选择的间隔序列（增量序列）。直到今天，已经有多种不同的间隔序列被提出来，每种都有自己的性能特点
《数据结构(C语言版)》— 严蔚敏
《数据结构-用面相对象方法与C++描述》— 殷人昆
空间复杂度为O(1)，在原数组上操作，时间复杂度为O(N^1.25) 到 O(1.6* N^1.25)
总结
- 时间复杂度：O(N²) -> 很复杂，有多种可能
- 空间复杂度：O(1)
- 稳定性：不稳定
- 复杂性：简单
二、选择排序
基本思想
选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小（或最大）元素，然后将其放置到未排序序列的起始位置，这个过程一直重复直至整个数组被排序
实现思路
- 从数组的当前未排序部分选择最小（或最大）的一个元素
- 将这个最小（或最大）元素与未排序序列的第一个元素交换位置
- 然后从剩余未排序的元素中继续这个过程，将每一次找到的最小（或最大）元素放到未排序序列的开始
- 这个过程一直进行到整个数组的所有元素都被排为有序状态
其实我们还可以再优化一下，既要找到最小，又要找到最大，然后一个跟头交换，一个跟尾交换，这样能有一个常数级别的优化
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int a[], int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;//找最大值的下标
int mini = begin;//找最小值的下标
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
- 首先初始化两个索引begin和end，分别代表当前未排序序列的开始和结束位置。
- 进入一个循环，条件是begin < end，确保在数组中还有未排序的元素。
- 遍历一遍序列，找到最大元素和最小元素的下标。
- 将最小元素与序列的始端交换，最大元素与序列的尾端交换。
- 更新begin与end
可是我们要思考这样书写会不会有问题，事实上是有的：
因为这里我们是首先进行最小元素与首位置更换，再进行最大元素与末尾更换，如果我的最大元素就在首位置就会有问题
本来找到了最大值和最小值的下标，头跟最小值交换位置，最大值被交换走了，可是最大值的下标还是没变，仍然指向头，所以要加个判断，如果最大值是begin的话，我们把最大值的下标改为最小值的下标
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int a[], int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int maxi = begin;//找最大值的下标
int mini = begin;//找最小值的下标
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
//最大值的位置跟最小值重合
//mini被换到maxi位置时 原本的最大值则是mini
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
时间空间复杂度分析
对于时间复杂度来说，最好、平均、最坏情况下的时间复杂度都是 O(n^2)，因为不管数组的初始顺序如何，选择排序都需要比较所有未排序的元素来找到最小（或最大）的元素，并执行这个过程 n-1 次（对于 n 个元素的数组），每次选择操作需要比较的次数从 n-1 次减少到 1 次
对于空间复杂度来说，选择排序是一种原地排序算法，除了输入数组外，它只需要有限的几个变量（比如，用于存储最小元素下标的变量和循环计数器）。因此，它的空间复杂度为常数空间O(1)
总结
- 选择排序思考非常好理解，但是效率不是很好。实际中很少使用。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 复杂性：简单
三、堆排序
直接参考前文就行：
堆排序的讲解
void AdjustDown(int* arr, int n, int parent)
{
// 假设法先选出大的孩子
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && arr[child] < arr[child + 1]){ // child + 1 < n是为了防止右孩子越界
child += 1;
}
if (arr[child] > arr[parent]){
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapSort(int* arr, int n)
{
// 要升序，建大堆
for (int i = (n - 2) / 2 ; i >= 0 ; i--){
AdjustDown(arr, n, i);
}
int end = n - 1;
while (end > 0){
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
四、冒泡排序
基本思想
比较两个相邻的元素，当不满足某一条件时，发生相邻元素的交换，直到整个序列有序为止
序列中两个相邻元素进行比较，当满足条件发生交换操作，导致最小或大元素放到后面位置，不断重复该过程，直到有序
实现思路
我们的目的是直到有序就停下来，但是上面的逻辑是地毯式查找，对此我们需要设置一个标识变量去标识是否有序，如果不需要交换说明有序直接退出
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
int arr[10] = { 0 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < sz; i++)
{
scanf("%d ", &arr[i]);///输入数据
}
int tap = 0;
for (int i = 0; i < sz - 1; i++)
{
int flag=1;
for (int j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
tap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tap;
flag=0;
}
}
if(flag==1)
{
break;
}
}
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);//打印数据
}
return 0;
}
总结
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度: O (N2)
- 空间复杂度: O(1)
- 稳定性：稳定
五、归并排序
基本思想
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序序列即先使每个子序列有序，再使子序列间有序。若加你个两个有序表合并成一个有序表，称为二路归并
实现思路
其实你猜一下就知道这里肯定还要运用到递归~哈哈！
归并排序主要是通过已有序的子序列合并，得到完全有序的序列。那么将已有序的左右子树得到完全有序的根序列，完成这项操作还需要借助一块空间完成合并，再使用内存函数复制或转移到原本序列中，所以先要排好左边和右边，其实是一种后序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right){
return ;
}
int mid = (left + right) >> 1;
_MergeSort(arr, left, mid, tmp); //排好了左边
_MergeSort(arr, mid + 1, right, tmp); //排好了右边
// 归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2){
if (arr[begin1] < arr[begin2]){
tmp[index++] = arr[begin1++];
}
else {
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1){
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2){
tmp[index++] = arr[begin2++];
}
// 拷贝回去，在回溯的过程中就要返回
// for (int i = left ; i <= right ; i++){
// arr[i] = tmp[i];
// }
memcpy(arr + left, tmp + left, sizeof(int)*(right - left + 1));
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
总结
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的使解决在磁盘中的外排序问题。
- 时间复杂度: O(N*logN)
- 空间复杂度: O(N)
- 稳定性:稳定
- 没有进行交换，更加适合外排序
六、计数排序
基本思想
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1; // 节省空间，存储数据并不是从0开始，采用相对映射
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
printf("calloc fail\n");
return;
}
// 统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
// 排序
int i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;//加回去
}
}
}
总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
总结
是不是被排序这一高深的学问给吓到了？哈哈，别急，下篇我会介绍一种最常用的排序算法，它有很多变式，也很美妙~