手把手搭建千万级Java算法测试-希尔排序

本文已参加[新人创造礼]活动，一起开启创造之路。

第二天开端呢，咱们解说希尔排序算法，从算法思路，到算法伪代码完成，到复杂度剖析，从这儿开端咱们手把手搭建一个测验渠道的根底，根据你本身硬件水平能够对下列代码进行从1000，到千万级测验，其中算法测验时刻与你的机器硬件水平和完成的算法有联系，下面是希尔算法的详细解说。

（1）排序算法的思路并且举例说明

希尔排序思维：先将整个待排序列分割成若干个子序列，分别进行直接插入排序，待将整个序列中的记载“基本有序”时，再对全体记载进行一次直接插入排序。

例如： 3 2 6 1 7 4

第一次排序： 1 2 4 3 7 6

第2次排序： 1 2 4 3 7 6

第三次排序： 1 2 3 4 6 7

（2）算法伪代码

	ShellSort(int a[], int n) {
	int d, i, j;
	for (d = n / 2; d >= 1; d = d / 2) {
		for (i = d + 1; i <= n; ++i) {
			if (a[i] < a[i - d]) {
				a[0] = a[i];
				for (j = i - d; j > 0 && a[0] < a[j]; j -= d) {
					a[j + d] = a[j];
				}
				a[j + d] = a[0];
			}
		}
	}
}

（3）复杂度剖析

均匀时刻复杂度：O(nlgn)

最好时刻复杂度：O(n)

最差时刻复杂度：O(n2)

空间复杂度：O(1)

稳定性：不稳定

（4）代码主体部分

package runoob;
/**
 * 希尔排序
 */
public class ShellSort {
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
    public static void ShellSort_text(long num) {
        long start,end;
        Integer[] arr = SortHelper.generateRandomArray(num, 0, 10);//随机生成数组类
        start = System.currentTimeMillis();
        ShellSort.sort(arr);
        end = System.currentTimeMillis();
        System.out.println("花费时刻:" + (end - start) + "(ms)");
        System.out.println("下面是排序好的数列");
        SortHelper.printArray(arr);
    }
}

对应代码中的SortHelper类咱们留一个小小的悬念，留到最后来进行叙说，其中目前来说他的办法generateRandomArray的参数为，（num，left，right）第一个参数参加算法生成的数量级，作为随机生成序列，它能够为千万，由于是long级别，left和right则为生成序列的大小范围，生成的序列为返回值类型为Integer[]。

（5）测验成果如下：

由于希尔排序算法的时刻复杂度剖析没有清晰，假如笔者有爱好能够测验千万级的算法测验，这儿便不在赘述。