双流规划建设管理局网站,沧州高端网站建设公司,DANI主题wordpress,广州网站建设 企业目录 1. 排序的概念#xff1a;
2.插入排序基本思想
3.直接插入排序
4.希尔排序 1. 排序的概念#xff1a;
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。
稳定性#xf…目录 1. 排序的概念
2.插入排序基本思想
3.直接插入排序
4.希尔排序 1. 排序的概念
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的;否则称为不稳定。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 2.插入排序基本思想
直接插入排序是一种简单的插入排序法其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 实际中我们玩扑克牌时就用了插入排序的思想 3.直接插入排序
直接插入排序InsertSort当插入第i(i1)个元素时前面的array[0]array[1]...aray[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2.]..的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。
直接插入排序图解 代码实现思路 假设在数组arr中[0end]这段区间是有序的我们要将 end1 位置处的元素插入就需要将arr[end1]与前面元素从后往前依次作比较如果要排成升序前面元素比arr[end1]大的就往后移动大或者等于就放在这个元素后面。数组一共有n个元素要排n-1次因为第一个元素不用排从第二个元素开始。 代码
//直接插入排序 升序
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 (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
直接插入排序的特性总结:
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性:稳定
4.希尔排序
希尔排序法ShellSort又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达gap1时所有记录已经在组内排好序。
希尔排序是对直接插入排序的优化因为直接插入排序处理接近有序的元素集合时效率会很高接近O(N)。当gap 1时都是预排序目的是让数组元素更接近于有序。当gap 1时就和直接插入排序相同了数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 代码实现思路
我们先要实现预排序使数组元素集合接近有序。我们先假设gap3。实现预排序有两种方式一种是分组排序排好一组再排下一组另外一种是多组并排。这两种方法内部还是直接插入排序。大家可以和上面直接插入排序的代码对比一下。
分组排序代码
//预排序 一组一组预排
void BeforeSort1(int* arr, int n)
{//假设gap 3,分为3组每组n/3个元素int gap 3;for (int j 0; j gap; j){//每组内部进行排序for (int i j; i n - gap; i gap){int end i;int tmp arr[i gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}
多组并排代码可以对比一下上面代码。
//预排序 多组并排
void BeforeSort2(int* arr, int n)
{//假设gap 3,分为3组每组n/3个元素int gap 3;for (int i 0; i n - gap; i){int end i;int tmp arr[i gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
其实预处理不是简单的只处理一次而是处理多次让数据更加接近有序。最开始gap最大之后gap每次逐渐减小直至gap1。
gap越大大的数可以更快的到后面小的数可以更快的到前面数据越不接近有序gap越小大的小的数据挪动越慢但是他越接近有序gap 1就是直接插入排序
我们这里让gapn 每次预排让 gap gap/31确保最后可以得到1。
希尔排序代码实现对于gap的取法我们下面会讲到。
// 希尔排序 升序
void ShellSort(int* a, int n)
{int gap n;while (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;}}
}
关系希尔排序的时间复杂度以及gap的取法问题
资料中是这样讲的
《数据结构(C语言版)》--- 严蔚敏《数据结构-用面相对象方法与C描述》--- 殷人昆 因为我们这里使用的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时时间复杂度就按照O(N^1.25)到O(1.6 * N^1.25)来算。
稳定性:不稳定。
本篇结束
