想借用此类问题深入理解快排特性。先给结论，再具体展示。

快排具有的特性：

1. 快排在每轮排完，能使pivot元素置于最终排序结果的位置上；
2. 对于正序排序，每轮排完的pivot元素的左边的元素均小于pivot，位于pivot右边的元素均大于pivot。（逆序排序正好相反）
3. 快速排序属于交换排序，交换排序除了快排还有冒泡排序，但是冒泡是稳定的排序算法，但快排是不稳定的！因此不能用原有的快排思想解决要求具有稳定特性的问题（如：有序的全排列问题）；

这里有两点要说明：

1. 所谓稳定性是指：如果对于原无序数组有两个相同大小的值，排完序后，这两个元素的相对顺序没有发生改变，则该排序算法是稳定的；
2. 还要说明的一点是，很多大厂（尤其是微软等外企）对于手写快排的要求是：还要加一些随机pivot的trick。而这实现起来，也无外乎是额外增加了三五行代码的事情（例题中有展现）。

首先来看一下快排算法：

def quick_sort(nums, reverse=False):
    if reverse == False:
        quick_sort_recursion(nums, 0, len(nums)-1)
    else:
        quick_sort_reverse_recursion(nums, 0, len(nums)-1)

def quick_sort_recursion(nums, left, right):
    if left >= right: return 
    pivot_loc = partition(nums, left, right)
    quick_sort_recursion(nums, left, pivot_loc-1)
    quick_sort_recursion(nums, pivot_loc+1, right)

    
def partition(nums, left, right):
    pivot = nums[left]
    while left < right:
        while left < right and nums[right] >= pivot:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] <= pivot:
            left += 1
        nums[right] = nums[left]
    nums[left] = pivot 
    return left 
    

def quick_sort_reverse_recursion(nums, left, right):
    if left >= right: return 
    pivot_loc = partition_reverse(nums, left, right)
    quick_sort_reverse_recursion(nums, left, pivot_loc-1)
    quick_sort_reverse_recursion(nums, pivot_loc+1, right)
      
def partition_reverse(nums, left, right):
    pivot = nums[left]
    while left < right:
        while left < right and nums[right] <= pivot:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] >= pivot:
            left += 1
        nums[right] = nums[left]
    nums[left] = pivot 
    return left 
    
    
nums = [1,3,5,7,6,4,2]
quick_sort(nums, True)
print(nums)

我们来总结一下快排代码需要注意的点：

1. 在递归代码中，只有当left < right的时候才会往下执行代码，注意这里没有等于；
2. 如果默认将数组的第一个元素设为pivot，请注意pivot = nums[left] 而不是pivot = nums[0]，同时在一轮交换操作完成后，还要做一个逆操作；
3. 排序规则仅是在partition函数的内层循环有所区别（请注意，这里的排序规则不仅仅是正序或者逆序这两种情况，根据不同的问题条件，会抽象出不同的排序规则，可以见后面的例题）；

在熟练掌握原有快排算法后，我们遇到了可以用快排来优化时间的问题时，需要思考两个问题：

1. 基于快排什么样的特性，该问题可以使用快排；
2. 该问题具有什么样的特点，才会想到使用快排；

一般地，前两个特性可以解决第k大或前k大问题，而通过适当改变排序规则，可以解决本质上是一个排序问题的衍生子问题。

215. 数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 由于使用的正序快排，利用数组长度将第k大转换成第len-k+1小的问题
        k = nums.length - k; //这里的k指转换成第len-k+1小的值的下标
        quicksort(nums, k, 0, nums.length - 1);
        return nums[k];
    }
    private void quicksort(int[] arr, int k, int left, int right) {
        if (left >= right) {return ;}
        int pivotLoc = partition(arr, left, right);
        if (pivotLoc == k) {
            return ;
        } else if (pivotLoc < k) {
            quicksort(arr, k, pivotLoc + 1, right);
        } else {
            quicksort(arr, k, left, pivotLoc - 1);
        }
    }
    private int partition(int[] arr, int left, int right) {
        // 随机产生一个pivot，并将其与当前数组的第一个元素进行交换
        int i = new Random().nextInt(right - left + 1) + left;
        int pre = arr[i];
        arr[i] = arr[left];
        arr[left] = pre;
        
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
}

