(一) 基本思想
希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整个文件恰被分成一组, 算法便终止.
(二) 例子
有一个数组, 其原始数组为:
2-1.png
取初始增量 gap = length / 2 = 5, 这样就将整个数组分为 5 组 (每组用相同的颜色表示)
2-2.png
将这 5 组的数据分别按由小到大的顺序排列, 结果为
2-3.png
缩小增量 gap = gap / 2 = 2, 整个数组被分成两组
2-4.png
将这两组的数据分别按由小到大的顺序排列, 结果为
2-5.png
再次缩小增量, 整个数组被分为 1 组
2-6.png
将这组数据按从小到大的顺序排序, 最终结果为
2-7.png
(三) 代码
1 C 语言实现
- #include<stdio.h>
- void swap(int &a, int &b)
- {
- a ^= b;
- b ^= a;
- a ^= b;
- }
- void shellsort(int a[], int n)
- {
- int i, j, gap;
- for (gap = n / 2; gap> 0; gap /= 2)
- {
- for (i = gap; i <n; i++)
- {
- for (j = i - gap; j>= 0 && a[j]> a[j + gap]; j -= gap)
- {
- swap(a[j], a[j + gap]);
- }
- }
- }
- }
- int main()
- {
- int arr[] = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
- printf("Original array:");
- int i;
- int len = sizeof(arr)/sizeof(int);
- for(i = 0; i <len; i++)
- {
- printf("%d", arr[i]);
- }
- printf("\n");
- shellsort(arr, len);
- printf("Sorted array:");
- for(i = 0; i < len; i++)
- {
- printf("%d", arr[i]);
- }
- printf("\n");
- return 0;
- }
2 Java 实现
- import java.util.Arrays;
- public class Sort {
- public static void shellSort(int[] a) {
- int i, j, gap;
- int len = a.length;
- for (gap = len / 2; gap> 0; gap /= 2) {
- for (i = gap; i <len; i++) {
- for (j = i - gap; j>= 0 && a[j]> a[j + gap]; j -= gap) {
- // 交换两个数
- a[j] ^= a[j + gap];
- a[j + gap] ^= a[j];
- a[j] ^= a[j + gap];
- }
- }
- }
- }
- public static void main(String[] args) {
- int[] arr = {49, 38, 65, 97, 76, 13, 27, 48, 55, 4};
- System.out.println("Original array:" + Arrays.toString(arr));
- shellSort(arr);
- System.out.println("Sorted array:" + Arrays.toString(arr));
- }
- }
3 运行结果
- Original array: [49, 38, 65, 97, 76, 13, 27, 48, 55, 4]
- Sorted array: [4, 13, 27, 38, 48, 49, 55, 65, 76, 97]
来源: http://www.bubuko.com/infodetail-2759532.html