嘉兴建设规划网站,沈阳哪家公司做网站好,湘潭网络公司网站建设,网上做代卖的网站思路#xff1a; #xff08;1#xff09;首先定义一个递归函数#xff1a;qucikSort(int [ ] arr,int l,int r)。函数的定义#xff1a;给定一个数组arr#xff0c;对它在[l,r]这个区间内的元素进行排序#xff0c;从而使得整个数组在[l,r]这个区间内有序。 #xff0…思路 1首先定义一个递归函数qucikSort(int [ ] arr,int l,int r)。函数的定义给定一个数组arr对它在[l,r]这个区间内的元素进行排序从而使得整个数组在[l,r]这个区间内有序。 2每次排序后得到一个索引p索引p左边的元素都小于它索引p右边的元素都大于它此时我们就可以到[l,p - 1]、[p1,r]这两个区间上继续排序直至lr区间内没有元素可排序为止。 3对区间[l,r]排序时首先确定基准元素pv选择区间内最右的元素arr[r]随后维护两个指针i、jj指针用于寻找在[l,r - 1]区间内比pv小的元素i指针用于在j指针找到比pv小的元素时交换i、j两个指针指向元素的位置同时i指针向右移动为下一次位置交换做准备。 4退出循环后区间[0,i - 1]区间的所有元素都小于pv[i,r - 1]区间的所有元素都大于pv。此时再交换i、r两个索引处的元素位置基准元素被交换到了索引i处基准元素的位置固定后续不再参与排序。 Code 1generate方法随机生成一个需要排序的数组
//生成一个长度为n元素值在1-v之间的整型数组private static int [] generate(int n,int v){int [] result new int[n];for (int i 0; i n; i) {result[i] (int) ((Math.random() * v) 1);}return result;} 2递归函数quickSort
//递归函数定义:对数组arr在[l,r]区间上的元素进行排序private static void quickSort(int [] arr,int l,int r){//l r:区间内只有一个元素不用排序//l r:区间内没有元素不用排序if(l r)return;//p:排好序的元素的索引在arr[p]左边都是小于它的元素右边都是大于它的元素int p partition(arr,l,r);quickSort(arr,p 1,r);quickSort(arr,l,p - 1);} 3swap方法交换两个元素arr[a]、arr[b]的位置
//交换arr[a]、arr[b]两个元素的为止private static void swap(int [] arr,int a,int b){int temp arr[a];arr[a] arr[b];arr[b] temp;} 4关键的排序方法
private static int partition(int [] arr,int l,int r){//选取[l,r]这个区间内最右边的元素:arr[r]作为基准元素pvint pv arr[r];//i:在[l,r]这个区间内如果元素比基准元素小那么这个元素就会被交换到i索引处int i l;//从索引l开始遍历整个区间for(int j l;j r;j ){//碰到比基准元素pv小的元素时if(arr[j] pv) {//交换arr[i]、arr[j]两个元素的位置swap(arr, i, j);//i是为了下一次交换位置做准备i;}}//循环结束时[l,r - 1]这个区间内所有比基准元素小的元素都在[0,i - 1]这个区间上//此时交换arr[i]、arr[r]两个元素的位置基准元素此时就是arr[i]//在arr[i]左边都是小于它的元素在arr[i]右边都是大于它的元素swap(arr,i,r);//返回索引i索引i上的元素位置不再发生变动return i;} 5测试
public static void main(String[] args) {//生成一个长度为10元素值在1-10之间的数组int[] test generate(10, 10);System.out.println(排序前Arrays.toString(test));quickSort(test,0,test.length - 1);System.out.println(排序后 Arrays.toString(test));} 6输出结果 总结 1首先明确base case当l r时数组不需要进行排序。 2每次排序确定一个索引位置pp左边都是小于它的元素p右边都是大于它的元素它不再参与排序。 3索引位置p确定后需要排序就只剩下区间[l,p - 1]、[p 1,r]不断递归直至l r时排序结束。
