当前位置：首页 > backend >正文

排序（数据结构）

backend 2025/8/23 15:39:29

比较排序

插入排序（斗地主摸牌就是一个插入排序）

单纯的插入排序也叫直接插入排序

时间复杂度：

最好O(n)
最坏O(n^2)

过程
先写单趟，再写整体
依次比较，如果大于就往后挪动，否则就退出循环，插入数据

void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i-1;int tmp = a[i];//讲tmp插入到[0,end]区间，保证有序//和前一次顺序有关系 所以最好的时候就是O(n)while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

希尔排序（分组插排）

希尔排序也是一个插入排序，不过他对原来的插入排序做了优化
时间复杂度

O(n^1.3)

过程
1.预排序 --目标数组接近有序
2.直接插入排序

//希尔排序
//简化写法
//多组并排
//时间复杂度O(n^1.3)
void ShellSort(int* a, int n)
{int gap = n;//gap > 1while (gap > 1){//gap /= 2;gap = gap / 3 + 1;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;}}
}

时间复杂度的分析

希尔排序是一个很复杂的排序，他的时间复杂度是一个增量式序列问题，如果我们只算边界的话，它可以约等于n,但是他的中间应该是一个上升和下降的曲线。但是该怎么证明嘛，这里没有明确的回答，涉及到了一些数学问题。正常分析可能会认为是n*logn,但是局部的结论认为他是n^1.3次方，这也是他复杂的原因，因为它没有一个明确的证明过程，可以记一下结论。这里如果非要深究的话，和gap取值是有关的，关键是gap的取值不是定值，而是一直在变化。目前比较认可的取值是n/2和n/3+1。如果有兴趣的话可以研究一下，但是这就涉及到一些数学领域的问题啦。

直接选择排序

时间复杂度

O(n^2)

直接选择排序很简单，同时也是一个最烂的排序。
为什么说这是一个最烂的排序呢因为他的时间复杂度无论是最好还是最坏的情况都是O(n^2)，他的每一次排序都是从新选择，和前面的排序没有关联。
选择排序和插入排序的关系就像一个是斗地主的时候边摸边排序，一个是等发完所有的牌，再去给牌排序。

//选择排序
//时间复杂O(n^2)
//最坏O(n^2)
//最好O(n^2)
//最垃圾的算法  他的前一次顺序调整和下一次没有关系 无论什么时候都是一个等差数列相加
void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int min = left, max = left;//单躺for (int i = left + 1; i <= right; i++){if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(&a[left], &a[min]);//left 和 max重叠if (left == max){max = min;}Swap(&a[right], &a[max]);left++;right--;}
}

冒泡排序（默认升序）

时间复杂度

O(n^2)

冒泡排序属于交换排序的一种
不做优化的情况下时间复杂度都是O(n^2)，做了优化的情况下最好的情况是O(n)
两两交换，一次遍历下来肯定能能把最大值排好，他和插入排序也是一个等差数列相加。
那冒泡排序和插入排序那一个更好呢？答案是插入排序。
虽然都属于一个量级，但是在数据是部分有序和接近有序的时候插入排序会更快，比如数据1，3，2，4，5。
大家可能不理解，不是时间复杂度都一样了吗？为啥还有更优的说法呢？这里时间复杂只是一个量级标准，就像我们都是在校大学生，但是大学生就没有区别吗？有的人早起备考四六级，考研；有的人天天宿舍打游戏，通宵熬夜。出去讲，我们都会说自己是大学生，这是一个量级标准，但是你们还是很有区别。如果你非要从时间复杂度为O(n^2)选择一个排序，那插入排序绝对是YYDS。
冒泡排序其实更多的是教学意义，实际中不太会用他。

堆排序

时间复杂度

O(n*logn)

结论

排升序，建大堆
排降序，建小堆

这里排序建堆，是有点反正常的。这里采用的是，从下向上逐渐建堆，类似于后序遍历。建好堆(升序为例)，从堆顶取数据放到末尾，再对剩余的数组建堆(向下调整)，重复操作。这里建堆，采用向上调整和向下调整都行，这里推荐使用向下调整（一个函数搞定）这里排序见大堆还是小堆，其实不是绝对，这里推荐的是最佳的解法，如果非要使用排升序，建小堆，也不是不能实现。

