经典排序算法之快速排序算法

快速排序法的思想

1、先从数列中取出一个数作为基准数。

2、分区过程，将比基准数大的数全部放到它的右边，小于它的数全放到它的左边。

3、在对左右区间重复第二步，直到个区间只有一个数。

假设对以下10个数进行快速排序：按照快速排序法的思想先取一个基准数，为了方便我们直接取第一个数为基准数。

快速排序是冒泡排序的一种改进，冒泡排序每次对相邻的两个数进行比较，相对比较浪费时间。 而快速排序是分别从两端开始进行比较，先从右边向左边找一个小于基准数6的数，再从左往右找一个大于基准数6的数，最后交换。

在选中基准数后，我们分别在左右设置两个指针，在初始状态下，数字6是在序列的第一位，第一步是进行第一轮分区，基准数应该到中间的某个位置。

从右指针指向的8开始和当前基准数作比较，如果比基准数大，那么右指针向左移动，如果比基准数小则停下来。接下来从左指针开始直到找到比6大的数后停下来。

然后交换指针指向的元素。交换后如下：

接着重复上一步，右指针向左，直到发现4<6后停下，左指针向右9>6后停下,此时在进行交换。交换后如下：

接着重复上一步，右指针向左，右指针和左指针相遇，并只剩下一个数，此时说明第一轮分区结束，这时把基准数6和最后一个数进行交换。

第一轮分区结束后，以6为中间节点分成左右两个数字序列。左边序列是3,1,2,5,4。右边序列是9，7，10，8。现在只需要模拟第一轮的方法，对左右两边进行排序就行。

按照相同的处理方式先处理左边序列3,1,2,5,4

重复第一轮分区过程得到：

基准数归位后左边的序列得到：

再按照上一步方法处理后得到：

右边数字序列同样重复处理后得到：

图示所有过程

快速排序法优点是每次排序设置一个基准数，小于基准数的全部放在左边，大于基准数的全部放在右边，这样交换时不用向冒泡排序一样只能相邻的数做交换，交换的次数少。

快速排序法缺点，在排序过程中可能导致相同的元素前后顺序发生改变。

快速排序的代码如下：

function partition<T>(arr: Array<T>, leftIndex: number = 0, rightIndex: number) {
  let pivot = arr[leftIndex]; // 选择一个基准数

  while (leftIndex < rightIndex) {
   // 右往左移动
    while (arr[rightIndex] >= pivot && rightIndex > leftIndex) {
      rightIndex--;
    }
    arr[leftIndex] = arr[rightIndex]; 
    
    // 左往右移动
    while (arr[leftIndex] <= pivot && rightIndex > leftIndex) {
      leftIndex++;
    }
    arr[rightIndex] = arr[leftIndex];

  }
  arr[leftIndex] = pivot; // 记录基准数到当前指针空间

  return leftIndex; // 返回基准数索引
}

export function quickSort<E>(arr: Array<E>, leftIndex: number = 0, rightIndex: number) {

  if (leftIndex < rightIndex) {
    const middle = partition(arr, leftIndex, rightIndex);

    quickSort(arr, leftIndex, middle - 1);

    quickSort(arr, middle + 1, rightIndex);
  }
  return arr;
};

let chineseArr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];
const result = quickSort(chineseArr, 0, chineseArr.length - 1);