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

1.排序的概念及应用

1.1 排序的概念

排序：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.3 常见的排序算法

2.常见排序算法的实现 (默认排升序)

2.1 插入排序

2.1.1 基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。

如下模拟动图:

2.1.2 直接插入排序

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置将 array[i] 插入，原来位置上的元素顺序后移如下图:

直接插入排序具体操作:

第一步 理清思路:

当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，

此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置将 array[i] 插入，原来位置上的元素顺序后移

第二步 具体步骤:

1. 定义 tmp 保存 排序前 i 下标对应的值。for(i) 为 外循环，for(j) 为 内循环，j = i -1.

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. 稳定性：不稳定