快捷導(dǎo)航

快速排序和分治排序介紹

更新時(shí)間：2015年04月08日 22:38:27 投稿：mdxy-dxy

這篇文章主要介紹了快速排序和分治排序,需要的朋友可以參考下

快速排序讓我看了很久，也折磨了我很長(zhǎng)時(shí)間，因?yàn)榇篌w上的思路我是有了，但是寫(xiě)代碼時(shí)總是出現(xiàn)各種問(wèn)題，要想把它調(diào)試出來(lái)對(duì)我個(gè)人來(lái)說(shuō)還是有一定難度的，而且因?yàn)楣ぷ骱屯祽械脑?，?dǎo)致之前調(diào)試不出來(lái)的錯(cuò)誤放了很久，今天終于出來(lái)啦，還是有些小激動(dòng)的哦，下面來(lái)分享一下我的代碼并做一點(diǎn)點(diǎn)說(shuō)明。

　　要學(xué)會(huì)快速排序，就必須先要學(xué)會(huì)分治法，分治的思想是給一串亂序的數(shù)字（數(shù)字是假設(shè)，也可以是其他的對(duì)象，當(dāng)然方法的參數(shù)可以自己定義哦，我在這里假設(shè)有一個(gè)整型的數(shù)組吧）然后給他一個(gè)中間數(shù)，分治法會(huì)把這些數(shù)字以給他的那個(gè)是中間數(shù)為分界分為兩部分，一部分在中間數(shù)的左邊，另一部分在右邊，以這個(gè)數(shù)為分界點(diǎn)，兩邊的數(shù)現(xiàn)在還是亂序的，我給他定義的方法如下：

//left是數(shù)組的想分治部分的左端點(diǎn)，right是數(shù)組分治部分的總端點(diǎn)，如長(zhǎng)度為10的數(shù)組，我想對(duì)前5個(gè)整數(shù)進(jìn)行分治，則傳0，4即可
  public int signalFenZhi(int left,int right){
    if(left<0||left>n-1||right<0||right>n-1){
      return -1;
    }
    int temp = test[left];
    int j=right;
    int i=left;
    
    while(i<j){
      while(test[j]>=test[left]&&i<j){
        j--;
      }
      while(test[i]<=test[left]&&i<j){
        i++;
      }
      
      if(i<j){
        temp = test[i];
        test[i]=test[j];
        test[j]=temp;
      }
    }
    
    if(i==j){
      temp = test[i];
      test[i]=test[left];
      test[left]=temp;
    }
    
    for(int m=0;m<n;m++){
      System.out.print(test[m]+"   ");
    }
    
    return i;
      
  }

當(dāng)然，也可以把那個(gè)中間數(shù)當(dāng)參數(shù)傳進(jìn)來(lái)，現(xiàn)在我只是單純的以數(shù)組的傳進(jìn)來(lái)的第left數(shù)做為分界數(shù)，這只是為了說(shuō)明。

　　明白了分治，那么快速排序也就簡(jiǎn)單了，那就是對(duì)已經(jīng)分為兩部分的數(shù)再進(jìn)行分治，依次類(lèi)推，直到全部的數(shù)字都有序?yàn)橹?，代碼如下：

public void quickSort(int left,int right){
    if(right-left<1){
      return ;
    }else{
      int point = this.signalFenZhi(left, right);
      System.out.println(point);
      //if(point!=left&&point!=right){
        quickSort(left,point-1);
        quickSort(point+1,right);
      //}
    }
  }

