牛耳教育|长沙java培训|长沙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)。