数据结构（十二）：快速排序

• 通过一趟排序将待排序元素分割成独立的两部分，其中一部分元素的值均比另一部分的值小，则分别对这两部分继续进行排序，直到整个序列有序

直接插入排序例子

• 流程：

  • 把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理
  • 交换了以后再和小的那端比，比它小不交换，比他大交换
  • 这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的
  • 然后再用分治法，分别对这两个独立的数组进行排序

• 举例：

  • 假设数组如下

  50	10	90	30	70	40	80	60	20

  • 选择基准值 50，从后往前比较，50 > 20 进行比较，交换位置

  20	10	90	30	70	40	80	60	50

  • 从前往后比较，20 10 均比 50 小 ，不做操作，直到 90 > 50，交换位置

  20	10	50	30	70	40	80	60	90

  • 继续从后往前比较，60 80 均大于 50，不做操作，直到 40 < 50，交换位置

  20	10	40	30	70	50	80	60	90

  • 继续从前往后比较，50 > 30，不做操作，70 > 50，交换位置

  20	10	40	30	50	70	80	60	90

  • 此时第一趟排序完成，然后采用分支法，分别对左右两个独立数组在进行排序

直接插入排序代码

public static void main(String[] args) {
    int[] arr = new int[]{50, 10, 90, 30, 70, 40, 80, 60, 20};
    quickSort(arr, 0, arr.length - 1);
}

// 快速排序
public static void quickSort(int[] a, int low, int high) {
    int start = low;
    int end = high;
    int key = a[low];       // 基准值

    while (end > start) {
        //从后往前比较
        while (end > start && a[end] >= key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
            end--;
        if (a[end] <= key) {
            swap(a, start, end);
        }
        //从前往后比较
        while (end > start && a[start] <= key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
            start++;
        if (a[start] >= key) {
            swap(a, start, end);
    }
    System.out.println(Arrays.toString(a));
    }
    //递归
    if (start > low) quickSort(a, low, start - 1); // 左边序列。第一个索引位置到关键值索引-1
    if (end < high) quickSort(a, end + 1, high); //右边序列。从关键值索引+1到最后一个
}

// 交换位置
public static void swap(int[] arr, int low, int high) {
    int temp = arr[low];
    arr[low] = arr[high];
    arr[high] = temp;
}

归并排序性能

• 快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的
• 但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序，在序列中元素很少时，效率将比较低
• 快速排序是一个不稳定的排序方法

快速排序优化

• 快速排序的基准值选取影响了快速排序的性能
• 对于基准值的选取一般有三种方法：固定切分，随机切分和三取样切分，通常采用“三取样切分”方法，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录

--- 待更新 ----