西宁网站建设费用,网站中全景是怎么做的,1.网站建设分为哪几个阶段,网站规范建设文章目录 前言一、直接插入排序1、基本思想2、直接插入排序的代码实现3、直接插入排序总结 二、希尔排序1、希尔排序基本思想2、希尔排序的代码实现3、希尔排序时间复杂度 前言
排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大… 文章目录 前言一、直接插入排序1、基本思想2、直接插入排序的代码实现3、直接插入排序总结 二、希尔排序1、希尔排序基本思想2、希尔排序的代码实现3、希尔排序时间复杂度 前言
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 一、直接插入排序
1、基本思想
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 例如当有如下一组有序的数组。当分别将10、5、0按照插入排序的思想插入到数组中时 此时插入的数据要与数组最后一位进行比较如果比最后一位大就插入到数组最后一位的后面 如果比数组中最后一位小就将数组中最后一位元素向后移一位然后插入的数据与倒数第二个数据进行比较就这样依次循环下去 。 如果插入的数据比数组中所有数据都小此时插入的数据会被插入到数组下标为0的位置即作为数组的第一个元素。 上述的操作就是插入排序的单趟排序即在有序区间插入一个数使这个区间继续有序。
2、直接插入排序的代码实现
直接写出来插入排序来将数组排序比较困难我们可以先写出来单趟排序即当有一个数组的[0,end]有序把end1位置的值插入数组中然后保持数组的[0,end1]有序。 例如有如下数组。 此时数组中end1的值为5该值小于数组中end位置的值此时就用tmp记录end1位置的值然后将end的值向后移一位移到end1位置。然后将end–此时再将end位置的值与tmp比较。 此时end位置的值比tmp小则说明tmp的值就应该插入到end位置之后此时直接将end1位置赋值为tmp即可。然后数组中[0,end1]有序。 上述就是单趟排序。
void InsertSort(int* arr, int n)
{//[0,end]有序把end1位置的值插入保持有序int end;//将tmp赋值为数组中下标为end1位置的值int tmp arr[end 1];//如果end没有到数组头部就继续比较while (end 0){//如果tmp小于arr[end]就将此时end的数据向后移然后将end--使tmp与新的end位置的值比较if (tmp arr[end]){arr[end 1] arr[end];end--;}else{//如果满足条件就跳出循环break;}}//此时end为数组中第一个小于tmp的位置此时将end1位置赋值为tmp。//如果当end为-1时即插入的数据tmp比数组头元素还小此时end1刚好为0即让插入的数据tmp作为新的数组头部。arr[end 1] tmp;
}通过上述的操作我们明白了插入排序排序数组时的单趟操作当我们有一个长度为n的数组arr时我们先将end置为0然后依次将数组首元素之后的元素依次进行插入当end为n-2时此时end1为n-1即为数组最后一个元素的插入。我们就可以再写一个循环将上面的代码套入其中并且控制end的值从0到n-2。
void InsertSort(int* arr, int n)
{int i 0;//控制end的值将数组中的元素从首元素后面开始依次进行插入。for (i 0; i n-1; i){//[0,end]有序把end1位置的值插入保持有序int endi;//将tmp赋值为数组中下标为end1位置的值int tmp arr[end 1];while (end 0){//如果tmp小于arr[end]就将此时end的数据向后移然后将end--使tmp与新的end位置的值比较if (tmp arr[end]){arr[end 1] arr[end];end--;}else{break;}}//此时end为数组中第一个小于tmp的位置此时将end1位置赋值为tmp。//如果当end为-1时即插入的数据tmp比数组头元素还小此时end1刚好为0即让插入的数据tmp作为新的数组头部。arr[end 1] tmp;}}3、直接插入排序总结
直接插入排序的特性总结 1.元素集合越接近有序直接插入排序算法的时间效率越高 2.时间复杂度O(N^2) 3.空间复杂度O(1)它是一种稳定的排序算法 4.稳定性稳定 直接插入排序的最坏时间复杂度为O(N^2)即当数组为逆序时。 最优时间复杂度为O(N)即当数组为顺序有序/接近顺序有序。
二、希尔排序
由上面总结的直接插入排序的最优时间复杂度可知当数组的顺序接近有序时直接插入排序的性能可以得到提高并且能达到O(N)的级别而希尔排序就是利用了这一点。
1、希尔排序基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成gap个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后gapgap/gap取gap重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 希尔排序分为两步。 1、预排序(接近顺序有序) 2、直接插入排序(有序) 例如有如下的一组逆序的数据。 假设gap为3即将该组数据分为如图所示的三组数据 然后将这三组数据分别进行直接插入排序此时该组数据的排序虽然没有达到顺序有序但是相比于原来的逆序此时该组数据已经接近顺序有序。 此时将该组数据总体进行直接插入排序这样相比于原来逆序时就直接进行直接插入排序效率提高了很多。并且我们可以看出当gap1时此时就是进行直接插入排序。
2、希尔排序的代码实现
我们可以像实现直接插入排序一样先了解希尔排序的一组数据中的单趟排序。 即将分成的3组数据的红色组数据先进行直接插入排序。
此时将endgap位置的值赋值为end位置的值。 然后end end - gap此时end已经为负数但是endgap为0刚好为数组的首位所以将arr[endgap]的位置存入tmp即将tmp插入到数组的首位。 下列代码就实现了上述的操作。
void ShellSort(int* arr, int n)
{int gap 3;int end 0;//将tmp赋值为数组中end位置后gap位置的值int tmp arr[end gap];while (end 0){//如果tmp的值小于此时end位置的值if (tmp arr[end]){//就将endgap位置的值赋值为end位置的值arr[end gap] arr[end];//然后将end向后移gap个距离继续和tmp比较end - gap;}else{break;}}//此时end位置的值是小于tmp的将endgap位置的值赋值为tmparr[end gap] tmp;
}但是上述代码只是将红色数组中的一个数据完成了直接插入排序下面我们要将红色数组的数据都进行直接插入排序则需要加一个循环然后使end的值每次都向后改变。
void ShellSort(int* arr, int n)
{int gap 3;int i 0;for (i 0; i n - gap; i gap){int end i;//将tmp赋值为数组中end位置后gap位置的值int tmp arr[end gap];while (end 0){//如果tmp的值小于此时end位置的值if (tmp arr[end]){//就将endgap位置的值赋值为end位置的值arr[end gap] arr[end];//然后将end向后移gap个距离继续和tmp比较end - gap;}else{break;}}//此时end位置的值是小于tmp的将endgap位置的值赋值为tmparr[end gap] tmp;}}上述代码只是将红色数组完成了直接插入排序但是蓝色数组和紫色数组还没有完成直接插入排序所以需要再次套入一个循环将蓝色数组和紫色数组也完成直接插入排序操作。此时才算将gap组数都分别在各自组内进行了直接插入排序此时数组arr中的数据接近顺序有序。
void ShellSort(int* arr, int n)
{int gap 3;int i 0;for (i 0; i gap; i){int j 0;for (j i; j n - gap; j gap){int end j;//将tmp赋值为数组中end位置后gap位置的值int tmp arr[end gap];while (end 0){//如果tmp的值小于此时end位置的值if (tmp arr[end]){//就将endgap位置的值赋值为end位置的值arr[end gap] arr[end];//然后将end向后移gap个距离继续和tmp比较end - gap;}else{break;}}//此时end位置的值是小于tmp的将endgap位置的值赋值为tmparr[end gap] tmp;}}
}上述代码嵌套了三层循环会让人觉得循环太多其实可以将外面的循环去掉然后将第二层循环的i gap变为i。达到的效果和上面的代码一致上面代码是将gap组数依次进行直接插入排序而这个代码是将第一组数的一个进行直接插入排序后然后将第二组数进行直接插入排序然后将第三组数进行直接插入排序。这样两个代码达到的效果是一样的。
void ShellSort(int* arr, int n)
{int gap 3;int j 0;for (j 0; j n - gap; j ){int end j;//将tmp赋值为数组中end位置后gap位置的值int tmp arr[end gap];while (end 0){//如果tmp的值小于此时end位置的值if (tmp arr[end]){//就将endgap位置的值赋值为end位置的值arr[end gap] arr[end];//然后将end向后移gap个距离继续和tmp比较end - gap;}else{break;}}//此时end位置的值是小于tmp的将endgap位置的值赋值为tmparr[end gap] tmp;}
}到这里只完成了希尔排序的第一个步骤即预排序而想要将数组中的数据都有顺序还需要将数组进行直接插入排序。预排序的目的是让数组中的数据达到基本顺序有序这样使用直接插入排序对数组排序时效率就会提高。 希尔排序的gap该怎么选择呢 由上面我们可以直到当排升序时gap越大大的数更快到后面小的数可以更快到前面但是越不接近有序。 排升序时gap越小越接近有序当gap1时就是直接插入排序。 当数组中数据为10000个时此时如果选择gap3则预排序和进行直接排序插入的复杂度差不多。当数组中数据为100个时此时将gap30则经过预排序后数组中的数据还是没有达到基本顺序有序。 此时我们可以将gap设置为一个变化的值。
void ShellSort(int* arr, int n)
{int gap n;int j 0;//gap1时都为预排序并且随着gap越来越小数组越来越接近有序while (gap 1){//随着gap越来越小数组中的数据越接近有序当gap1时就是直接插入排序gap gap / 3 1; // gap / 3 1保证了最后一次gap1即最后一次为直接插入排序for (j 0; j n - gap; j){int end j;//将tmp赋值为数组中end位置后gap位置的值int tmp arr[end gap];while (end 0){//如果tmp的值小于此时end位置的值if (tmp arr[end]){//就将endgap位置的值赋值为end位置的值arr[end gap] arr[end];//然后将end向后移gap个距离继续和tmp比较end - gap;}else{break;}}//此时end位置的值是小于tmp的将endgap位置的值赋值为tmparr[end gap] tmp;}}}3、希尔排序时间复杂度
希尔排序的时间复杂度很难求我们只需记住它的时间复杂度接近于O(N^1.3)。 《数据结构(C语言版)》— 严蔚敏
