当前位置 博文首页 > ice_elephant的博客：数据结构算法之希尔排序
插入排序虽好,但是某些特殊情况也有很多缺点,比如像下面这种情况:
156 161 163 165 167 168 169 1 2
169 前的元素基本不用插入操作就已经有序, 元素 1 和 2 的排序几乎要移动数组前面的所有
元素!!! 于是,有个老帅哥就提出了优化此问题的希尔排序!
希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排
序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。它与插入排序
的不同之处在于，它会优先比较距离较远的元素。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐
渐减少，每组包含的元素越来越多，当增量减至 1 时，所有元素被分成一组,实际上等同于执行一
次上面讲过的插入排序，算法便终止。
希尔排序的基本步骤 ：
选择增量 ：gap=length/2，缩小增量：gap = gap/2
增量序列：用序列表示增量选择，{n/2, (n/2)/2, …, 1}
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进
行直接插入排序;
仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
#include<stdio.h>
#include<iostream>
#include<Windows.h>
using namespace std;
//希尔排序
void sortShier(int *arr,int L){
//排序的次数为
int gap = L/2;
for(gap;gap>0;gap=gap/2){
//每次排序触及的次数
for(int i=0;i<gap;i++){
//元素的下标从i~i+L-gap
//开始进行插入排序,插入排序默认第一个有序
//这个地方有问题
//比较的步长为(L-gap)
/*for(int j=i+1;j<i+L-gap;j++){
//插入排序的第一个有序我们进行比较的次数为
if(arr[j+1]<arr[j]){
int temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}*/
//只需做好每一次的排序就ok了
//以最后一次为例
//每一个大循环有其实的元素个数为 (L-gap)+1个
}
}
}
void Shier(int *arr,int Length){
int gap = Length/2;
for(gap;gap>0;gap=gap/2){
for(int i=gap;i<Length;i++){
int current = arr[i];//代表的是最左边的那个
int j = 0;
for(j = i-gap;arr[j]>current&&j>=0;j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = current;
}
}
}
int main(void){
int beauty[]={163,161,158,165,171,170,131,1,2};
int L = sizeof(beauty)/sizeof(beauty[0]);
Shier(beauty,L);
for(int i=0;i<L;i++){
cout<<beauty[i]<<" ";
}
printf("\n");
system("pause");
return 0;
}
