快速排序算是基本排序里面比较有难度的一个排序方式，但是其原理比较简单，每次都是看一下就懂了，但是时隔好久又忘记了。因此写这个文章记录一下其中的细节以及思考过程。

定义

快速排序就是找到一个基准元素，并将其放到它所在的位置，并且分别对元素前和后的元素进行快速排序。

实现

    public void quickSort(int[] nums, int start, int end) {
       // 队列中只有一个元素或者不含有元素则直接返回
        if (start >= end) return;
       // 找到基准元素的位置
        int partitionIndex = findPartitionIndex(nums, start, end);
        // 排序基准元素前数组
        quickSort(nums, start, partitionIndex - 1);
        // 排序基准元素后数组
        quickSort(nums, partitionIndex + 1, end);
    }
   // 找到基准元素的位置：将第一个元素作为基准元素，从第二个元素开始排序，按照递增的顺序填充元素，最后将最后一个符合条件的元素与基准元素进行替换，就能达到在最后的递增元素之前都是比基准元素大或者小的元素
    public int findPartitionIndex(int[] nums, int start, int end) {
        int pivot = start;
        int index = pivot + 1;
        for (int i = index; i <= end; i++) {
            if (nums[i] > nums[pivot]) {
                swap(nums, i, index);
                index++;
            }
        }
        swap(nums, pivot, index-1);
        return index-1;
    }
   // 交换数组中两元素的位置
    public void swap(int[] nums, int start, int end) {
        int value = nums[start];
        nums[start] = nums[end];
        nums[end] = value;
    }

找到基准元素特定位置图解

快速排序图解.png