对于给定的序列实现直接插入、折半插入、冒泡、希尔、快速、选择、堆排序
2021/12/12 23:48:51
本文主要是介绍对于给定的序列实现直接插入、折半插入、冒泡、希尔、快速、选择、堆排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.本代码一共实现7种常见排序,其中直接插入排序和折半插入排序思想相同,只不过在寻找插入位置的时候,折半插入排序采用了二分法,在这一步上较直接插入排序更快。
2.冒泡排序很简单,但是可以进阶一步,在内层循环 j 中加一个flag标识,判断在这一次循环中有没有发生值交换。如果发生了,那么flag的值变化。如果没发生,就直接break循环,节省时间提高效率。
3.希尔排序属于高级排序方法,采用的是缩小增量的思想。在开始正式的排序之前(这个正式的排序可以理解为直接插入排序),先对序列中的一小部分进行排序,这个一小部分数量是由增量deta来控制的,然后一步一步缩小增量,直至增量为1,即演变为直接插入排序。到真正的直接插入排序的时候,前面已经做好了铺垫,根本不需要大费周章就可以完成排序。但值得注意的是:目前还没有选择增量函数的统一的好方法,但是我们要保证的是尽量让所有的增量互质。在进行正式的希尔排序之前,我们需要创建好增量数组,并且得到在增量数组的中元素的个数,这个个数就是我们对序列排序的总次数。
4.快速排序,顾名思义是所有排序方法中平均时间最短的。对它来说,原序列越乱它就越快,如果原序列本身就是有序的,反而不适合快速排序。快速排序的中心思想是首先任取一个元素为中心点pivot,假如就是第一个元素,然后以这个元素为中心,小于它的放左边,大于它的放右边,从而形成左右两个子表。然后利用递归的思想,再对左右两个子表进行快速排序,相同的流程。关键点是如何找到我选择的这个中心点的所在位置?这里采用的是挖坑法,具体看代码
5.选择排序很简单,不再赘述。
6.堆排序首先要理解小根堆和大根堆的含义,并且掌握如何把一个无序序列构建成小根堆(大根堆),然后怎么在排序的过程中调整堆。
7个排序代码都放在一起了
上代码:
#include <iostream> #include <algorithm> using namespace std; #define OK 1 #define ERROR 0 #define Status int typedef struct { int* data; //存储主要信息的数组 int length; //顺序表长度 int listSize; //空间大小 }SqList; //初始化顺序表 Status InitSqList(SqList& L) { L.data = (int *) malloc(100 * sizeof(int)); L.length = 0; L.listSize = 100; return OK; } //输入值到顺序表中 void CreatSqList(SqList& L) { cout << "请输入序列:(以-1为结束数字)" << endl; int i, index = 1; //0号位置作为哨兵 cin >> i; while (i != -1) { if (i != -1) { L.data[index] = i; index++; L.length++; cin >> i; } else break; } } //打印顺序表 void PrintSqList(SqList L) { cout << "顺序表为:" << endl; for (int i = 1; i <= L.length; i++) { cout << L.data[i] << " "; } cout << endl; } //直接插入排序 void DirectInsertSort(SqList& L) { int j; for (int i = 2; i <= L.length; i++) { //i从2开始 因为0作哨兵 1是起始元素 所以从2开始比较 if (L.data[i] < L.data[i - 1]) { //当i处的值小于i-1时才比较 否则根本不需要进行比较 这样节省了时间 L.data[0] = L.data[i]; //把要比较的第i个元素值给哨兵 for (j = i - 1; L.data[0] < L.data[j]; j--) { L.data[j + 1] = L.data[j]; //元素后移 } L.data[j + 1] = L.data[0];//插入到正确位置j+1上 } } } //折半查找排序 void HalfInsertSort(SqList& L) { for (int i = 2; i <= L.length; i++) { //依次插入2~n个元素 除了第一个 int low = 1, high = i - 1; L.data[0] = L.data[i]; //哨兵 while (low <= high) { int mid = (low + high) / 2; if (L.data[i] < L.data[mid]) high = mid - 1; else low = mid + 1; }//while结束后 high + 1或者low是插入位置 画图分析即可 for (int j = i - 1; j >= high + 1; j--) { //移动元素到low L.data[j + 1] = L.data[j]; } L.data[high + 1] = L.data[0]; }//for } //进阶版冒泡排序 void BubbleSort(SqList& L) { int tmp; //辅助变量 for (int i = 1; i < L.length; i++) { //注意 顺序表创建时 第一个位置没有用 所以从1开始 int flag = 0; for (int j = 1; j < L.length - i + 1; j++) { if (L.data[j] > L.data[j + 1]) { tmp = L.data[j]; L.data[j] = L.data[j + 1]; L.data[j + 1] = tmp; flag = 1; } } if (flag == 0) break; } } //希尔排序 void ShellInsert(SqList& L, int Increment) { int j; for (int i = Increment + 1; i <= L.length; i++) { // 一种增量对应的比较次数 if (L.data[i] < L.data[i - Increment]) { //当这种情况下才排序 L.data[0] = L.data[i]; for (j = i - Increment; j > 0 && (L.data[0] < L.data[j]); j = j - Increment) { L.data[j + Increment] = L.data[j]; //元素后移 } L.data[j + Increment] = L.data[0]; } } } void ShellSort(SqList& L) { int Increment[10]; //增量序列 int cnt = 0; //计算有几个增量 用于增量序列数组的元素个数 int i = L.length; while (i > 1) { i = i / 3 + 1; //计算增量 采用除3加1的方式 尽量让增量序列互质 Increment[cnt] = i; //给增量数组赋值 cnt++; } cout << "增量序列为:"; for (int j = 0; j < cnt; j++) cout << Increment[j] << " "; cout << endl; for (int j = 0; j < cnt; j++) { ShellInsert(L, Increment[j]); } } //快速排序 (挖坑法) int Partition(SqList& L,int low, int high) {//找到中心点的位置给主程序QuickSort int pivotValue = L.data[low]; //取出low位置的值为中心点值 可以想象为low处的值被挖空了 while (low < high) { while (low < high && L.data[high] > pivotValue) high--; //当循环跳出时 说明high处的值小于pivotValue了 所以放在左边挖空的地方 即low处 L.data[low] = L.data[high]; while (low < high && L.data[low] < pivotValue) low++; //当循环跳出时 说明low处的值大于pivotValue了 所以放在右边被挖空的地方 L.data[high] = L.data[low]; } //当整个循环结束时 low == high 这个位置就是我们要找的放置中心点的位置 我们先给这个地方填上值 L.data[low] = pivotValue; //low 或者 high 都可以 return low; } void QuickSort(SqList& L, int low, int high) { //快速排序的递归主体 if (low < high) { int pivot = Partition(L, low, high); QuickSort(L, low, pivot - 1); // 对左子表进行递归的快速排序 QuickSort(L, pivot + 1, high); // 对右子表进行递归的快速排序 } } //简单选择排序 void SelectSort(SqList& L) { for (int i = 1; i < L.length; i++) { int k = i; //辅助变量 用于记录最小值的位置 for (int j = i + 1; j <= L.length; j++) { if (L.data[j] < L.data[i]) k = j; //记录最小值的下标 } if (k != i) { int t; t = L.data[k]; L.data[k] = L.data[i]; L.data[i] = t; } } } //堆调整 void HeapAdjust(SqList& L, int front, int last) { /* * 已知R[front...last]中记录的关键字除了R[front]之外均满足堆的定义,本函数作用是调整R[front]关键字 * 使得R[front...last]成为一个小根堆 */ int cur = L.data[front]; //cur表示需要调整位置的结点 for (int i = 2 * front; i <= last; i *= 2) { //i从根节点的左孩子开始 到右孩子 if (i < last && L.data[i] > L.data[i + 1]) i++; //找到较小的那个 if (cur <= L.data[i]) break; //如果当前需要调整的小于较小的,直接break跳出循环,当前位置就是正确的 //如果当前的更大 就往下交换 L.data[front] = L.data[i]; front = i; //把当前需要调整的结点移动到i位置处 } L.data[front] = cur; } //堆排序 void HeapSort(SqList& L) { for (int i = L.length / 2; i >= 1; i--) { HeapAdjust(L, i, L.length); //从无序序列建立初始的小根堆 } for (int i = L.length; i > 1; i--) { swap(L.data[1], L.data[i]); //根与最后一个元素交换 //然后进行堆调整 HeapAdjust(L, 1, i - 1); } //进行完堆调整后 由于没有删除每一步最小的结点 所有它们都被存在了数组中 for (int i = L.length; i >= 1; i--) cout << L.data[i] << " "; cout << endl; } int main() { SqList L; InitSqList(L); CreatSqList(L); PrintSqList(L); cout << endl; int choice; while (1) { cout << "0.退出程序" << "\n1.进行直接插入排序" << "\n2.进行折半插入排序" << "\n3.进行冒泡排序" << "\n4.进行希尔排序" << "\n5.进行快速排序" << "\n6.进行选择排序" << "\n7.进行堆排序" << endl; cout << "请输入选择:"; cin >> choice; switch (choice) { case 0: cout << "已退出程序!"; exit(0); case 1: DirectInsertSort(L); PrintSqList(L); break; case 2: HalfInsertSort(L); PrintSqList(L); break; case 3: BubbleSort(L); PrintSqList(L); break; case 4: ShellSort(L); PrintSqList(L); break; case 5: QuickSort(L, 1, L.length); PrintSqList(L); break; case 6: SelectSort(L); PrintSqList(L); break; case 7: HeapSort(L); break; default: break; } } }
这篇关于对于给定的序列实现直接插入、折半插入、冒泡、希尔、快速、选择、堆排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)