排序之快速排序

分手后的思念是犯贱 2022-05-17 07:45 182阅读 0赞

快速排序的精髓在于如何理解它的算法，我称之为“填坑法”。假入有一数组arr，数组第一个元素的索引为head，最后一个元素的索引为last，把第一个元素“挖”出来，临时保存，记录“坑”的位置，这便是“挖坑”。坑有了，如何“填坑”呢？大致思路是，从最后一个元素开始，逐一递减，直到找到一个元素比临时值小，那么将该数据放入“坑”中，并记录“坑”的位置；然后从第一个元素开始，逐一递增，直到找到一个元素比临时值大，那么将该数据放入“坑”中，并记录“坑”的位置；然后又从last的位置开始往前找比临时值小的元素……像这样循环往复，直到head比last大，最后一定剩下了一个“坑”，并且处于中间位置。这样的结果便是某一元素处于中间位置，它前面的元素都比它小，它后面的远都比它大。核心算法阐述完毕。之后再对该元素前面的元素和后面的元素分别做上述操作即可（递归）。下面给一个用java实现的整型数组快排的例子：

import java.util.Arrays;
    
    public class QuickSort {
      public static void sort(int[] arr, int head, int last) {
        int mid = quickSort(arr, head, last);
        if (mid > head) {
          // 递归
          sort(arr, head, mid - 1);
        }
        if (mid < last) {
          // 递归
          sort(arr, mid + 1, last);
        }
      }
    
      private static int quickSort(int[] arr, int head, int last) {
        int index = head; //index：记录坑的位置
        int temp = arr[head]; //temp：临时值
        while (head < last) {
          while (last > head) {
            if (arr[last] < temp) {
              arr[index] = arr[last];   //填坑
              index = last;
              break;
            }
            last--;
          }
          while (head < last) {
            if (arr[head] > temp){
              arr[index] = arr[head];   //填坑
              index = head;
              break;
            }
            head++;
          }
        }
        arr[index] = temp;  // 最后把临时值放入坑中
        return index;   //返回中间值的位置
      }
    
      public static void main(String[] args) {
        int[] arr = new int[]{5,3,2,1,4,2,1,8,9};
        sort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
      }
    }