「数据结构」八大排序(超详解 附动图 源码)(4)
2023-04-24 来源:飞速影视
代码如下:
// 希尔排序void ShellSort(int* a, int n){ assert(a); int gap = n; while (gap > 1) { //gap /= 2; gap = gap / 3 1; 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.5) 空间复杂度O(1) 稳定性:不稳定。
3.选择排序
基本思想:
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,
然后选出次小(或次大)的一个元素,存放在最大(最小)元素的下一个位置,
重复这样的步骤直到全部待排序的数据元素排完 。
动图演示:
![「数据结构」八大排序(超详解 附动图 源码)](http://fs.qqfile.top/re/aHR0cHM6Ly9waWMucm1iLmJkc3RhdGljLmNvbS9iamgvbmV3cy8zYjg1ZmQxOTIyOThkMWM2OTg5ZTMwYTQ1MmQyYWIyZC5naWY1)
代码入下:
这里我们可以进行一个优化,最小值和最大值同时选,然后将最小值与起始位置交换,将最大值与末尾位置交换。
// 选择排序void SelectSort(int* a, int n){ assert(a); int begin = 0;//保存数组的起始位置 int end = n - 1;//保存换数组的末尾位置 while (begin < end) { int maxi = begin;//保存最大元素下标 int mini = begin;//保存最小元素下标 //遍历数组寻找最小和最大元素 for (int i = begin; i <= end; i ) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //将最小元素交换到起始位置 Swap(a begin, a mini); //判断最大值的位置是否在起始位置 if (maxi == begin) { maxi = mini; } //将最大元素交换到末尾位置 Swap(a end, a maxi); //移动数组起始和末尾位置 begin ; end--; }}
本站仅为学习交流之用,所有视频和图片均来自互联网收集而来,版权归原创者所有,本网站只提供web页面服务,并不提供资源存储,也不参与录制、上传
若本站收录的节目无意侵犯了贵司版权,请发邮件(我们会在3个工作日内删除侵权内容,谢谢。)
www.fs94.org-飞速影视 粤ICP备74369512号