快速排序的效率在眾多的排序算法中是很優(yōu)秀的，時(shí)間復(fù)雜度為O(N*log2n),但是如果分治的分界點(diǎn)選的不好的話(huà)，時(shí)間復(fù)雜度將會(huì)降到（n的平方）,因?yàn)槿绻眠@個(gè)數(shù)組是有序的，然后我們每次都取傳過(guò)來(lái)的最左端的數(shù)，那么效率就會(huì)很低，所以要避免發(fā)生這種情況，如果檢測(cè)所有的選項(xiàng)，那么將會(huì)很花時(shí)間，所以一個(gè)折中的辦法，就是把最左端的數(shù)和最右端的數(shù)加上一個(gè)中間的數(shù)，找到他們?nèi)齻€(gè)中間的數(shù)，以這個(gè)為分界值就會(huì)變的好一點(diǎn)，在上面方法的基礎(chǔ)上，修改以后的代碼如下，但是我做完了以后這樣的做法不是很好，應(yīng)該把分界值也當(dāng)做傳給分治的方法會(huì)好些，細(xì)心的朋友可以自己試一下，我在這里就不試了哈，大體上是一樣的哦！

package com.jll;

public class FenZhi {
  
  int[] test;
  
  int n=10;
  
  public FenZhi(){
    test = new int[10];
    
    for(int i=0;i<n;i++){
      test[i]=(int)(Math.random()*100)+1;
      System.out.print(test[i]+"   ");
    }
    System.out.println();
  }
  
  public FenZhi(int n){
    if(n>0){
      this.n=n;
      test = new int[n];
      
      for(int i=0;i<n;i++){
        test[i]=(int)(Math.random()*100)+1;
      }
    }
  }
  
  public int signalFenZhiMajorizationFirst(int left,int right){
    if(left<0||left>n-1||right<0||right>n-1||left>=right){
      return -1;
    }
    
    if(right-left>=2){
      int middle = (right+left)/2;
      if(test[left]>test[middle]){
        int temp = test[middle];
        test[middle] = test[left];
        test[left] = temp;
      }
      if(test[left]>test[right]){
        int temp = test[left];
        test[left] = test[right];
        test[right] = temp;
      }
      if(test[middle]>test[right]){
        int temp = test[middle];
        test[middle] = test[right];
        test[right] = temp;
      }
      int temp = test[middle];
      test[middle] = test[left];
      test[left] = temp;
      int j=right-1;
      int i=left+1;
      
      while(i<j){
        while(test[j]>=test[left]&&i<j){
          j--;
        }
        while(test[i]<=test[left]&&i<j){
          i++;
        }
        
        if(i<j){
          temp = test[i];
          test[i]=test[j];
          test[j]=temp;
        }
      }
      if(i==j){
        temp = test[i];
        test[i]=test[left];
        test[left]=temp;
      }
      
      /*if(i==j){
        temp = test[middle];
        test[middle]=test[i];
        test[i]=temp;
      }*/
      
      /*for(int m=0;m<n;m++){
        System.out.print(test[m]+"   ");
      }*/
      
      return i;
    }else {
      if(test[right]<test[left]){
        int temp = test[right];
        test[right] = test[left];
        test[left] = temp;
      }
      return right;
    }
  }
  
  public void quickSortMajorizationFirst(int left,int right){
    if(right-left<1){
      return ;
    }else{
      int point = this.signalFenZhiMajorizationFirst(left, right);
      System.out.println("the point is:"+point);
      quickSortMajorizationFirst(left,point-1);
      quickSortMajorizationFirst(point+1,right);
    }
  }
  
  public static void main(String[] args) {
    FenZhi f = new FenZhi();
    System.out.println(f.signalFenZhiMajorizationFirst(0, 9));
    System.out.println();
    f.quickSortMajorizationFirst(0,f.n-1);
    
    //f.quickSort(0,f.test.length-1);
    for(int i:f.test){
      System.out.print(i+" ");
    }
  }
}

代碼運(yùn)行如下：

95   40   64   18   78   23   73   84   40   


the point is:4
the point is:1
the point is:3
the point is:7
the point is:6
the point is:9
18 23 40 40 64 73 78 84 95

以上就是我學(xué)習(xí)到的東西，記錄一下，以備后面查閱。