排序-快速排序-Java

﹏ヽ暗。殇╰゛Y 2022-06-15 10:40 143阅读 0赞

快排定义一个j 以他为标志，所有其左边比他小，右边比他大。  
lo，hi 两边遍历与j比较。然后遇到不符合的交换lo 与hi的位置

然后递归实现，采用分而治之的办法

![这里写图片描述][SouthEast]  
图片参考：[http://blog.csdn.net/jianyuerensheng/article/details/51258374][http_blog.csdn.net_jianyuerensheng_article_details_51258374]

package sorts;
    
    import object.Example;
    
    public class kuaisu extends Example{ 
    
         public static  int partition(Comparable[] a,int lo,int hi){
              int i=lo,j=hi+1;//左右扫描指针
              Comparable v = a[lo];//这个是以这个v为切分元素
              while(true){
                  while(less(a[++i], v)){
       if(i==hi)break;}
                  //a[i]，i就是lo一直向右移动，如果左边的小于V那么继续循环。
                  while(less(v, a[--j])){
       if(j==lo)break;}
                  //a[j],j就是hi 一直向左移，如果V小于右边的也就是有序的那么继续循环。
    
                  if(i>=j){
       break;}//指针相遇
    
                  exch(a, i, j);
                  //当不满足上面两个while条件也就是左边比V大的，与右边比v小的，进行交换
    
              }
              exch(a, lo, j);//将V=a[j]放入正确的位置,也就是最后的j
              return j;
    
         }
    
         public static void sort(Comparable[] a,int lo, int hi ){
              int N = a.length;
              if(hi<=lo)return;
              int j = partition(a, lo, hi);
              //递归j的左边再来，右边同样。递归结束条件是hi<=lo。也就是一个的时候。
              sort(a,lo,j-1);
              sort(a, j+1, hi);
    
         }
    
         public static void main(String[] a){
              Comparable[] ac = new Comparable[]{
       6,7,5,8,4,9,3,0,3,1,4,8,9};
              sort(ac,0,ac.length-1);
              show(ac);
    
         }
    
    
    
    
    }

改进的方法1到了比较的小的数组后采用插入排序实现，因为插入排序对小的数据更好些。

改进2三分，因为快速排序对重复的数据不是很好。  
可以将其分为比其小的，比起大的，和想等的。

![这里写图片描述][SouthEast 1]

package sorts;
    
    import javax.swing.text.html.HTMLDocument.HTMLReader.HiddenAction;
    
    import object.Example;
    
    public class kuaisu3 extends Example { 
    
         public static void sort(Comparable[] a,int lo,int hi){
              if(hi<=lo)return;//递归结束条件
              int lt=lo,i=lo+1,gt=hi;//定义哨兵，i是指针，定义为lo+1是因为lo是切分元素
              //lt表示最左边，gt表示最右边，交换的时候就是与这两个交换，交换就要移动。
              //i从切分元素后开始移动一直到与指针gt从右边过来相遇结束
              Comparable v = a[lo];//初始V
              while(i<=gt){
                  int cmp = a[i].compareTo(v);//比较i位置与V的值
                  if(cmp<0){exch(a, lt++, i++);}
                  //指针的值小于切分元素，那么就在lt左边，然后指针lt、i都右移
                  else if(cmp>0){exch(a, i, gt--);}
                  //指针的值大于切分元素，那么就在gt的右边，然后gt左移。
                  else {i++;}//相等就不变。
    
              }
              //然后递归
              sort(a, lo, lt-1);
              sort(a, gt+1, hi);
    
         }
    
    
         public static void main(String[] a){
              Comparable[] ac = new Comparable[]{
       6,7,5,8,4,9,3,0,3,1,4,8,9};
              sort(ac,0,ac.length-1);
              show(ac);
         }
    
    }

参考：[http://www.cnblogs.com/kiwibird/p/5026489.html][http_www.cnblogs.com_kiwibird_p_5026489.html]

[SouthEast]: /images/20220615/a2f6ac40763d47808fad23e327ad01c4.png
[http_blog.csdn.net_jianyuerensheng_article_details_51258374]: http://blog.csdn.net/jianyuerensheng/article/details/51258374
[SouthEast 1]: /images/20220615/7af6f020fe2b4ab4a114663258bcef56.png
[http_www.cnblogs.com_kiwibird_p_5026489.html]: http://www.cnblogs.com/kiwibird/p/5026489.html