java实现快速排序

public class MyQuickSort { void QuickSort(int[] nums, int low , int hight) { if(low < hight) { int pivot = Partition(nums, low, hight); QuickSort(nums, low, pivot-1); QuickSort(nums, pivot+1, hight); } } int Partition(int[] nums, int low, int hight) { int pivot = nums[low]; while(low < hight) { while(low < hight && nums[hight] >= pivot) { //需要交换 hight--; // 找到需要交换的 } nums[low] = nums[hight]; // 交换 while(low < hight && nums[low] <= pivot) low++; nums[hight] = nums[low]; } nums[low] = pivot; return low; // 当前划分位置，并按这个位置进行子序列划分 } }

原理不在叙述，百度上太多

就是划分加递归，简单描述就是找到划分，然后递归左序列再递归右序列。

某题：

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-colors 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution { public void sortColors(int[] nums) { MyQuickSort myQuickSort = new MyQuickSort(); myQuickSort.QuickSort(nums, 0, nums.length-1); } class MyQuickSort { void QuickSort(int[] nums, int low , int hight) { if(low < hight) { int pivot = Partition(nums, low, hight); QuickSort(nums, low, pivot-1); QuickSort(nums, pivot+1, hight); } } int Partition(int[] nums, int low, int hight) { int pivot = nums[low]; while(low < hight) { while(low < hight && nums[hight] >= pivot) { //需要交换 hight--; // 找到需要交换的 } nums[low] = nums[hight]; // 交换 while(low < hight && nums[low] <= pivot) low++; nums[hight] = nums[low]; } nums[low] = pivot; return low; // 当前划分位置，并按这个位置进行子序列划分 } } }