(招生:13908467300 0731-838616321)牛耳教育十六年专注长沙java培训,是湖南最专业的长沙java培训学校。长沙java培训班招生热线:13908467300 0731-838616321

java数据结构与算法——快速排序

核心思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


快速排序采用分治的策略。将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。


java相关代码

publicstaticvoid quickSort(int[] arr, int low, int high){int l = low;int h = high;int key = arr[low];System.out.println("low:"+l+" high:"+h);while(h>l){while(h>l){if(arr[h]<key){ arr[l]= arr[h];break;} h--;}while(h>l){if(arr[l]>key){ arr[h]= arr[l];break;} l++;}} arr[l]= key;for(int j=0; j<arr.length; j++){System.out.print(arr[j]);System.out.print(",");}System.out.println();if(l>low){ quickSort(arr,low,h-1);}if(h<high){ quickSort(arr,l+1,high);}}


     相同,也是O(n^2)。比如一个序列5,4,3,2,1,要排为1,2,3,4,5。按照快速排序方法,每次只会有一个数据进入正确顺序,不能把数据分成大小相当的两份,很明显,排序的过程就成了一个歪脖子树,树的深度为n,那时间复杂度就成了O(n^2)。尽管如此,需要排序的情况几乎都是乱序的,自然性能就保证了。据书上的测试图来看,在数据量小于20的时候,插入排序具有最好的性能。当大于20时,快速排序具有最好的性能,归并(merge sort)和堆排序(heap sort)也望尘莫及,尽管复杂度都为nlog2(n)。


评论