全国咨询/投诉热线:400-618-4000

c++培训之希尔排序

更新时间:2016年07月27日17时58分 来源:传智播客C/C++学科 浏览次数:

希尔排序是D.L.Shell于1959年提出来的一种排序算法,在这之前的算法的时间复杂度为O(n²),希尔排序算法是突破这个时间复杂度的第一批算法之一.
希尔算法基于一种增量序列,将待排序序列分组,分别对每一组进行插入排序。希尔排序在随机情况下,算法的效率表现很优秀。
回顾之前讲过的插入排序,插入排序在序列元素较少的情况下,序列基本有序的情况下效率较高,希尔排序在插入排序基础上去实现这两种苛刻的要求,也就是使得每一次进行插入排序的待排序序列元素个数较少,并使得整体元素更加有序。
使得待排序序列元素减少,那么可以使用分组,分组的策略是基于增量,可理解为相差固定个数的的元素组成组,分别对每一组进行排序,每一组的元素个数就会减少。每一组的元素趋于有序,那么整个待排序序列也越来越趋于有序。
我们在说到分组时,提到增量,因为增量关系到要分多少组,这个增量的算法至今没有确切的答案,但是根据行业经验,增量 = 数据个数 / 3 + 1.
在进行希尔排序中,这个增量循环调用这个增量计算公式递减,直至增量为1时,对所有元素进行最后一次插入排序。
希尔排序是不稳定的排序算法,希尔排序平均时间复杂度n*log2n,最坏时间复杂度为O(n²)。下面我们来介绍希尔排序:
 

待排序序列为:9,1,5,8,3,7,4,6,2,当增量为3时,将待排序序列分为3组:
第一组:9,8,4
第二组 : 1,3,6
第三组 : 5,7,2
分别对每一组进行插入排序,排序后结果为:4,1,2,8,3,5,9,6,7
递减增量为2,再分组:
第一组:4,2,3,9,7
第二组:1,8,4,6
分组对这两组进行排序,排序后结果为: 2,1,3,5,4,6,7,8,9
继续递减增量为1,对整体数据进行一次插入排序,排序结果为:
1,2,3,4,5,6,7,8,9
实现代码为:
void PrintArray(int arr[], int len){
for (int i = 0; i < len; i++){
printf("%d ", arr[i]);
}
printf("\n");
}
//希尔排序
void ShellSort(int arr[], int len){
 
int increasement = len;
do{
 
//通过算法递减增量
increasement = increasement / 3 + 1;
//获得每一组的第一个元素下标
for (int i = 0; i < increasement; i++){
//根据第一个元素下标+增量,遍历每一组元素
for (int j = i + increasement; j < len; j += increasement){
//对当前组进行插入排序
if (arr[j] < arr[j - increasement]){
 
int temp = arr[j];
int k = j - increasement;
for (; k >= i && temp < arr[k]; k -= increasement){
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
 
}
 
}
 
}
 
} while (increasement > 1);
}
int main(){
 
int arr[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 };
int len = sizeof(arr) / sizeof(int);
//排序前打印
PrintArray(arr, len);
ShellSort(arr, len);
//排序后打印
PrintArray(arr, len);
 
return EXIT_SUCCESS;
}


本文版权归传智播客C++培训学院所有,欢迎转载,转载请注明作者出处。谢谢!
作者:传智播客C/C++培训学院
首发:http://www.itcast.cn/c/ 
 

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额