希尔排序

发表于 分类于 Waline：

希尔排序

希尔排序的思想是按照下标的一定增量分组，对魅族使用直接插入排序算法进行排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减少到1时，整个文件恰好被分成一组，算法终止。
简单来说就是按照一定步长分组，例如100个数排序，第一次分50组，每组两个数，第二次分25组，每组4个数，第三次分12组，第四次分6组，第五次分3组，第六次分1组。每一次分组后在组内进行排序。

排序流程：

代码实现：

首先分组，然后使用交换法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void shellSort(int[] arr) {
    // 第一个循环，对数组进行分组，直到gap=1为止
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        //交替遍历所有组
        for (int i = gap; i < arr.length; i++) {
            // 组内排序，使用交换法
            for (int j = i - gap; j >= 0; j -= gap) {
                if (arr[j] > arr[j + gap]) {
                    arr[j] = arr[j] ^ arr[j + gap];
                    arr[j + gap] = arr[j] ^ arr[j + gap];
                    arr[j] = arr[j] ^ arr[j + gap];
                }
            }
        }
    }
}

使用交换法，每次对比都要进行交换，效率比较低，内部排序的方式可以修改成直接插入排序。

分组，然后插入法（希尔排序）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void shellSort2(int[] arr) {
    // 第一个循环，对数组进行分组，直到gap=1为止
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 交替遍历所有的组
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                // 移动数据，等待插入
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 找到待插入的位置，插入数据
                arr[j] = temp;
            }
        }
    }
}

希尔排序是对直接插入排序的更高效的改进版本，