一直想复习下算法,先把经典的快排复习下,好好理解下分治思想:
先介绍快速排序的算法过程:
[1].记录第一个数位置和最后一个数位置; int i = low; int j = high;[2].找到主元位置,可以是第一个数,也可以是最后一个,或者随机的一个位置,一般可以以数组中第一个位置的数, int povit = a[low],主元选择好了就记录不改变它的值;[3].如果主元是第一个数,则由 j 从后向前搜索,直到找到第一个小于主元的数,与主元进行交换位置.[4].然后由 i 从前向后搜索,找到第一个大于主元的数,并与主元交换位置.
[5].重复[3],[4]步骤,直到 i = j;
a[0] ……….a[7]12,3,5,44,21,8,56,2主元:a[0] = 12;—————————————————————–2,3,5,44,21,8,56,12 i = 1; j = 7;2,3,5,12,21,8,56,44 i = 3;j =6;———————- 一趟完成,开始第二趟————————2,3,5,8,21,12,56,44 i = 4;j = 5;2,3,5,8,12,21,56,44 i = 4;j = 4;———————- 一趟完整移位结束,主元移到了 4 的位置———————————————-此时由主元位置分为前后2个数组——————————-{2,3,5,8} 12 {21,56,44}———————-递归对前后2个数组进行上述移位操作—————————
而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
[java] view plaincopyprint?
- packagetest;importjava.util.Date;importjava.util.Iterator;importjava.util.Properties;publicclasstest{publicstaticvoidmain(Stringargs[]){testt=newtest();Comparablea[]={12,3,5,44,21,8,56,2};t.quickSort(a,0,a.length-1);for(Comparablec:a){System.out.print(c.toString()+",");}}publicvoidquickSort(Comparablea[],intlow,inthigh){if(low<high){inti=partition(a,low,high);//再递归移位i前面一个数组 quickSort(a,low,i-1);//再递归移位i后面一个数组 quickSort(a,i+1,high);}}publicintpartition(Comparablea[],intlow,inthigh){inti=low;intj=high;//主元 Comparablepivot=a[low];if(low<high){while(i!=j){printA(a);//从j开始往前扫描直到第一个小于主元的数字出现,与主元交换while(i<j){if(a[j].compareTo(pivot)<0){swap(a,j,i);break;}j–;}if(i<j){//此时,因为与i互换了位置,i需要向后移动一位i++;}//从i开始往后扫描,直到第一个大于主元的数字出现,与主元交换while(i<j){if(a[i].compareTo(pivot)>0){swap(a,i,j);break;}i++;}if(i<j){//此时,因为与j互换了位置,j需要向前移动一位j–;}printA(a);}}returni;}publicintpartition2(Comparablea[],intl,intr){inti=l,j=r;Comparablex=a[l];//s[l]即s[i]就是第一个坑while(i<j){//从右向左找小于x的数来填s[i]while(i<j&&a[j].compareTo(x)>=0)j–;if(i<j){a[i]=a[j];//将s[j]填到s[i]中，s[j]就形成了一个新的坑i++;}//从左向右找大于或等于x的数来填s[j] while(i<j&&a[i].compareTo(x)<0)i++;if(i<j){a[j]=a[i];//将s[i]填到s[j]中，s[i]就形成了一个新的坑j–;}}//退出时，i等于j。将x填到这个坑中。 a[i]=x;returni;}publicvoidswap(Comparablea[],inti,intj){Comparabletemp=a[i];a[i]=a[j];a[j]=temp;}publicvoidprintA(Comparablea[]){for(Comparablec:a){System.out.print(c.toString()+",");}System.out.println();}}
所有欺骗中，自欺是最为严重的
