dede网站备份,八戒logo设计网,松江企业网站建设,石家庄网站建设培训班目录#xff1a;
一、希尔排序与插入排序 1#xff09;希尔排序的概念 2#xff09;插入排序实现
二、希尔排序实现 一、希尔排序与插入排序 1#xff09;希尔排序的概念 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”#xff08;Diminishing Incremen…目录
一、希尔排序与插入排序 1希尔排序的概念 2插入排序实现
二、希尔排序实现 一、希尔排序与插入排序 1希尔排序的概念 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”Diminishing Increment Sort是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。 2插入排序实现 既然希尔排序是插入排序的优化那么我们有必要先了解一下插入排序的过程基本操作是将需要进行排序的元素插入到已排序区当中这样每次插入都会使已排序区长度加一。 直观的看插入排序的操作就和我们在打扑克牌时一样我们默认将小的或者大的往一边插进去插入排序也是如此。 1、我们从第二个元素开始插入排序因为这样左边只有一个数必然有序我们把左边的称为已排序区右边的称为待排序区。 2、将待排序区的第一个元素向已排序区插入将其与已排序区元素从后向前比较将其插入到合适位置已排序区元素个数1。 3、然后待排序区重复2的步骤向已排序区从后往前比较找到合适位置插入。 4、 继续将待排序区元素插入到已排序区当待排序区元素为0时这组数据就已经排序完成。 我们明白了插入排序的过程接下来就是实现插入排序了我们先来分析插入排序中第一个元素(0位置处)本来就是有序的所以我们直接从第二个元素开始操作1位置处。 1、定义待排序区的首元素下标为end,用tmp记录下end下标的元素将tmp与已排序区元素进行比较发现小于5则将待排序区的元素插入到首元素位置。 2、已排序区数组元素加一待排序区首元素变为3end也变为3的下标tmp记录此元素的值将tmp与已排序区元素进行比较首先与5比较小于5。 3、再跟1比较发现大于1那么这个值就插入在1和5之间已排序元素加一待排序数组元素减一。 4、一直刷新end与tmp值与已排序区进行从右往左的比较比较到合适的位置才进行插入而不是每次比较都插入元素。 时间复杂度最坏情况下为 O(N^2)此时待排序列为逆序或者说接近逆序。最好情况下为 O(N)此时待排序列为升序或者说接近升序。平均为O(N^2)。 空间复杂度没有额外使用空间所以空间复杂度为 O(1)。 代码实现
#includestdio.h
#includestdlib.h
#includestring.h
#includeassert.hvoid InsertSort(int *a, int len)//插入排序
{int i 0;for(i 1 ; i len ; i)//从下标为1的位置进行插入排序{int end i;//用end记录待排序区的首元素下标int tmp a[end];//用tmp记录待排序区首元素的值while(end 0)//保证不越界tmp就一直往前进行比较找到合适的位置break{if(a[end - 1] tmp){a[end] a[end - 1];end--;}else{break;}}a[end] tmp;//最后在将tmp值放在end的下标下}
}void Print(int *a, int len)//打印数组元素
{int i 0;for(i 0 ; i len ; i){printf(%3d,a[i]);}printf(\n);return;
}void Test()//测试
{int a[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };int len sizeof(a) / sizeof(int);InsertSort(a, len);Print(a, len);return;
}int main()
{Test(); return 0;
}
运行结果 二、希尔排序实现 希尔排序法又称为缩小增量法。希尔排序法的基本思想是首先选定一个整数把待排序文件中所有记录分成gap个组增量所有距离为gap的数据记录在同一组内并对每一组内的记录进行排序。然后再取gap/2个组缩小增量重复上述分组和排序的工作。当gap 1时所有记录在统一组内排好序。 注希尔排序缩小增量在数学上是个难题大家经常用的就是gap/2。 我们有这样一个数组a[] {6, 1, 5, 2, 4, 8, 3, 7, 9}。我们对这个数组进行排序首先假设设置gap的值为3那么这组数就会分为三组 接下来控制这三组每组分别进行插入排序结果为 那么gap为3时的所有组已经排完了接下来就该缩小增量了gap / 2gap 1: 知晓了希尔排序是如何进行数据管理的下面来看看具体的操作是如何完成的 1、首先 我们需要对gap进行控制在gap0范围内每次分组后的所有组排完序之后都要除以二可以用while循环来控制gap的大小
void ShellSort(int *a, int n)
{assert(a);int gap n;int i 0;while(gap 1){if(gap 1)gap / 2;//..分完组后的预排序 }
} 2、我们已经将缩小增量设置好了接下来只需要把每次分完组都进行排序也就是预排序。如何进行预排序呢既然希尔排序是插入排序的优化我们不妨以插排的思路对希尔预排序进行调整。 用for循环对所有数据进行预排序值得注意的是这里不会像插排那样循环到n我们只需要限制在n - gap 的范围就行了例如上图 这个数组从3往后就不需要排了因为在每一组的排序中最后一个值都是被拍过序的没必要再次进行一次排序总共为n个数据那么就是只需要n - gap - 1个数据进行排序。则
void ShellSort(int *a, int n)
{assert(a);int gap n;int i 0;while(gap 1){if(gap 1)gap / 2;for(i 0 ; i n - gap ; i)//控制n - gap数据进行预排序{//具体排序过程...}}
} 3、其实预排序的实现和直接插入排序的过程几乎是完全相似前面也说了当希尔排序的缩小增量为1时和插入排序没区别也就是说插入排序每次都对相邻的数据处理而希尔排序是将分好的组看成新的数组例如上面数据的6 2 3为一组我们可以看成其他的数据不存在只有这一组存在那么对于这一组而言希尔排序就是插入排序将上图的三组都排完序这一趟预排序就算完成了。 与插入排序相同定义一个end记录当前元素下标定义一个tmp记录a[end gap]处的值为什么不是a[end]处的值可别忘了第一个值是默认有序的所以要从第二个值向前比较当end对应的值要大于tmp那么就将end处的值赋给下一个位置也就是endgap处当不满足end处的值大于endgap时代表前面已经没有比自己大的值了直接break最后在循环结束的时候记得将a[end gap]之前被覆盖的地方重新赋值
void ShellSort(int *a, int n)
{assert(a);int gap n;int i 0;while(gap 1){if(gap 1)gap / 2;for( i 0; i n - gap; i)//对n组数据进行n - gap次预排序{int end i;int tmp a[gap end];while(end 0)//当end 0时候对每组进行预排序{if(tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}return;
} 这样希尔排序就完成了其实在希尔排序的过程中或许你还有疑问为什么for循环这里是连续的不是进行分组了吗其实你仔细想想 我们还是以上面gap3为例首先是第一个数据就是对第一组的首个数据进行排序当到了第二个数据的时候就是对第二组首个数据进行排序但是因为有gap的控制这两组数据其实是互不影响的所以连续的遍历数据进行预排序也是没有问题的。 总结希尔排序的特性 1、希尔排序是对直接插入排序的优化。 2、当gap 1时都是预排序目的是让数组更接近有序当gap1时将前面预排序的结果进行直接插入排序而完成排序。 时间复杂度O(NlogN)近似因为增量问题并不能准确得出时间复杂度。 空间复杂度没有开额外的空间所以空间复杂度为O(1)。 以下是希尔排序的完整代码
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.hvoid ShellSort(int *a, int n)
{assert(a);int gap n;int i 0;while(gap 1){if(gap 1)gap / 2;for( i 0; i n - gap; i)//对n组数据进行n - gap次预排序{int end i;int tmp a[gap end];while(end 0)//当end 0时候对每组进行预排序{if(tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}return;
}void Print(int *a, int n)
{assert(a);int i 0;for(i 0 ; i n ; i){printf(%d ,a[i]); }printf(\n);return;
}int main()
{int a[] {5,6,1,2,7,4,8,3,9};int len sizeof(a) / sizeof(int);ShellSort(a, len);Print(a, len);return 0;
} 如果这篇文章对你有帮助的话还望各位佬能多多三连~~[doge][玫瑰]
