快速排序定义:快速排序是对冒泡排序的一种改进。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。排序原理首先设定一个分界值通过该分界值将数组分成左右两部分将大于或等于分界值的数据放到到数组右边小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值而右边部分中各元素都大于或等于分界值然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后整个数组的排序也就完成了。切分原理快速排序是也是一种分治思想的排序算法把一个数组切分成两个子数组的基本思想找一个基准值用两个指针分别指向数组的头部和尾部先从尾部向头部开始搜索一个比基准值小的元素搜索到即停止并记录指针的位置再从头部向尾部开始搜索一个比基准值大的元素搜索到即停止并记录指针的位置交换当前左边指针位置和右边指针位置的元素重复2,3,4步骤直到左边指针的值大于右边指针的值停止。代码实现 1快速排序API设计:代码publicclassQuick{/* 比较v元素是否小于w元素 */privatestaticbooleanless(Comparable v,Comparable w){returnv.compareTo(w)0;}/* 数组元素i和j交换位置 */privatestaticvoidexch(Comparable[]a,inti,intj){Comparable ta[i];a[i]a[j];a[j]t;}//对数组内的元素进行排序publicstaticvoidsort(Comparable[]a){intlo0;inthia.length-1;sort(a,lo,hi);}//对数组a中从索引lo到索引hi之间的元素进行排序privatestaticvoidsort(Comparable[]a,intlo,inthi){//安全性校验if(hilo){return;}//需要对数组中lo索引到hi索引处的元素进行分组左子组和右子组intpartitionpartition(a,lo,hi);//返回的是分组的分界值所在的索引分界值位置变换后的索引//让左子组有序sort(a,lo,partition-1);//让右子组有序sort(a,partition1,hi);}//对数组a中从索引 lo到索引 hi之间的元素进行分组并返回分组界限对应的索引publicstaticintpartition(Comparable[]a,intlo,inthi){//确定分界值Comparable keya[lo];//定义两个指针分别指向待切分元素的最小索引处和最大索引处的下一个位置intleftlo;intrighthi1;//切分while(true){//先从右往左扫描移动right指针找到一个比分界值小或者相等的元素停止while(less(key,a[--right])){if(rightlo){break;}}//再从左往右扫描移动left指针找到一个比分界值大或者相等的元素停止while(less(a[left],key)){if(lefthi){break;}}//判断 leftright,如果是则证明元素扫描完毕结束循环如果不是则交换元素即可if(leftright){// 一定要是leftright,因为有可能出现left大于right的情况break;}else{exch(a,left,right);}}//交换分界值exch(a,lo,right);//此时只能是和right交换值,因为有可能left此时已经大于right了.returnright;}}测试:publicstaticvoidmain(String[]args){Integer[]data{6,1,6,2,7,9,3,4,5,6,8};System.out.println(排序之前\njava.util.Arrays.toString(data));Quick.sort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}代码实现 2/** * 快速排序 * 通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分关键字小 * 则分别对这两部分继续进行排序直到整个序列有序。 * author shkstart * 2018-12-17 */publicclassQuickSort{privatestaticvoidswap(int[]data,inti,intj){inttempdata[i];data[i]data[j];data[j]temp;}publicstaticvoidquickSort(int[]data){subSort(data,0,data.length-1);}privatestaticvoidsubSort(int[]data,intstart,intend){if(startend){intbasedata[start];intlowstart;inthighend1;while(true){while(lowenddata[low]-base0);while(highstartdata[--high]-base0);if(lowhigh){swap(data,low,high);}else{break;}}swap(data,start,high);subSort(data,start,high-1);//递归调用subSort(data,high1,end);}}publicstaticvoidmain(String[]args){int[]data{9,-16,30,23,-30,-49,25,21,30};System.out.println(排序之前\njava.util.Arrays.toString(data));quickSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}对线排序:importmain.java.Algorithms.DataWrap;publicclassQuickSort02{privatestaticvoidswap(DataWrap[]data,inti,intj){DataWraptempdata[i];data[i]data[j];data[j]temp;}privatestaticvoidsubSort(DataWrap[]data,intstart,intend){if(startend){DataWrapbasedata[start];intistart;intjend1;while(true){while(ienddata[i].compareTo(base)0);while(jstartdata[--j].compareTo(base)0);if(ij){swap(data,i,j);}else{break;}}swap(data,start,j);subSort(data,start,j-1);subSort(data,j1,end);}}publicstaticvoidquickSort(DataWrap[]data){subSort(data,0,data.length-1);}publicstaticvoidmain(String[]args){DataWrap[]data{newDataWrap(9,),newDataWrap(-16,),newDataWrap(21,*),newDataWrap(23,),newDataWrap(-30,),newDataWrap(-49,),newDataWrap(21,),newDataWrap(30,*),newDataWrap(30,)};System.out.println(排序之前\njava.util.Arrays.toString(data));quickSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}快速排序 是不稳定的快速排序需要一个基准值在基准值的右侧找一个比基准值小的元素在基准值的左侧找一个比基准值大的元素然后交换这两个元素此时会破坏稳定性所以快速排序是一种不稳定的算法。快速排序时间复杂度分析快速排序的一次切分从两头开始交替搜索直到left和right重合因此一次切分算法的时间复杂度为O(n).但整个快速排序的时间复杂度和切分的次数相关。最优情况每一次切分选择的基准数字刚好将当前序列等分。如果我们把数组的切分看做是一个树那么上图就是它的最优情况的图示共切分了logn次所以最优情况下快速排序的时间复杂度为O(nlogn);最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数这使得每次切分都会有一个子组那么总共就得切分n次所以最坏情况下快速排序的时间复杂度为O(n^2);最坏情况下快速排序的时间复杂度为O(n^2);平均情况:每一次切分选择的基准数字不是最大值和最小值也不是中值这种情况我们也可以用数学归纳法证明快速排序的时间复杂度为O(nlogn),快速排序的平均时间复杂度为O(nlogn),小结:最佳情况T(n) O(nlogn)最差情况T(n) O(n2)平均情况T(n) O(nlogn) 不稳定
快速排序定义:快速排序是对冒泡排序的一种改进。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。排序原理首先设定一个分界值通过该分界值将数组分成左右两部分将大于或等于分界值的数据放到到数组右边小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值而右边部分中各元素都大于或等于分界值然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后整个数组的排序也就完成了。切分原理快速排序是也是一种分治思想的排序算法把一个数组切分成两个子数组的基本思想找一个基准值用两个指针分别指向数组的头部和尾部先从尾部向头部开始搜索一个比基准值小的元素搜索到即停止并记录指针的位置再从头部向尾部开始搜索一个比基准值大的元素搜索到即停止并记录指针的位置交换当前左边指针位置和右边指针位置的元素重复2,3,4步骤直到左边指针的值大于右边指针的值停止。代码实现 1快速排序API设计:代码publicclassQuick{/* 比较v元素是否小于w元素 */privatestaticbooleanless(Comparable v,Comparable w){returnv.compareTo(w)0;}/* 数组元素i和j交换位置 */privatestaticvoidexch(Comparable[]a,inti,intj){Comparable ta[i];a[i]a[j];a[j]t;}//对数组内的元素进行排序publicstaticvoidsort(Comparable[]a){intlo0;inthia.length-1;sort(a,lo,hi);}//对数组a中从索引lo到索引hi之间的元素进行排序privatestaticvoidsort(Comparable[]a,intlo,inthi){//安全性校验if(hilo){return;}//需要对数组中lo索引到hi索引处的元素进行分组左子组和右子组intpartitionpartition(a,lo,hi);//返回的是分组的分界值所在的索引分界值位置变换后的索引//让左子组有序sort(a,lo,partition-1);//让右子组有序sort(a,partition1,hi);}//对数组a中从索引 lo到索引 hi之间的元素进行分组并返回分组界限对应的索引publicstaticintpartition(Comparable[]a,intlo,inthi){//确定分界值Comparable keya[lo];//定义两个指针分别指向待切分元素的最小索引处和最大索引处的下一个位置intleftlo;intrighthi1;//切分while(true){//先从右往左扫描移动right指针找到一个比分界值小或者相等的元素停止while(less(key,a[--right])){if(rightlo){break;}}//再从左往右扫描移动left指针找到一个比分界值大或者相等的元素停止while(less(a[left],key)){if(lefthi){break;}}//判断 leftright,如果是则证明元素扫描完毕结束循环如果不是则交换元素即可if(leftright){// 一定要是leftright,因为有可能出现left大于right的情况break;}else{exch(a,left,right);}}//交换分界值exch(a,lo,right);//此时只能是和right交换值,因为有可能left此时已经大于right了.returnright;}}测试:publicstaticvoidmain(String[]args){Integer[]data{6,1,6,2,7,9,3,4,5,6,8};System.out.println(排序之前\njava.util.Arrays.toString(data));Quick.sort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}代码实现 2/** * 快速排序 * 通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分关键字小 * 则分别对这两部分继续进行排序直到整个序列有序。 * author shkstart * 2018-12-17 */publicclassQuickSort{privatestaticvoidswap(int[]data,inti,intj){inttempdata[i];data[i]data[j];data[j]temp;}publicstaticvoidquickSort(int[]data){subSort(data,0,data.length-1);}privatestaticvoidsubSort(int[]data,intstart,intend){if(startend){intbasedata[start];intlowstart;inthighend1;while(true){while(lowenddata[low]-base0);while(highstartdata[--high]-base0);if(lowhigh){swap(data,low,high);}else{break;}}swap(data,start,high);subSort(data,start,high-1);//递归调用subSort(data,high1,end);}}publicstaticvoidmain(String[]args){int[]data{9,-16,30,23,-30,-49,25,21,30};System.out.println(排序之前\njava.util.Arrays.toString(data));quickSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}对线排序:importmain.java.Algorithms.DataWrap;publicclassQuickSort02{privatestaticvoidswap(DataWrap[]data,inti,intj){DataWraptempdata[i];data[i]data[j];data[j]temp;}privatestaticvoidsubSort(DataWrap[]data,intstart,intend){if(startend){DataWrapbasedata[start];intistart;intjend1;while(true){while(ienddata[i].compareTo(base)0);while(jstartdata[--j].compareTo(base)0);if(ij){swap(data,i,j);}else{break;}}swap(data,start,j);subSort(data,start,j-1);subSort(data,j1,end);}}publicstaticvoidquickSort(DataWrap[]data){subSort(data,0,data.length-1);}publicstaticvoidmain(String[]args){DataWrap[]data{newDataWrap(9,),newDataWrap(-16,),newDataWrap(21,*),newDataWrap(23,),newDataWrap(-30,),newDataWrap(-49,),newDataWrap(21,),newDataWrap(30,*),newDataWrap(30,)};System.out.println(排序之前\njava.util.Arrays.toString(data));quickSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}快速排序 是不稳定的快速排序需要一个基准值在基准值的右侧找一个比基准值小的元素在基准值的左侧找一个比基准值大的元素然后交换这两个元素此时会破坏稳定性所以快速排序是一种不稳定的算法。快速排序时间复杂度分析快速排序的一次切分从两头开始交替搜索直到left和right重合因此一次切分算法的时间复杂度为O(n).但整个快速排序的时间复杂度和切分的次数相关。最优情况每一次切分选择的基准数字刚好将当前序列等分。如果我们把数组的切分看做是一个树那么上图就是它的最优情况的图示共切分了logn次所以最优情况下快速排序的时间复杂度为O(nlogn);最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数这使得每次切分都会有一个子组那么总共就得切分n次所以最坏情况下快速排序的时间复杂度为O(n^2);最坏情况下快速排序的时间复杂度为O(n^2);平均情况:每一次切分选择的基准数字不是最大值和最小值也不是中值这种情况我们也可以用数学归纳法证明快速排序的时间复杂度为O(nlogn),快速排序的平均时间复杂度为O(nlogn),小结:最佳情况T(n) O(nlogn)最差情况T(n) O(n2)平均情况T(n) O(nlogn) 不稳定
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
