文章目录

1. 快速排序

1.1 算法思想

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1.2 算法步骤

  1. 从数列中挑出一个元素，称为 “基准”；(一般选第一个)
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位。这个称为分区（partition）操作；
  3. 递归地以当前“基准”为界限，对左右分区重复上述步骤直至无左右分区。

1.3 复杂度分析

最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定性
O(nlogn) O(n^2) O(nlogn) O（logn） 不稳定

2. 代码实现

2.1 Java版

class Solution {
   
    public int[] sortArray(int[] nums) {
   
        // 快速排序
        // 分区思想，
        // 时间onlgn，空间olgn，不稳定
        int[] arr = new int[nums.length];
        System.arraycopy(nums,0,arr,0,nums.length);
        quickSort(arr, 0, arr.length-1);
        return arr;
    }
    private void quickSort(int[] arr, int left, int right){
   
        if(left >= right){
   
            return;
        }
		// 将元素划分为两个分区
        int l = left, r = right, base = arr[left];
        while(l < r){
   
            while(l < r && arr[r] >= base){
   
                --r;
            }
            while(l < r && arr[l] <= base){
   
                ++l;
            }
            if(l < r){
   
                swap(arr, l, r);
            }
        }
        arr[left] = arr[l];
        arr[l] = base;
		// 递归
        quickSort(arr, left, l-1);
        quickSort(arr, l+1, right);
    }

    private void swap(int[] arr, int i, int j){
   
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}