该问题用到了快排的第一个特性；

剑指 Offer 40. 最小的k个数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quicksort(arr, k, 0, arr.length - 1);
        return Arrays.copyOfRange(arr, 0, k);
    }
    private void quicksort(int[] arr, int k, int left, int right) {
        if (left >= right) {return ;}
        int pivotLoc = partition(arr, left, right);
        if (pivotLoc == k) {
            return ;
        } else if (pivotLoc < k) {
            quicksort(arr, k, pivotLoc + 1, right);
        } else {
            quicksort(arr, k, left, pivotLoc - 1);
        }
    }
    private int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
}

该问题体现了快排的第二个特性。

剑指 Offer 45. 把数组排成最小的数

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quick_sort(nums):
            quick_sort_recursion(nums, 0, len(nums)-1)

        def quick_sort_recursion(nums, left, right): 
            if left >= right: return 
            pivot_loc = partition(nums, left, right)
            quick_sort_recursion(nums, left, pivot_loc-1)
            quick_sort_recursion(nums, pivot_loc+1, right)
            
        def partition(nums, left, right):
            pivot = nums[left]
            while left < right:
                while left < right and nums[right] + pivot >= pivot + nums[right]: right -= 1 # 排序规则发生改变
                nums[left] = nums[right]
                while left < right and nums[left] + pivot <= pivot + nums[left]: left += 1 # 排序规则发生改变
                nums[right] = nums[left]
            nums[left] = pivot 
            return left 
        
        nums = [str(num) for num in nums]
        quick_sort(nums)
        return ''.join(nums)

该问题修改排序规则之后利用了快排思想。

973. 最接近原点的 K 个点

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int[][] res = new int[K][2];
        quickSort(points, K, 0, points.length - 1);
        for (int i = 0; i < K; ++i) {
            res[i] = points[i];
        }
        return res;
    }
    private void quickSort(int[][] points, int K, int left, int right) {
        if (left >= right) {return;}
        int pivotLoc = partition(points, left, right);
        if (pivotLoc == K) {
            return ;
        } else if (pivotLoc < K) {
            quickSort(points, K, pivotLoc + 1, right);
        } else {
            quickSort(points, K, left, pivotLoc - 1);
        }
    }
    private int partition(int[][] points, int left, int right) {
        int i = new Random().nextInt(right - left + 1) + left;
        int[] pre = points[i];
        points[i] = points[left];
        points[left] = pre;
        int[] pivot = points[left]; 
        while (left < right) {
            while (left < right && distance(points[right]) >= distance(pivot)) {
                right--;
            }
            points[left] = points[right];
            while (left < right && distance(points[left]) <= distance(pivot)) {
                left++;
            }
            points[right] = points[left];
        }
        points[left] = pivot;
        return left;
    }
    private int distance(int[] pos) {
        return pos[0] * pos[0] + pos[1] * pos[1];
    }
}

该问题修改了排序规则，同时体现了快排的前两个特性。

延伸为一种交换思想来优化问题的解决方案：

46. 全排列

class Solution:
    def permute(self, nums): #  全排列I
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # 所有数都填完了
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res

// 一般回溯，used标记原数组具体位置对应的元素
public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;

        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        Deque<Integer> path = new ArrayDeque<>(len);

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     Deque<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.addLast(nums[i]);
                used[i] = true;

                System.out.println("  递归之前 => " + path);
                dfs(nums, len, depth + 1, path, used, res);

                used[i] = false;
                path.removeLast();
                System.out.println("递归之后 => " + path);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}

1. 使用交换思想，定住一个位置的元素，写出来的代码可以优化空间；
2. 对于要求按顺序输出全排列的问题，该交换思想并不能保证是有序的。