首页C/C++技术文章正文

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/

上一篇：c++培训之指针的三点精华 下一篇：黑马程序员C/C++：C++学科推出全新三大实战项目