希尔排序

2021-05-01 10:29

阅读：494

标签：loading include stream sort i++ 有序 namespace col 数据

稳定性：不稳定排序

1.过程介绍

希尔排序，又名递减增量排序算法，是一种非稳定的更高效的插入排序，在对几乎已经排好序的数据操作时，效率极高，即可以达到线性排序的效率，直接插入排序整体来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

过程如下：

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列个数 k，对序列进行 k 趟排序；

3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2. 图示过程

技术图片

可以见的，相比直接插入排序由于可以每趟进行分段操作，故整体效率体现较高。

3. 相关的代码

 1 #include 2 using namespace std;
 3 void shellSort(int arr[], int n) {
 4     int i, j, gap;
 5     for (gap = n / 2; gap > 0; gap /= 2) {
 6         for (i = 0; i ) {
 7             for (j = i + gap; j  gap) {
 8                 for (int k = j; k > i && arr[k]  gap) {
 9                     swap(arr[k-gap], arr[k]);
10                 }
11             }
12         }
13     }
14 }
15   
16 int main() {
17     int a[8]= {70,50,30,20,10,70,40,60};
18     int n=8;
19     shellSort(a,n);
20     for(int i=0; i) {
21         cout‘ ‘;
22     }
23     return 0;
24 }

输出：

1 10 20 30 40 50 60 70 70

希尔排序

标签：loading include stream sort i++ 有序 namespace col 数据

原文地址：https://www.cnblogs.com/qunxuan/p/13219398.html

上一篇：分治算法之快排和归并

下一篇：哈希算法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：希尔排序
文章链接：http://soscw.com/index.php/essay/80830.html

亲，登录后才可以留言！

希尔排序

3. 相关的代码

评论

热门文章

推荐文章

最新文章

置顶文章