前言

这是我的八股专栏的第9篇文章。

我的八股专栏：https://www.nowcoder.com/creation/manager/columnDetail/j8ZZk0

(里面还有苍穹外卖的完整话术)

我的架构设计专栏：https://www.nowcoder.com/creation/manager/columnDetail/0ybvLm

1.10种排序算法汇总

*先谈一谈稳定性：稳定性简单来讲就是考虑排序后值相同的元素和排序前是否保持一致（如排序前a1和a2值相同，排序后仍是a1在前a2在后）*

1.冒泡排序

通过对待排序序列从前向后（从下标较小的元素开始）,依次*对相邻两个元素的值进行两两比较*，若发现*逆序则交换*，使值较大的元素逐渐从前移向后部，就如果水底下的气泡一样逐渐向上冒。

    //定义一个标志位，用于判定元素之间是否进行了交换
    boolean flag = false;
 
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                //进入这个if分支里边，则说明有元素进行了交换
                //所以将flag=true
                flag = true;
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        
        //在进行完一轮的排序之后，判断本轮是否发生了元素之间的交换
        //如果没有发生交换，说明数组已经是有序的了，则直接结束排序
        if (!flag) {
            break;
        } else {
            //如果发生了交换，那么在下一轮排序之前将flag再次置为false
            //以便记录下一轮排序的时候是否会发生交换
            flag = false;
        }
    }

2.选择排序

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

代码实现：

    public void selectionSort(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

3.插入排序

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。

• 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
• 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
• 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

代码实现：

public void insertSort(int[] arr) {
    if (arr == null) {
        return;
    }
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int j = i;
        //将当前元素tmp插入到合适位置
        for (; j > 0 && tmp < arr[j - 1]; j--) {
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
}

4.希尔排序

希尔排序是一种基于插入排序的算法，通过将待排序数组按照一定的间隔分组，对每个分组进行插入排序，逐渐缩小间隔，最终使得整个数组有序。

代码实现：

public static int[] ShellSort(int[] array) {
    int len = array.length;
    int temp, gap = len / 2;
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            temp = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = temp;
        }
        gap /= 2;
    }
    return array;
}
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1}; // 待排序数组
        shellSort(arr); // 调用希尔排序方法
        for (int i : arr) {
            System.out.print(i + " "); // 输出排序后的数组
        }
    }

    /**
     * 希尔排序算法实现
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr) {
        int n = arr.length; // 获取数组长度
        for (int gap = n / 2; gap > 0; gap /= 2) { // 初始gap为数组长度的一半，每次减半
            for (int i = gap; i < n; i++) { // 从gap开始遍历数组
                int temp = arr[i]; // 记录当前元素
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { // 插入排序，将大于temp的元素后移
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp; // 将temp插入到正确的位置
            }
        }
    }
}

5.快速排序

快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个分界点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。

/* 快速排序主函数 */
void sort(int[] nums) {
    // 一般要在这用洗牌算法将 nums 数组打乱，
    // 以保证较高的效率，我们暂时省略这个细节
    quicksort(nums, 0, nums.length - 1);
}

/* 快速排序核心逻辑 */
void quicksort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    // 通过交换元素构建分界点索引 p
    int p = partition(nums, lo, hi);
    // 现在 nums[lo..p-1] 都小于 nums[p]，
    // 且 nums[p+1..hi] 都大于 nums[p]
    quicksort(nums, lo, p - 1);
    quicksort(nums, p + 1, hi);
}
//partition函数会将nums[p]排到正确的位置，使得nums[lo..p-1] < nums[p] < nums[p+1..hi]。
int partition(int[] nums, int lo, int hi) {
    if (lo == hi) return lo;