全国咨询热线:400-618-4000

c++培训之希尔排序

更新时间:2019年05月19日23时10分 来源:传智播客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/