【排序算法】总结篇

✨✨这些 排序算法都是指的 需要进行比较的排序算法

✨✨下面都是略微讲解一下思路，如果需要详细了解哪一个排序，点击👉链接即可

✨✨对于时间、空间复杂度、稳定性，希望你🧑‍🎓能够理解记忆🧑‍🎓而不是背表格

目录

一、稳定性定义：

 二、各个排序：

 1、直接插入排序：【排序算法】插入排序-CSDN博客

2、希尔排序：【排序算法】希尔排序-CSDN博客

3、选择排序：【排序算法】选择排序-CSDN博客

4、堆排序：【排序算法】堆排序(Heapsort)-CSDN博客

5、冒泡排序：【排序算法】冒泡排序-CSDN博客

6、快速排序：【排序算法】快速排序-CSDN博客

7、归并排序：【排序算法】归并排序-CSDN博客

三、性能比较：

Sort.h

Sort.c

 test.c

四、总结：​编辑

---

一、稳定性定义：

        排序算法的稳定性指的是在排序过程中，相等的元素在排序后保持它们原有的相对顺序。也就是说，如果两个元素在原始未排序的序列中是相等的，并且其中一个在另一个之前，那么在排序后的序列中，这个顺序依然保持不变。

当然使用可能对我们来说不够明显，但是在实践中，在对结构体进行排序非常有意义

✨👉 假设我们要按总分进行排名，但是如果总分相同的情况，按照数学成绩高的排前头，这个时候，我们先按照数学成绩排好序，相当于第一名是张三，那么按照总分拍好后，张三还是排在李四的前面，从这个表来看，第一是张三，第二是李四，第三是小翔，这就是稳定性，总分相同的情况下，张三还是在李四的前面

 二、各个排序：

 1、直接插入排序：【排序算法】插入排序-CSDN博客

✨直接插入排序的思想：前一个数有序，我拿这一个数和你比，如果比你小，前一个数往后移动。相当于插扑克牌，那么前一个和我手上的牌相等的话，不会取挪前一张牌。

所以》》 稳定性：✨稳定

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

2、希尔排序：【排序算法】希尔排序-CSDN博客

✨希尔的思想是分gap组，对每个组都进行插入排序，然后gap会不断变小，当到1时进行直接插入排序，那么想想场景：👉👉相同的元素在预排序的时候如果被分到不同的组，顺序也可能被打断，那么就是不稳定，因为预排序无法控制，所以直接认为不稳定🧑‍🎓

时间复杂度：O(N^1.3)

空间复杂度：O(1)

稳定性：不稳定

3、选择排序：【排序算法】选择排序-CSDN博客

✨在数组里面选小的数，选到小的就更新一下，相同的不更新，然后继续找，直到遍历结束，把最小的放到左边🤔看着好像是稳定的，真是一回事，但是我们只是注意了小的耶🐸，忘记了我们在，在第一个位置的数的情况，如下：我的5和原来的5相对顺序是不是就已经发生改变了🤔记住这个例子它是不稳定的

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：不稳定

4、堆排序：【排序算法】堆排序(Heapsort)-CSDN博客

✨思想：向下调整建堆，建好堆后，将尾元素和栈顶元素交换，交换以后，重现堆n-1个元素的堆进行调整；比如：全是2的大堆，将2取出来，全乱了，乱套了

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

5、冒泡排序：【排序算法】冒泡排序-CSDN博客

✨思想：前一个和后一个比较，大于后一个就交换，相等的s；》》》稳定的

时间复杂度：O(N^2)

空间复杂度：O(1)

稳定性：稳定

6、快速排序：【排序算法】快速排序-CSDN博客

✨思想：找比kyi小的和比kyi大的，小的放前半部分，大的放到后半部分，最后kyi放到中间》》

kyi交换到后面，顺序乱了，所以✨不稳定

时间复杂度：O(N*logN)

空间复杂度：O(logN)

稳定性：不稳定

7、归并排序：【排序算法】归并排序-CSDN博客

✨思想：2个有序的数组合并，2个有序数组，相等的情况，取前一个尾插

✨ 稳定的

时间复杂度：O(NlogN)   

空间复杂度：O(N) 

稳定性：稳定

三、性能比较：

