Java版希尔排序

分析&回答

动态演示 -> 跳转到博客查看

实现代码

/**
 * 希尔排序 针对有序序列在插入时采用移动法。
 * <p/>
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 *
 * @param sortArr
 */
private static void shellSort(int[] sortArr) {
    //增量gap，并逐步缩小增量
    for (int gap = sortArr.length / 2; gap > 0; gap /= 2) {
        //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < sortArr.length; i++) {
            int j = i;
            int temp = sortArr[j];
            if (sortArr[j] < sortArr[j - gap]) {
                while (j - gap >= 0 && temp < sortArr[j - gap]) {
                    //移动法
                    sortArr[j] = sortArr[j - gap];
                    j -= gap;
                }
                sortArr[j] = temp;
            }
        }
    }
}

/**
 * 希尔排序 针对有序序列在插入时采用交换法
 *
 * @param sortArr
 */
private static void shellSortSwap(int[] sortArr) {
    //增量gap，并逐步缩小增量
    for (int gap = sortArr.length / 2; gap > 0; gap /= 2) {
        //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < sortArr.length; i++) {
            int j = i;
            while (j - gap >= 0 && sortArr[j] < sortArr[j - gap]) {
                //插入排序采用交换法
                swap(sortArr, j, j - gap);
                j -= gap;
            }
        }
    }
}


/**
 * 交换数组元素
 *
 * @param arr
 * @param a
 * @param b
 */
public static void swap(int[] arr, int a, int b) {
    arr[a] = arr[a] + arr[b];
    arr[b] = arr[a] - arr[b];
    arr[a] = arr[a] - arr[b];
}

性能分析

• 不稳定 
• 平均时间复杂度O(n ㏒n)
• 空间复杂度O(1) 

反思&扩展

Java版常用排序算法复杂度

喵呜面试助手： 一站式解决面试问题，你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享！