网站被百度删除的原因,产品包装设计与制作,泸县城乡住房建设厅网站,成都专业网站推广1.快速排序的思想快速排序属于交换排序#xff0c;是冒泡排序的升降版。相对于冒泡排序而言#xff0c;快速排序增大了记录比较和移动的距离#xff0c;将关键字较大的记录直接移动到后面#xff0c;将关键字较小的记录直接移动到前面#xff1b;不再是相邻两个记录依次进…1.快速排序的思想快速排序属于交换排序是冒泡排序的升降版。相对于冒泡排序而言快速排序增大了记录比较和移动的距离将关键字较大的记录直接移动到后面将关键字较小的记录直接移动到前面不再是相邻两个记录依次进行比较和交换需要多次移动才能将关键字较大的记录移动到后面。从而快速排序减少了总的比较次数和移动次数。快速排序是指在待排序记录中选择一个记录作为基准记录(通常选择第一个)从待排序两端开始交替比较使得基准记录左侧的记录的关键字都比基准记录的关键字小右侧都比基准记录大这就是一趟快排。再将基准记录分出来的两个区域进行快排以此类推直到每个分区只有一个元素。快速排序采用的分冶法的策略。2.快速排序的本质快速排序本质是不断确定所选基准值的位置当分区中只有一个记录时不需要进行移动排序结束。网上有一张图展示的很到位(侵删)3.代码1 public classQuickSort {2 public int[] quickSort(int[] data, int start, intend){3 if(start end) return null;4 int pivot data[start]; //基准值5 int i start;6 int j end;7 inttmp;8 while(i i data[j] pivot){ //注意这里ji13 j--;14 }15 if(i start){22 tmp data[start];23 data[start] data[j];24 data[j] tmp;25 }26 quickSort(data,start,j-1);27 quickSort(data,j1,end);28 returndata;29 }3031 public static voidmain(String[] args){32 QuickSort sort newQuickSort();33 int[] data {70,30,40,10,80,20,90,100,75,60,45};34 data sort.quickSort(data,0,data.length-1);35 for(intx : data) {36 System.out.println(quickSort x);37 }38 }39 }4.需要注意的地方快排有多种实现方法在一些资料上提到每一趟排序必须右端先走然后左端再走。这样操作的原因是来自于代码的写法他们的代码写法如下1 packagelearn;2 //快速排序3 public classQuickSort {4 public int[] quickSort(int[] data, int start, intend){5 if(start end) return null;6 int pivot data[start]; //基准值7 int i start;8 int j end;9 inttmp;10 while(i i data[j] pivot){//注意这里ji15 //j--;16 //}17 while(ji data[j] pivot){18 j--;19 }20 while(i start){ //当j start避免一趟排序这个约束条件不是必须的30 tmp data[start];31 data[start] data[j];32 data[j] tmp;33 }34 quickSort(data,start,j-1);35 quickSort(data,j1,end);36 returndata;37 }3839 public static voidmain(String[] args){40 QuickSort sort newQuickSort();41 int[] data {70,30,40,10,80,20,90,100,75,60,45};42 data sort.quickSort(data,0,data.length-1);43 for(intx : data) {44 System.out.println(quickSort x);45 }46 }47 }区别在于第11-16行和第17-22行。按照17-22行j 结束的条件是 ji我们考虑一下while( i j)结束后 i j如果让i 先出发i 停在值大于基准值的位置因为 ji 条件的约束j只能也停留在i处这个时候在while( i j)结束后交换data[j] (data[j] data[i])就把大于基准值的data[j]交换到基准值左边了。但按照17-22行让j先出发总会停在小于基准值的位置这样循环结束后和基准值交换是没有问题的。或者按照11-16行的写法谁先出发无所谓只要j 结束的条件变成 j i那么 j 会跑到 i 停下来的前一个位置再停下来这时data[j] 小于基准值和基准值交换是没有问题的。以上就是我对这个问题的一点思考了。
