常见的排序算法

kinglyjn     2020-11-20     阅读次

常见的排序算法

1. 1. 基础排序
   1. 1.1. 冒泡排序
   2. 1.2. 选择排序
   3. 1.3. 插入排序
2. 2. 高级排序
   1. 2.1. 希尔排序
   2. 2.2. 归并排序
   3. 2.3. 双路快速排序
   4. 2.4. 三路快速排序

基础排序

冒泡排序

/**
 * 冒泡排序
 * 时间复杂度：O(n^2)
 * 稳定性：稳定
 */
public static void bubbleSort(Comparable[] array) {
    for (int i = array.length-1; i > 0; i--) {
        boolean needNext = false;
        for (int j = 0; j < i; j++) {
            if (array[j].compareTo(array[j+1]) > 0) { // 比较
                needNext = true;
                Comparable tmp = array[j]; // 交换
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
        if (!needNext) { // 如果不存在交换，则算法结束
            break;
        }
    }
}

选择排序

/**
 * 选择排序
 * 时间复杂度：O(n^2)
 * 稳定性：不稳定
 */
public static void selectSort(Comparable[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int selectIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j].compareTo(array[selectIndex]) < 0) { // 比较
                selectIndex = j;
            }
        }
        Comparable tmp = array[i]; // 交换
        array[i] = array[selectIndex];
        array[selectIndex] = tmp;
    }
}

插入排序

/**
 * 插入排序
 * 时间复杂度：O(n^2)
 * 稳定性：稳定
 */
public static void insertSort(Comparable[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if (array[j].compareTo(array[j-1]) < 0) { // 判断
                Comparable tmp = array[j]; // 交换
                array[j] = array[j-1];
                array[j-1] = tmp;
            } else {
                break;
            }
        }
    }
}

高级排序

希尔排序

/**
 * 希尔排序（插入排序的分组优化）
 * 时间复杂度：~ O(n*log2(n))
 * 稳定性：不稳定
 */
public static void shellSort(Comparable[] array) {
    int h = 1;
    while (h < array.length/2) {
         h = 2*h + 1;
    }

    while (h >= 1) {
        for (int i=h; i<array.length; i+=h) {
            for (int j=i; j>=h; j-=h) {
                if (array[j].compareTo(array[j-h]) < 0) { // 判断
                    Comparable tmp = array[j]; // 交换
                    array[j] = array[j-h];
                    array[j-h] = tmp;
                } else {
                    break;
                }
            }
        }
        h = h/2;
    }
}

归并排序

/**
 * 归并排序
 * 时间复杂度：O(n*log2(n))，性能跟希尔排序相似（虽然归并排序性能极好，但它需要申请额外的数组空间）
 * 稳定性：稳定
 */
public static void mergeSort(Comparable[] array) {
    Comparable[] assistArray = new Comparable[array.length];
    mergeSort(array, assistArray, 0, array.length-1);
}
private static void mergeSort(Comparable[] array, Comparable[] assistArray, int low, int high) {
    // 校验
    if (low >= high) {
        return;
    }
    // 分治
    int middle = low + (high-low)/2;
    mergeSort(array, assistArray, low, middle);
    mergeSort(array, assistArray, middle+1, high);
    // 合并
    merge(array, assistArray, low, middle, high);
}
private static void merge(Comparable[] array, Comparable[] assistArray, int low, int middle, int high) {
    // 指针三剑客
    int index = low;
    int p1 = low;
    int p2 = middle + 1;

    // 遍历，移动指针p1和p2，比较对应索引处的值，找出比较小的那个，放到辅助数组对应索引处
    while (p1<=middle && p2<=high) {
        if (array[p1].compareTo(array[p2]) < 0) {
            assistArray[index++] = array[p1++];
        } else {
            assistArray[index++] = array[p2++];
        }
    }
    // 遍历，如果p1指针没走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
    while (p1<=middle) {
        assistArray[index++] = array[p1++];
    }
    // 遍历，如果p2指针没走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
    while (p2<=high) {
        assistArray[index++] = array[p2++];
    }
    // 把辅助数组中的元素拷贝到原数组中
    for (int i = low; i <= high; i++) {
        array[i] = assistArray[i];
    }
}

双路快速排序

/**
 * 快速排序
 * 时间复杂度：平均为 O(n*log2(n))，最坏 O(n^2)
 * 稳定性：不稳定
 */
public static void quickSort(Comparable[] array) {
    quickSort(array, 0, array.length-1);
}
private static void quickSort(Comparable[] array, int low, int high) {
    // 校验
    if (low >= high) {
        return;
    }
    // 切分，index为分组后（左边都是小的，右边都是大的）的索引值
    int index = partition(array, low, high);
    // 让左子组、右子组分别有序
    quickSort(array, low, index-1);
    quickSort(array, index+1, high);
}
private static int partition(Comparable[] array, int low, int high) {
    // 确定分界值
    Comparable key = array[low];

    // 定义两个指针，分别指向待切分元素的最小索引处和最大索引的下一个位置
    int left = low;
    int right = high + 1;

    // 切分
    while (true) {
        // 先从右向左扫描，移动right指针，找第一个比分界值小的元素，停止
        while (array[--right].compareTo(key) > 0) { // 只要比x大就继续
            if (right == low) {
                break;
            }
        }
        // 然后从左向右扫描，移动left指针，找第一个比分界值大的元素，停止
        while (array[++left].compareTo(key) < 0) {  // 只要比x小就继续
            if (left == high) {
                break;
            }
        }
        // 判断 left >= right，是则证明元素扫描完毕，否则交换元素
        if (left >= right) {
            break;
        } else {
            Comparable tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
    }

    // 交换分界值
    Comparable tmp = array[low];
    array[low] = array[right]; // 注意，无论从小到大，还是从大到小排序，取right返回才是正确的！
    array[right] = tmp;
    return right;
}

三路快速排序

Java底层默认使用的是三路快速排序，三路快排较之于双路快排，大大优化了处理大量重复元素的情况。三路快排也是不稳定排序。

public static void quickSort(Comparable[] array) {
    quickSort(array, 0, array.length-1);
}

private static void quickSort(Comparable[] array, int low, int high) {
    // 结束条件
    if (low >= high) {
        return;
    }

    // 优化一：数组长度小于16的时候，使用插入排序，以减少递归层级
    if (high - low + 1 < 16) {
        insertSort(array, low, high);
        return;
    }

    // 优化二：随机选取基准值，切割采用三路方式
    swap(array, low, low+(int)(Math.random()*(high-low+1)));
    Comparable key = array[low];
    int lt = low;
    int gt = high + 1;
    int index = low + 1;
    while (index < gt) {
        if (array[index].compareTo(key) < 0) {
            lt++;
            swap(array, index, lt);
            index++;
        } else if (array[index].compareTo(key) > 0) {
            gt--;
            swap(array, index, gt);
        } else {
            index++;
        }
    }
    swap(array, low, lt);

    // 递归处理
    quickSort(array, low, lt-1);
    quickSort(array, gt, high);
}

public static void insertSort(Comparable[] array, int low, int high) {
    for (int i = low+1; i < high+1; i++) {
        for (int j = i; j > low; j--) {
            if (array[j].compareTo(array[j-1]) < 0) {
                swap(array, j, j-1);
            } else {
                break;
            }
        }
    }
}

algorithm, sort

algorithm