Java 七大排序算法详解（上）

2. 遍历数组，在内循环中，tmp 与 array[j] 进行比较，若是 tmp 小 则 [j + 1] = [j];

若是 tmp 大 则 直接 break;

3. 在外循环中 将 最后 j + 1 位置的值 赋为 tmp 值，[j + 1] = tmp;

第三步 画图理解，一目了然:

第四步 代码实现:

/**
 * 时间复杂度:
 * 最好情况：数据完全有序的时候 1 2 3 4 5 :O(N)
 * 最坏情况：数据完全逆序的时候 5 4 3 2 1 :O(N^2)
 * 结论：数据越有序，排序越快，
 * 场景：现在有一组基本有序的数据，那么用哪个排序好点？ - 直接插入排序。
 * 空间复杂度：O(1)
 * 稳定性：稳定的排序
 * 一个本身就是稳定的排序 是可以实现为不稳定的排序的
 * 相反 一个本身就不稳定的排序 是不可以实现为稳定的排序的。
 *
 * @param //直接插入排序
 */
public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int tmp = array[i];
        int j = i-1;
        for (; j >= 0; j--) {
            if(array[j] > tmp) { // >= 会变成不稳定的
                array[j+1] = array[j];
            }else {
                //array[j+1] = tmp; 执行了一次
                break;
            }
        }
        //当 j=-1 时，a[j+1]=tmp 这条语句没被执行，所以再写一次
        array[j+1] = tmp;
        //执行了两次，故把第一次屏蔽。
    }
}

最后总结:

1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定

2.1.3 希尔排序 (缩小增量排序)

希尔排序本质上 就是 在对直接插入排序做优化。

第一步 了解基本思想:

先选定一个整数 gap，把待排序文件中所有记录分成多个组，此处 gap 通常都是初始化成 gap = array.length/2;所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行直接插入排序。每进行一次直接插入排序 gap /= 2 重复上述分组和排序的工作。当 gap = 1 时，所有记录在同一组内进行直接插入排序。

第二步 画图辅助理解:

第三步 具体步骤:

具体步骤与 直接插入排序的大体相同，将 外循环条件换成 for (int i = gap; i < array.length; i++)，外循环中 j = i - gap 而不是 - 1; 同时，内循环变成 for (; j >= 0; j -= gap) 赋值条件变为 array[j+gap] = tmp; 最后在直接插入排序外加一层 gap /= 2 的循环 就大功告成了。

第四步 代码实现:

/**
 * 希尔排序
 *
 * 时间复杂度:
 * n^1.3 - n^1.5
 * 空间复杂度：O(1)
 *
 * 稳定性：不稳定
 * @param //shell
 */
public static void shellSort(int[] array) {
    int gap = array.length;
    while(gap > 1) {
        gap /= 2;
        shell(array,gap);
    }
    //gap /= 2;不用写 因为 gap=2 或 3 时，gap/2 = 1.已经进行了直接插入排序。
}

private static void shell(int[] array,int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0; j -= gap) {
            if(array[j] > tmp) {
                array[j+gap] = array[j];
            }else {
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

最后 希尔排序的特性总结:

1. 希尔排序是对直接插入排序的优化。 2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。 3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：O(n^1.25) ~ O(1.6 * n^1.25) 4. 稳定性：不稳定

2.2 选择排序

2.2.1 基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 如下模拟动图:

第一步 理清思路:

在元素集合 array[i] ~ array[n-1] 中选择关键码最小的数据元素，若它不是这组元素中的第一个元素，则将它与这组元素中的最后一个（第一个）元素交换。

在剩余的 array[i] ~ array[n-2]（array[i+1] ~ array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。

第二步 具体步骤:

1. 写个双层循环，for(i) 为 外层循环，for(j) 为外层循环，定义 minIndex = i, j = i + 1;

2. [minIndex] 与 [j] 比较，当 [minIndex] > [j] 时 二者交换。

第三步 代码实现:

/**
 * 选择排序
 *
 * 时间复杂度:
 * 最好：O(N^2)
 * 最坏：O(N^2)
 * 空间复杂度：O(N)
 *
 * 稳定性：不稳定
 *
 * @param array
 */
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if(array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        swap(array,minIndex,i);
    }
}

public static void swap(int[] array,int i,int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

选择排序有 第二种写法，反正都要遍历一遍数组，不如把最大值和最小值都找出来，最小的往最前放，最大的往最后放。

第二种写法步骤:

1. 定义 left = 0, right = array.length-1, i = left + 1; minIndex = maxIndex = 0;

2. while( left < right ) 循环，i 在循环中，遍历数组 找到最小元素下标 和 最大元素下标，出循环 与 minIndex 和 maxIndex 交换。

3. 出循环后 考虑一个特殊情况，当 left = 0 下标 对应的值就是最大值时，第二步出循环后的交换操作 将最大值交换到 minIndex 下标处了。需要 再将 maxIndex 标记到最大值。

第二种写法代码实现:

public static void swap(int[] array,int i,int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
//选择排序的第二种写法.
public static void selectSort2(int[] array) {
    int left = 0;
    int right = array.length-1;
    while(left < right) {
        int minIndex = left;
        int maxIndex = left;
        for (int i = left; i <= right; i++) {
            if(array[i] < array[minIndex]) {
                minIndex = i;
            }
            if(array[i] > array[maxIndex]) {
                maxIndex = i;
            }
        }
        swap(array,left,minIndex); //有一种情况是 maxIndex 原本就在 left 位置上，上面的交换将最大值交换到 minIndex 下标处了。导致后续的排序不正确。
        if(maxIndex == left) {
            maxIndex = minIndex;
        }
        swap(array,right,maxIndex);
        left++;
        right--;
    }
}

第四步 直接选择排序的特性总结:

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：不稳定

2.2.3 堆排序

堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

第一步 具体步骤:

1. 排升序，建大堆，向下调整算法，parent 从 (array.length - 1)/2 开始 减到 1 2. 将最后一个元素与首元素交换，除末尾元素外，其余元素调整成大根堆 3. 定义一个 end = array.length - 1; while (end > 0) 循环中进行 2 步骤。

第二步 代码实现:

/**
 * 堆排序
 *
 * 时间复杂度:O(N)+O(N*logN) 约等于 O(N*logN)
 *
 * 如果都以最坏的情况来看，堆排序是目前来说最快的，希尔排序其次。
 * 假设希尔排序为 O(N^1.3) 当 N 越大时，logN 趋于不变所以，堆排序 O(N*logN) 要快一些。
 *
 * 空间复杂度:O(1)
 * 稳定性：不稳定
 */
public static void heapSort(int[] array) {
    //建大堆 createBigHeap(array);//O(N)
    int end = array.length-1; //O(N*logN)
    while(end > 0) {
        swap(array,0,end);
        shiftDown(array,0,end);
        end--;
    }
}

private static void createBigHeap(int[] array) {
    for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
        shiftDown(array,parent,array.length);
    }
}

private static void shiftDown(int[] array,int parent,int end) {
    int child = (parent*2)+1;
    while(child < end) {
        //保证右子树存在并且当右子树大的时候，child++来到右子树的下标。
        if(child+1 < end && array[child+1] > array[child]) {
            child++;
        }
        if(array[child] > array[parent]) {
            swap(array,child,parent);
            parent = child;
            child = parent*2+1;
        }else {
            //本身就是大根堆
            break;
        }
    }
}

第三步 堆排序的特性总结:

1. 堆排序使用堆来选数，效率就高了很多。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(1) 4. 稳定性：不稳定