七种常见的排序算法和实现

2024-08-22 11:12
文章标签 算法 实现 常见 排序 七种

本文主要是介绍七种常见的排序算法和实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

 我们依次对下面排序进行讲解，并用下面函数来测试其性能。

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);// 希尔排序void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void AdjustDwon(int* a, int n, int root);void HeapSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n)// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);// 快速排序挖坑法
int PartSort2(int* a, int left, int right);// 快速排序前后指针法
int PartSort3(int* a, int left, int right);void QuickSort(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)// 测试排序的性能对比
void TestOP(){srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int)*N);int* a2 = (int*)malloc(sizeof(int)*N);int* a3 = (int*)malloc(sizeof(int)*N);int* a4 = (int*)malloc(sizeof(int)*N);int* a5 = (int*)malloc(sizeof(int)*N);int* a6 = (int*)malloc(sizeof(int)*N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N-1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}

2.常见排序算法的实现

2.1 插入排序
2.1.1基本思想：

OJ链接 直接插入排序是一种简单的插入排序法，其基本思想是：

比特科技 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为 止，得到一个新的有序序列。

2.1.2直接插入排序：

将后面数依次和前面数相比较，当碰到小于它的数时就插在其身后。

void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}	
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

2.1.3 希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。

void ShellSort(int* a, int n)
{int gam = n-1;while (gam >= 1){gam /= 2;for (int i = 0; i < n-gam; i++){int end = i;int tmp = a[end + gam];while (end >= 0){if (tmp < a[end]){a[end + gam] = a[end];end -= gam;}elsebreak;}a[end + gam] = tmp;}}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定： 

4 . 稳定性：不稳定。

2.2 选择排序
2.2.1基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。

2.2.2 直接选择排序:

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。

若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。

在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

 

注意：作者每次都去选择最大和最小数 

void SelectSort(int* a, int n)
{int left=0, right=n-1;int mini = left, maxi = left;while (left < right){for (int i = left+1; i <= right; i++){if (a[i] < a[mini])mini = i;if (a[i]> a[maxi])maxi = i;}Swap(&a[left], &a[mini]);if (left == maxi)maxi = mini;Swap(&a[right], &a[maxi]);left++;right--;}
}

 直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

void  AdjustDwon(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){//交换Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}
void HeapSort(int* a, int n)
{for (int i = 0; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}
}

 直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.3 交换排序

根据两个数比较的结果来进行交换，从而排出有序。

2.3.1冒泡排序

每次排序会将最大数或者最小数排好。

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int tmp = 1;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);tmp = 0;}			}if (tmp == 1)break;}	
}

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

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

3. 空间复杂度：O(1)

4. 稳定性：稳定 

2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1. hoare版本

int GetmidNumi(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] >= a[right]&& a[mid] <= a[left]|| a[mid] <= a[right] && a[mid] >= a[left])return mid;if (a[right] >= a[mid] && a[right] <= a[left] || a[right] <= a[mid] && a[right] >= a[left])return right;if (a[left] >= a[mid] && a[left] <= a[right] || a[left] <= a[mid] && a[left] >= a[right])return left;
}
void PartSort1(int* a, int left, int right)
{if (left >= right)return;//随机key/*int randi = left+(rand() % (right - left));Swap(&a[randi], &a[left]);*///三数选中Swap(&a[GetmidNumi(a, left, right)],&a[left]);int keyi=left;int L = left, R = right;while (L < R){while (L<R && a[R]>=a[keyi])R--;while (L<R && a[L]<=a[keyi])L++;Swap(&a[L], &a[R]);}Swap(&a[R], &a[keyi]);keyi = R;PartSort1(a, left, keyi-1);PartSort1(a, keyi + 1, right);
}

 2. 挖坑法

int GetmidNumi(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] >= a[right]&& a[mid] <= a[left]|| a[mid] <= a[right] && a[mid] >= a[left])return mid;if (a[right] >= a[mid] && a[right] <= a[left] || a[right] <= a[mid] && a[right] >= a[left])return right;if (a[left] >= a[mid] && a[left] <= a[right] || a[left] <= a[mid] && a[left] >= a[right])return left;
}
void PartSort2(int* a, int left, int right)
{if (left >= right)return;//随机key/*int randi = left+(rand() % (right - left));Swap(&a[randi], &a[left]);*///三数选中Swap(&a[GetmidNumi(a, left, right)], &a[left]);int key = a[left];int L = left, R = right;while (L < R){while (L < R && a[R] >=key)R--;a[L] = a[R];while (L < R && a[L] <= key)L++;a[R] = a[L];}Swap(&a[R], &key);PartSort2(a, left, R - 1);PartSort2(a, R + 1, right);
}

3. 前后指针版本

int GetmidNumi(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] >= a[right]&& a[mid] <= a[left]|| a[mid] <= a[right] && a[mid] >= a[left])return mid;if (a[right] >= a[mid] && a[right] <= a[left] || a[right] <= a[mid] && a[right] >= a[left])return right;if (a[left] >= a[mid] && a[left] <= a[right] || a[left] <= a[mid] && a[left] >= a[right])return left;
}
int PartSort3(int* a, int left, int right)
{//随机key/*int randi = left+(rand() % (right - left));Swap(&a[randi], &a[left]);*///三数选中Swap(&a[GetmidNumi(a, left, right)], &a[left]);int keyi = left;int prev = left, cur = left+1;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;
}
2.3.3 快速排序优化

1.三数取中选key法：在最后和最前和中间选一个第二大的数

int GetmidNumi(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[mid] >= a[right]&& a[mid] <= a[left]|| a[mid] <= a[right] && a[mid] >= a[left])return mid;if (a[right] >= a[mid] && a[right] <= a[left] || a[right] <= a[mid] && a[right] >= a[left])return right;if (a[left] >= a[mid] && a[left] <= a[right] || a[left] <= a[mid] && a[left] >= a[right])return left;
}

2.递归到小的子区间时可以考虑用插入排序（递归到后面，会有大量繁琐的函数递归，要是直接用插入解决会更快）

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

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

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

2.4 归并排序

基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤： 

 

void MergeSort(int* a,int begin,int end,int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int j = begin;MergeSort(a, begin1, end1, tmp);MergeSort(a, begin2, end2, tmp);while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}while (begin1 <= end1 || begin2 <= end2){if (begin1 <= end1)tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}memcpy(a+begin , tmp+begin , sizeof(int) * (end-begin+1));
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

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

3. 空间复杂度：O(N)

4. 稳定性：稳定 

3.总结

这篇关于七种常见的排序算法和实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1096109。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2