希尔排序
希尔排序是对插入排序的一种改进,它其实是先将整个序列分为一些子序列,然后分别对这些子序列进行排序,排序后之后,再将整个序列分为比前一次序列规模大的子序列,再对这些子序列进行排序,继续这样的操作。直至将整个序列只分为一个子序列,即序列本身。希尔排序其实上是将整个序列慢慢变的基本有序。
希尔排序比较重要的是增量序列。它利用增量序列将整个序列分割为多个子序列。
比如有序列{3, 6, 10, 4, 2, 5, 9, 7, 8, 12, 1, 11} 增量序列为{5, 3, 2, 1}
则先根据增量5分割序列为{3, 5, 1}, {6, 9, 11}, {10, 7}, {4, 8}, {2, 12}并对这些子序列进行排序。{1, 3 ,5}, {6, 9, 11}, {7, 10}, {4, 8}, {2, 12},则整个序列变为{1, 6, 7, 4, 2, 3, 9, 10, 8, 12, 5, 11}。
接下来,根据增量3分割序列为{1, 4, 9, 12}, {6, 2, 10, 5}, {7, 3, 8, 11},排序后为{1, 4, 9, 12}, {2, 5, 6, 10}, {3, 7, 8, 11},则整个序列为{1, 2 ,3 ,4 ,5 ,7 ,9, 6, 8, 12, 10, 11}。
然后根据增量2分割序列{1, 3, 5 ,9, 8, 10}, {2, 4, 7, 6, 12, 11},排序后为{1, 3, 5, 8, 9, 10}, {2, 4, 6, 7, 11, 12},则整个序列为{1, 2, 3, 4, 5, 6, 8, 7, 9, 11, 10 ,12}。
最后增量为1,对整个序列进行排序。最终排序结果为{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}。
typedef int datatype;
int ShellSort(datatype *array, int size)
{
int i, j, temp;
int increment = size;
if(array == NULL) {
return -1;
}
while(increment > 1) {
//比如数组长度为12,则增量序列为{5, 2, 1}
increment = increment / 3 + 1;
for(i = increment; i < size; i++){
temp = array[i];
//对子序列进行排序
for(j = i-increment; j >= 0; j -= increment) { if(temp >= array[j]) {
break;
}
array[j+increment] = array[j];
}
array[j+increment] = temp;
}
}
return 0;
}