class Solution { //quickSort函数 public static void quickSort(int[] arr,int l,int r){ if(l>=r) { return ; } int p=partition(arr, l, r); //找到分界点的下标位置 quickSort(arr,l,p-1); quickSort(arr,p+1,r); } //partition函数，找到第一个元素在数组中的位置，将数组分成两块 public static int partition(int[] arr,int l,int r) { //随机生成一个下标，用来作为这个初始的l，将它与l下标的元素交换一下，再将l位置作为我们的v //下面的代码注释掉是为了提高在leetcode上的运行时间，最好加上这几行代码，具体作用之前已经讲过。// Random m=new Random();// int k= m.nextInt(r-l)+l;// int tp=arr[k];// arr[k]=arr[l];// arr[l]=tp; //将随机化过后的第一个l位置的元素作为我们选择好的v int v=arr[l]; //对于区间[l,i)来说，都是不大于v的，i是当前要判断的那个位置的下标 //而对于区间(j,r]来说，都是不小于v的，j是我们当前要判断的这个位置的下标 int i=l+1; //要判断的第一个i的值 int j=r; //要判断的第一个j的值 while(true) { while(i<=r&&arr[i]<v) i++; //对于i值满足arr【i】小于v，就一直往前走，直到遇见一个不满足条件的，前提要满足边界条件 i<=r; while(j>=l+1&&arr[j]>v) j--; //----------------------------------------------------------------------------一样参上 if(i>j) //上面两个式子都找到了满足条件的，需要交换了，但是前提需要判断一下i和j的顺序，如果此时i和j已经相遇了，说明数组已经是 有序了，可以直接break出去了 { break; } //交换一下元素位置 int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; //i和j继续 i++; j--; } int swap=arr[j]; arr[j]=v; arr[l]=swap; return j; } public int[] sortArray(int[] nums) { quickSort(nums,0,nums.length-1); return nums; }}
转载于:https://www.cnblogs.com/cold-windy/p/11188901.html
