八大排序算法之快速排序

飞熊 • 2023年4月17日上午11:03 • 后端漫谈 • 阅读 60

基本思想：

把n个待排序元素看出为一个有序表和无序表。开始时有序表中只包含1个元素，无序表中包含n-1个元素，排序过程中每次从无序表中按下标顺序取出元素，将他插入到有序表中适当位置，重复n-1次完成排序过程。
如下图

稳定性：稳定
时间复杂度：O(n2)
代码实现

public static int[] insertEx(int[] arr) {

    // 如果数组小于或等于1直接返回
    if (arr.length <= 1) return arr;
    // 创建一个和arr一样大的数组，所有元素默认为0
    int[] newArr = new int[arr.length];

    // 将arr第一个元素赋给新数组第一个元素
    newArr[0] = arr[0];

    // 从arr的第一个元素开始遍历
    for (int i = 1; i < arr.length; i++) {
        for (int j = i - 1; j >= 0; j--) {
            // 将arr中的元素与新数组的作比较
            if (arr[i] < newArr[j]) {
                // 这里将大于arr【i】的新数组的元素向后移，直到找到合适元素插入
                newArr[j+1] = newArr[j];
                newArr[j] = arr[i];
            }
            // 当新数组里面的元素为0时在更换数据
            if (newArr[i] == 0) {
                newArr[i] = arr[i];
            }
        }
    }

    return newArr;
}

这样的代码不是特别简介，但是结合示例图容易理解
简化后的代码

//插入排序
public static int[] insertSort(int[] arr) {

    if (arr.length <= 1) return arr;

    for (int i = 1; i < arr.length; i++) {

        //待排序的元素
        int insertValue = arr[i];
        //待排序的前一个元素的下标
        int insertIndex = i-1;
        //insertIndex >= 0 防止数组越界
        //insertValue < arr[insertIndex]待插入的数，还没有找到位置将arr[insertIndex]后移
        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertValue;

    }

    return arr;
}