👉✨拿上代码可以自己测试玩哦，感兴趣的可以拿走;

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include"Stack.h"
#include<string.h>
//插入排序：有实践意义
void InsertSort(int* a, int n);
//希尔排序：
void ShellSort(int* a, int n);//堆排序：
void Swp(int* p1, int* p2);
void AdjustDwon(int* a, int n, int paret);
void HeapSort(int* a, int n);
//选择排序：
void SelectSort(int* a, int n);//冒泡排序：
void BubbleSort(int* a, int n);//快速排序：left和right传的都是下标
void QuickSort1(int* a, int left, int right);
//挖坑法
void QuickSort2(int* a, int left, int right);
//前后指针法：
void QuickSort3(int* a, int left, int right);
//非递归法：
void QuickSortNonR(int* a, int left, int right);//归并排序：
void MergeSort(int* a, int n);
//非递归：
void MergeSortNonR(int* a, int n);//计数排序：
void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 3
#include"Sort.h"//堆排序：
//交换数据
void Swp(int* p1, int* p2)
{assert(p1 && p2);int tmp = *p2;*p2 = *p1;*p1 = tmp;
}
void AdjustDwon(int* a, int n, int parent)
{assert(a);//孩子int child = parent * 2 + 1;while (child<n){if (child + 1 < n && a[child + 1] > a[child]){child = child + 1;}if (a[parent] < a[child]){Swp(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//向下调整建堆int i;for (i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}for (i = n - 1; i > 0; i--){Swp(&a[0], &a[i]);AdjustDwon(a, i, 0);}
}
//选择排序：
//void SelectSort(int* a, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int min = i;
//		for (int j = i; j < n; j++)
//		{
//			if (a[j] < a[min])
//			{
//				min = j;
//			}
//		}
//		Swp(&a[min], &a[i]);
//	}
//
//}
选择排序
//void SelectSort(int* a, int n)
//{
//	int begin = 0, end = n - 1;
//	while (begin < end)
//	{
//		int mini = begin, maxi = begin;
//		for (int i = begin + 1; i <= end; ++i)
//		{
//			if (a[i] > a[maxi])
//			{
//				maxi = i;
//			}
//
//			if (a[i] < a[mini])
//			{
//				mini = i;
//			}
//		}
//		if (mini == end && maxi == begin)
//		{
//			Swp(&a[maxi], &a[mini]);
//			
//		}
//		else if (maxi == begin)
//		{
//			//谁先换掉
//			Swp(&a[end], &a[maxi]);
//			Swp(&a[begin], &a[mini]);
//		}
//		else
//		{
//			Swp(&a[begin], &a[mini]);
//			Swp(&a[end], &a[maxi]);
//		}
//		begin++;
//		end--;
//	}
//}
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[maxi] < a[i]){maxi = i;}if (a[mini] > a[i]){mini = i;}}Swp(&a[mini], &a[begin]);if (maxi == begin){maxi = mini;}Swp(&a[maxi], &a[end]);begin++;end--;}
}//插入排序：end+1前面的是有序的，不断拿end+1去比较
void InsertSort(int* a, int n)
{int i;for (i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}//希尔排序:插入的优化，1、预排序 2、插入排序
void ShellSort(int* a, int n)
{int gap = n;//gap的组数越大，数据可以更快的跳到后面，小的更快跳到前面，但是越不接近有序；反之，gap越接近有序while (gap > 1){//巧妙的用的除法，/2 /3 /4都行，但是有人证明了/3更好，还要加1，因为gap小于3的话gap/3==0//最后一次gap一定是1,也就是插入排序，数据变成有序的呢！！！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;}}}
//4层循环(方法二)
//void ShellSort(int* a, int n)
//{
//
//	int gap = n;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int i = 0; i < gap; i++)
//		{
//			for (int j = i; j < n - i-gap; j += gap)
//			{
//				int end = j;
//				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;			}
//		}
//
//	}
//
//
//}//冒泡排序：
void BubbleSort(int* a, int n)
{int i;for (i = 0; i < n - 1; i++){int flag = 0;//从前往后冒泡，第一趟最后一个为最大值；只要n-1趟即可for (int j=1; j < n-i; j++){if (a[j] < a[j - 1]){int tmp = a[j];a[j] = a[j - 1];a[j - 1] = tmp;flag = 1;}}if (flag == 0){break;}}}//快速排序：
//递归实现：
//优化：先三个数找中间：
int GetMin(int* a, int left, int right)
{int min = ((right - left) >> 1)+ left;if (a[min] < a[left]){if (a[min] > a[right]){return min;}else if (a[right]<a[left]){return right;}else{return left;}}else{if (a[min] < a[right]){return min;}else if (a[right] > a[left]){return right;}else{return left;}}}
//Hoare
void QuickSort1(int* a, int left, int right)
{//递归结束条件/*if (right <= left){return;}*///优化后：递归结束条件变成了当剩下10个以内的元素需要排序时，就使用插入排序if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else {//3个取中int mid = GetMin(a, left, right);//将中的元素换到leftSwp(&a[mid], &a[left]);int keyi = left;int begin = left;int end = right;while (begin < end){//右边找小的，左边找大的while (a[end] >= a[keyi] && end > begin){end--;}while (a[begin] <= a[keyi] && end > begin){begin++;}//交换Swp(&a[begin], &a[end]);}Swp(&a[keyi], &a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, end + 1, right);}
}
//挖坑法(有一个人要蹲坑)效率差不多
void QuickSort2(int* a, int left, int right){if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int mid = GetMin(a, left, right);Swp(&a[left], &a[mid]);int keyi = a[left];int begin = left;int end = right;while (begin < end){//仍然是左边找大，右边找小while (begin < end && a[end] >= keyi){end--;}a[begin] = a[end];while (begin < end && a[begin] <= keyi){begin++;}a[end] = a[begin];}a[end] = keyi;QuickSort2(a, left, begin - 1);QuickSort2(a, end + 1, right);}}
//前后指针法：
void QuickSort3(int* a, int left, int right)
{/*if (left >= right){return;}*/if (right - left + 1 < 10){//小于10个数据进行插入排序InsertSort(a + left, right - left + 1);}else{int mid = GetMin(a, left, right);Swp(&a[mid], &a[left]);int keyi = left;int prev = left;int cur = left + 1;//cur先走，找小的while (cur <= right){//若小于a[keyi]则prev后移一位 再交换if (a[cur] <= a[keyi]){prev++;Swp(&a[prev], &a[cur]);}cur++;}Swp(&a[prev], &a[keyi]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev + 1, right);}
}
//非递归，将递归变成迭代，最重要的是区间
void QuickSortNonR(int* a, int left, int right)
{SL pts;SLInit(&pts);SLPush(&pts,right);SLPush(&pts, left);while (!SLEmpty(&pts)){int begin = SLPot(&pts);SLPop(&pts);int end = SLPot(&pts);SLPop(&pts);int mid = GetMin(a, begin,end);Swp(&a[mid], &a[begin]);int keyi = begin;int prev = begin;int cur = begin + 1;//cur先走，找小的while (cur <= end){//若小于a[keyi]则prev后移一位 再交换if (a[cur] <= a[keyi]){prev++;Swp(&a[prev], &a[cur]);}cur++;}Swp(&a[prev], &a[keyi]);if (prev + 1 < end){SLPush(&pts, end);SLPush(&pts, prev + 1);}if (prev - 1 > begin){SLPush(&pts, prev-1);SLPush(&pts, 0);}}SLDestroy(&pts);}//归并排序:
//子函数:实现递归
void _MergeSort(int* tmp, int* a, int left, int right)
{if (left >= right){return;}int mid = ((right-left)>>1)+left;_MergeSort(tmp, a, left, mid);_MergeSort(tmp, a, mid + 1,right);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int i = 0;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 + left, tmp, (right - left + 1)*sizeof(int));}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(tmp, a, 0, n-1);free(tmp);tmp = NULL;
}
//非递归归并
void MergeSortNonR(int* a, int n)
{//额外创造一个空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i+=2*gap){int begin1 = i;int end1 = i + gap - 1;int begin2 = i + gap;int end2 = i + 2 * gap-1;int j = i;if (begin2>=n){break;}	 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++];}memcpy(a + i, tmp+i, sizeof(int)*(end2 - i + 1));}putchar('\n');gap *= 2;}free(tmp);tmp = NULL;
}//计数排序：
void CountSort(int* a, int n)
{//求最大和最小值int max = a[0];int min = a[0];for (int i = 1; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int ragem = max - min + 1;//计数的数组int* count = (int*)calloc(ragem, sizeof(int));;if (count == NULL){perror("calloc fail");return;}//计数for (int i = 0; i < n; i++){count[a[i] - min]++;}int j = 0;//排序for (int i = 0; i< ragem; i++){while (count[i]--){a[j++] = i+ min;}}}

 test.c

#define _CRT_SECURE_NO_WARNINGS 3#include"Sort.h"//打印
void InPrin(int* a, int n)
{int i;for (i = 0; i < n; i++){printf("%d ", a[i]);}
}
//验证函数是否成功
void SortTest()
{int a[] = { 10,9,7,1,3,9,4,2,12,3,5,7};int n = sizeof(a) / sizeof(a[0]);//HeapSort(a, n);/*printf("InsertSort:");InsertSort(a, n);InPrin(a, n);putchar('\n');puts("对比");printf("ShellSort:");*///ShellSort(a, n);//InPrin(a, n);//BubbleSort(a, n);//SelectSort(a, n);//QuickSort1(a, 0, n - 1);//QuickSort3(a, 0, n - 1);//QuickSortNonR(a, 0, n - 1);//MergeSort(a, n);//MergeSortNonR(a, n);CountSort(a, n);InPrin(a, n);
}
//性能测试
void SortTest1()
{int n = 10000000;srand((unsigned int)time(NULL));int* a1 = (int*)malloc(sizeof(int) * n);if (a1 == NULL){perror("malloc:a1");return;}int* a2 = (int*)malloc(sizeof(int) * n);if (a2 == NULL){perror("malloc:a2");return;}int* a3 = (int*)malloc(sizeof(int) * n);if (a3 == NULL){perror("malloc:a3");return;}int* a4 = (int*)malloc(sizeof(int) * n);if (a4 == NULL){perror("malloc:a4");return;}int* a5 = (int*)malloc(sizeof(int) * n);if (a5 == NULL){perror("malloc:a5");return;}int* a6 = (int*)malloc(sizeof(int) * n);if (a6 == NULL){perror("malloc:a6");return;}int* a7 = (int*)malloc(sizeof(int) * n);if (a7 == NULL){perror("malloc:a7");return;}int* a8 = (int*)malloc(sizeof(int) * n);if (a8 == NULL){perror("malloc:a8");return;}for (int i = 0; i < n; i++){//尽可能保证多个随机数a1[i] = rand()+i;a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];a8[i] = a1[i];}//冒泡int begin1 = clock();//BubbleSort(a1, n);int end1 = clock();//堆排序int begin2 = clock();HeapSort(a2, n);int end2 = clock();//希尔int begin3 = clock();ShellSort(a3, n);int end3 = clock();//插入（数据太多，也得下桌）int begin4 = clock();//InsertSort(a4, n);int end4 = clock();//选择(下桌，太慢了，影响到其他数据计算)int begin5 = clock();//SelectSort(a5,n);int end5 = clock();//快排int begin6 = clock();QuickSort3(a6, 0, n - 1);int end6 = clock();int begin7 = clock();MergeSort(a7, n);//MergeSortNonR(a7, n);int end7 = clock();int begin8 = clock();CountSort(a8, n);int end8 = clock();printf("BubbleSort:%d\n", end1 - begin1);printf("HeadSort:%d\n", end2 - begin2);printf("ShellSort:%d\n", end3 - begin3);printf("InsertSort:%d\n", end4 - begin4);printf("SelectSort:%d\n", end5 - begin5);printf("QuickSort:%d\n", end6 - begin6);printf("MergeSort:%d\n", end7 - begin7);printf("CountSort:%d\n", end8 - begin8);free(a1);a1 = NULL;free(a2);a2 = NULL;free(a3);a3 = NULL;free(a4);a4 = NULL;free(a5);a5 = NULL;free(a6);a6 = NULL;free(a7);a7 = NULL;free(a8);a8 = NULL;
}int main()
{//SortTest();SortTest1();return 0;
}

四、总结：排序算法

提醒一句：希望你还是通过代码理解性的记忆，明确这个值是怎么计算出来的，而不是记住冰冷的表格❤️🫰