//向下调整
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//注意越界if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
//时间复杂度O(n*logn)
void HeapSort(int* a, int n)
{//模拟插入建堆//排升序 建大堆//排降序 减小堆//向下调整建堆 效率更高 一般使用向下调整建堆  o(n - log n)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;//这里的时间复杂度计算和向上建堆一样 N*logNwhile (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

快速排序

时间复杂度

O(n*logn)

1962年由Hoare提出的一种二叉树结构的交换排序，它的基本思想是，选基准值/关键值，把他放在一个正确的位置(比他小的放在左边，比它大的放在右边)，递归该过程。（升序为例）

结论：以左边为基准值，先从右边找，相遇位置一定是比key小的,以右边为基准值，先从左边找，相遇位置一定是比key大的。

这里分析是两种情况，右边先遇到左边，左边先遇到右边。数据分析下就可以的出来，很简单。
如果你是以左边为基准值，先从左边找，相遇位置一定是比key小的,
这个相遇位置不一定是比key小，这里随便找一个反例，就可以得出来。

最原始的快排有个致命问题就是key值的选择如果固定，在有序的时候，就是最坏的情况。递归太深了，会栈溢出。所以，这里提供了两种解决方案，三数选中和随机选key。这里更推荐三数选中，他完美解决了有序的情况。

这里有三种实现快速排序的方法，第一种就是最纯粹的Hoare版本，但是Hoare版本不太好理解，容易写错。所以就有大佬进行改编，衍生出了挖坑法和前后指针法。这种方法只是对单趟的遍历进行了改编，本质上还是快排的思想，还是递归，时间复杂度也是属于O(n*logn)。这里推荐使用前后指针的方法，因为这个方法比较简单而且不容易写错。
这里介绍的都是递归快排的写法，但是递归就有一个致命问题，那就是递归太深会栈溢出，这其实不是代码的问题，是编译器的问题。所以，我们还要学习非递归的写法。
三数选中

//选取中间的数
int GetMiduimNum(int* a,int left, int right)
{//int mid = left + right / 2; 错误写法int mid =  left + (right - left) / 2;if (a[left] < a[mid]) // 2 < 3{if (a[right] > a[mid])//4 > 3{return mid; // 2 3 4}else if(a[left] > a[right]){return left;}else{return right;}}else //a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}}
}

Hoare

快速排序 Hoare写法 最简单最原始版本
最坏情况O(n^2)
最好情况O(n*logn)
时间复杂度n*logn 加了优化就可以解决有序的情况
int Part1Sort(int* a, int left, int right)
{//结束条件if (left >= right){return;}int begin = left, end = right;//随机选Key 版本//int randi = left + (rand() % (right - left));//Swap(&a[left], &a[randi]);//三数选中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int key = left;//left++ 这是一种错误写法 千万不要写while (left < right){//右边找小while (left < end && a[right] >= a[key]){right--;}//左边找大while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}Swap(&a[key], &a[right]);key = left;return key;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part1Sort(a, left, right);//begin key -1 hole key+1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

挖坑法

//挖坑法 不再有左边先走还是右边先走 就是挖坑填坑 大思路不变
int Part2Sort(int* a, int left, int right)
{int begin = left, end = right;//三数选中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int hole = left;int key = a[left];while (left < right){while (left < end && a[right] >= key){right--;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;//回坑return hole;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part2Sort(a, left, right);//begin key -1 hole key+1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

前后指针

//前后指针
int Part3Sort(int* a, int left, int right)
{int begin = left, end = right;//三数选中int mid = GetMiduimNum(a, left, right);Swap(&a[left], &a[mid]);int prev = left, cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
//区间优化 减少递归次数 主要是递归深度 对性能影响不大
void QuickSort(int* a, int left, int right)
{//结束条件if (left >= right){return;}if (right - left + 1 > 10){int keyi = Part3Sort(a, left, right);//begin key -1 hole key+1 end//递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}else{InsertSort(a + left, right - left + 1);}
}

递归改非递归有两种思路

直接改循环（斐波那契额数列）
使用栈辅助（快排）

非递归写法
栈里面取一段区间，单排分割子区间入栈，子区间只有一个值或者不存在就不入栈。这里其实就是在模拟递归而已，不理解的话，可以画个递归展开图。
快排其实还有一个非常致命的问题就是如果存在大量重复的问题，他的效率会变得很低，这个时候三数选中和随机选key也不管用。这个时候需要一个三路划分

//非递归写法
void QuickSort(int* a, int left, int right)
{ST stack;STInit(&stack);STPush(&stack, right);STPush(&stack, left);while (!STEmpty(&stack)){int begin = STTop(&stack);STPop(&stack);int end = STTop(&stack);STPop(&stack);//先单趟int keyi = Part3Sort(a, begin, end);//begin keyi-1 keyi keyi+1 endif (keyi + 1 < end){STPush(&stack, end);STPush(&stack, keyi+1);}if (begin < keyi -1){STPush(&stack, keyi-1);STPush(&stack, begin);}}STDestroy(&stack);
}

总结

快排类似于一个二叉树的前序遍历，就像先找到根，在遍历左子树和右子树。快排与普通的排序相比，时间复杂度已经有了质的提升。但是快排也不是一个简单的排序。它有许多版本，最原始的就是Hoare版本，也是很难理解的。于是后面的挖坑法和前后指针法及诞生了。这里三种方法都要学习，但是平常写建议前后指针，这是一种比较简单的方法(如果你能理解)

归并排序

归并排序类似与一个二叉树的后序遍历，要对一段数字排序先找到这段数字的两个有序子区间，使用比较大小，依次取数字，进行排序。找到两个有序子区间就是一个分割归并过程。

递归实现

void _MergeSort(int* a, int begin,int end,int* tmp)
{if (begin >= end){return;}int mid = (begin + end) / 2;//[begin mid] [mid+1 end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);//归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(a, 0, n - 1,tmp);free(tmp);tmp = NULL;
}

非递归实现

//非递归 归并排序
void _MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc failed");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2*gap){int begin1 = i, end1 = i+gap-1;int begin2 = i+gap, end2 = i+2*gap-1;//printf("[%d %d][%d %d] ", begin1, end1, begin2, end2);int j = i;//修正路线/*	if (end1 >= n){end1 = end2 = n - 1;begin2 = n;}else if (begin2 >= n){end2 = n - 1;begin2 = n;}*/if (begin2 >= n){break;}else if (end2 >= n){end2 = n - 1;}printf("[%d %d][%d %d] ", begin1, end1, begin2, end2);while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//0 1 2 3memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}//memcpy(a, tmp, sizeof(int) * (n));printf("\n");gap *= 2;}free(tmp);
}

非比较排序

计数排序

时间复杂度

O(n+range)

hash映射，记录坑位数字出现的次数。当范围很集中时，数据为int，比较适合。
局限性：对于double，字符串和很多其他情况无法完成。

void CountSort(int* a, int n)
{//找最大值和最小值int max = a[0], min = a[0];for (int i = 1; i < n; i++){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* CountA = (int*)calloc(range, sizeof(int));//映射for (int i = 0; i < n; i++){CountA[a[i]-min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (CountA[i]--){a[j++] = i+min;}}
}