快速排序

算法

发布日期: 2023-07-05

更新日期: 2023-07-06

文章字数: 1k

阅读时长: 4 分

阅读次数:

快速排序

快速排序的思想是分治，将整体拆成一个局部，当局部是有序的话，整体自然而然就是有序的。所以说这种思想放在其他问题上，非常的巧妙。

整体思路

选取基准数
根据基准数进行分区，分为小于基准数和大于等于基准数两部分
对于上一步分区后的两部分，重复前两步操作，直到每个区间只有一个元素停止操作

流程分析

比如数组arr=[2,3,1,8,9,6,-1], 数组长度为7

定义左右指针0, 6 ，分别指向头和尾。
确定基准数，以起始位置的元素作为基准数，也就是下标为0的元素2，然后我们将基准数临时保存下来，后面还会用到。
当左右指针重合时，我们停止本次遍历操作
先移动右指针，往左移，当发现在移动的过程中有比基准数小的元素，我们停止移动
我们会将当前元素覆盖到做指针指向的元素，第一次左指针刚好在基准数位置
这个时候右指针停止的位置相当于留有一个坑位，等待被覆盖，这个要覆盖的元素来自左指针右移指向的元素
我们开始移动左指针，当发现当前元素比基准数大，我们就将该元素覆盖到右指针指向的坑位，当覆盖完之后，左指针指向的元素变成来新的坑位
这个时候我们继续移动右指针，重复第四部操作
反复移动左右指针，直到两个指针重合，我们停止当前操作。这个时候发现停止的位置，需要把一开始的基准数放在这个位置，此时左右两边刚好是小于基准数和大于等于基准数两部分
然后进行递归操作，去分别排序左右两部分，直到每个部分只有一个元素，停止所有操作

完整代码实现

Java实现

  public static void quickSort(int[] array, int start, int end){
      if (start >= end){
          return;
      }
      // 确立基准数
      int base = array[start];
      int i = start , j = end;
      while (i < j){
          // 先是右指针左移，发现小于基准数的时候，停止移动
          while (i < j && array[j] >=  base){
              j--;
          }
          if (i < j){
              array[i] = array[j];
              i++;
          }
          // 先是左指针右移，发现大于基准数的时候，停止移动
          while (i < j && array[i] < base){
              i++;
          }
          if (i < j){
              array[j] = array[i];
              j--;
          }
      }
      //当左指针和右指针重合的时候，发现两边的已经被分为小于基准数和大于等于基准数，然后将一开始的基准数赋值给当前位置
      array[i] = base;
      // 继续进行排序，重复上面的操作
      quickSort2(array, start, i - 1);
      quickSort2(array, i + 1, end);
  }

  public static void quickSort(int[] array, int left, int right) {
      if (left >= right){
          return;
      }
      int i = left;
      int j = right;
      int temp = array[left];
      while (i < j){
          while (i < j && array[j] > temp){
              j--;
          }
          while (i < j && array[i] < temp){
              i++;
          }
          if (i < j && array[i] == array[j]){
              i++;
          }else {
              int swap = array[j];
              array[j] = array[i];
              array[i] = swap;
          }
      }
      array[i] = temp;
      quickSort(array, left, i - 1);
      quickSort(array, i + 1, right);
  }

Go实现

  func quickSort(arr []int, start , end int)  {
      if start >= end {
          return
      }
      left, right := start, end
      base := arr[start]
      for left < right {
          for left < right && arr[right] >= base {
              right--
          }
          if left < right {
              arr[left] = arr[right]
              left++
          }
          for left < right && arr[left] < base {
              left++
          }
          if left < right {
              arr[right] = arr[left]
              right--
          }
      }
      arr[left] = base
      quickSort(arr, start, left - 1)
      quickSort(arr, left + 1, end)
}