强化网站建设和管理,整站优化的公司,品牌红酒网站建设,做网站的哪里便宜文章目录排序的概念和运用排序的概念排序运用常见的排序算法常见的排序算法直接插入排序希尔排序性能对比排序的概念和运用
排序的概念 排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操…
文章目录排序的概念和运用排序的概念排序运用常见的排序算法常见的排序算法直接插入排序希尔排序性能对比排序的概念和运用
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
排序运用
在生活中排序有很多运用比如说购物按照价格排序全国高校排序等等 常见的排序算法
插入排序直接插入排序希尔排序选择排序选择排序堆排序交换排序冒泡排序快速排序归并排序计数排序 常见的排序算法
// 常见排序算法接口
// 插入排序
void InsertSort(int* a, int n);// 希尔排序
void ShellSort(int* a, int n);// 选择排序
void SelectSort(int* a, int n);// 堆排序
void HeapSort(int* a, int n);// 冒泡排序
void BubbleSort(int* a, int n);// 快速排序
void QuickSort(int* a, int left, int right);// 归并排序
void MergeSort(int* a, int n);// 计数排序
void ConutSort(int* a, int n);// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N 10000000;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);
}
直接插入排序
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。
这和在现实生活中我们玩扑克牌很像我们在整理牌的时候每一次拿一张牌插入之前已经有序的牌中一直整理到最后一张让整体的牌有序。 动图演示 参考代码
// 直接插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int x a[end 1];while (end 0){if (a[end] x){a[end 1] a[end];end--;}else{break;}}a[end 1] x;}
}直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度 O(N^2)空间复杂度 O(1)稳定性稳定
直接插入排序的时间复杂度进行分析可以得出一下结论
普通插入排序的时间复杂度最坏情况下为O(N^2)此时待排序列为逆序或者说接近逆序。普通插入排序的时间复杂度最好情况下为O(N)此时待排序列为升序或者说接近升序。 希尔排序
希尔排序法又称缩小增量法。 希尔排序法的基本思想是 先选定一个整数为gap把待排序文件中所有记录分成个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后缩小gap的值重复上述分组和排序的工作。当到达gap1时相当于直接插入排序因为此时序列经过了分组预排序序列的数据已经接近有序此时再进行直接插入排序时间复杂度相当于O(N)所有记录在统一组内排好序。
动图演示
参考代码
void ShellSort(int* a, int n)
{// 1. 分组预排序 gap 1// 2. 整体插入排序 gap 1int gap n;while (gap 1){gap gap / 2;for (int i 0; i n - gap; i){int end i;int x a[end gap];while (end 0){if (a[end] x){a[end gap] a[end];end - gap;}else{break;}}a[end gap] x;}}
}希尔排序的特性总结 希尔排序是对直接插入排序的优化。 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算很多书给出了不同的时间复杂度平均时间复杂度O(N^1.3) 《数据结构(C语言版)》 — 严蔚敏 《数据结构-用面相对象方法与C描述》 — 殷人昆 稳定性不稳定 性能对比
使用直接插入排序和希尔排序进行十万个随机数排序
测试程序
// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);free(a1);free(a2);}测试结果 可以看到希尔排序对于直接插入排序的优化很明显。
