java排序算法的總結

排序算法類型:

冒泡排序弯予,選擇排序苗沧,插入排序刊棕,希爾排序,快速排序
歸并排序待逞,堆排序甥角,基數排序

一. 冒泡排序(BubbleSort)

1:基本思想:

兩個數比較大小,較大的數下沉识樱,較小的數冒起來嗤无。

2:過程:

1: 比較相鄰的兩個數據,如果第二個數小牺荠,就交換位置翁巍。
2:從后向前兩兩比較,一直到比較最前兩個數據休雌。最終最小
數被交換到起始的位置,這樣第一個最小數的位置就排好
了肝断。
3:繼續(xù)重復上述過程杈曲,依次將第2.3...n-1個最小數排好位置。

image
3 平均時間復雜度:O(n2)
4 java代碼實現:
public static void BubbleSort(int [] arr){
     int temp;//臨時變量
    for(int i=0; i<arr.length-1; i++){   //表示趟數胸懈,一共arr.length-1次担扑。
        for(int j=arr.length-1; j>i; j--){
            
            if(arr[j] < arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}
5 優(yōu)化:
針對問題:

數據的順序排好之后,冒泡算法仍然會繼續(xù)進行下一輪的比較趣钱,直到arr.length-1次涌献,后面的比較沒有意義的。

方案:

設置標志位flag首有,如果發(fā)生了交換flag設置為true燕垃;如果沒有交換就設置為false。
這樣當一輪比較結束后如果flag仍為false井联,即:這一輪沒有發(fā)生交換卜壕,說明數據的順序已經排好,沒有必要繼續(xù)進行下去烙常。

public static void BubbleSort1(int [] arr){
    
    int temp;//臨時變量
    boolean flag;//是否交換的標志
    for(int i=0; i<arr.length-1; i++){   //表示趟數轴捎,一共arr.length-1次。
        
        flag = false;
        for(int j=arr.length-1; j>i; j--){
            
            if(arr[j] < arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = true;
            }
        }
        if(!flag) break;
    }
}
二. 選擇排序(SelctionSort)
1 基本思想:

在長度為N的無序數組中,第一次遍歷n-1個數侦副,找到最小的數值與第一個元素交換侦锯;
第二次遍歷n-2個數,找到最小的數值與第二個元素交換秦驯;
尺碰。。汇竭。
第n-1次遍歷葱蝗,找到最小的數值與第n-1個元素交換,排序完成细燎。

2 過程:
image
3 平均時間復雜度:O(n2)
4 java代碼實現:
  public static void select_sort(int array[],int lenth){
  
  for(int i=0;i<lenth-1;i++){
      
      int minIndex = i;
      for(int j=i+1;j<lenth;j++){
         if(array[j]<array[minIndex]){
             minIndex = j;
         }
      }
      if(minIndex != i){
          int temp = array[i];
          array[i] = array[minIndex];
          array[minIndex] = temp;
      }
  }

}

三. 插入排序(Insertion Sort)
1 基本思想:

在要排序的一組數中两曼,假定前n-1個數已經排好序,現在將第n個數插到前面的有序數列中玻驻,使得這n個數也是排好順序的悼凑。如此反復循環(huán),直到全部排好順序璧瞬。

2 過程:
image
3 平均時間復雜度:O(n2)
4 java代碼實現:
 public static void  insert_sort(int array[],int lenth){
  
  int temp;
  
  for(int i=0;i<lenth-1;i++){
      for(int j=i+1;j>0;j--){
          if(array[j] < array[j-1]){
              temp = array[j-1];
              array[j-1] = array[j];
              array[j] = temp;
          }else{         //不需要交換
              break;
          }
      }
  }
}
四. 希爾排序(Shell Sort)

前言:
數據序列1: 13-17-20-42-28 利用插入排序户辫,13-17-20-28-42. Number of swap:1;
數據序列2: 13-17-20-42-14 利用插入排序,13-14-17-20-42. Number of swap:3;
如果數據序列基本有序嗤锉,使用插入排序會更加高效渔欢。

1 基本思想:

在要排序的一組數中,根據某一增量分為若干子序列瘟忱,并對子序列分別進行插入排序奥额。
然后逐漸將增量減小,并重復上述過程。直至增量為1,此時數據序列基本有序,最后進行插入排序访诱。

2 過程:
image
3 平均時間復雜度O(n1.5)
4 java代碼實現:
 public static void shell_sort(int array[],int lenth){
  
  int temp = 0;
  int incre = lenth;
  
  while(true){
      incre = incre/2;
      
      for(int k = 0;k<incre;k++){    //根據增量分為若干子序列
          
          for(int i=k+incre;i<lenth;i+=incre){
              
              for(int j=i;j>k;j-=incre){
                  if(array[j]<array[j-incre]){
                      temp = array[j-incre];
                      array[j-incre] = array[j];
                      array[j] = temp;
                  }else{
                      break;
                  }
              }
          }
      }
      
      if(incre == 1){
          break;
      }
  }
}
五.快速排序(Quicksort)
1 基本思想:

先從數列中取出一個數作為key值垫挨;
將比這個數小的數全部放在它的左邊,大于或等于它的數全部放在它的右邊触菜;
對左右兩個小數列重復第二步九榔,直至各區(qū)間只有1個數。

2 2. 輔助理解:挖坑填數

初始時 i = 0; j = 9; key=72
由于已經將a[0]中的數保存到key中涡相,可以理解成在數組a[0]上挖了個坑哲泊,可以將其它數據填充到這來。
從j開始向前找一個比key小的數漾峡。當j=8攻旦,符合條件,a[0] = a[8] ; i++ ; 將a[8]挖出再填到上一個坑a[0]中生逸。
這樣一個坑a[0]就被搞定了牢屋,但又形成了一個新坑a[8]且预,這怎么辦了?簡單烙无,再找數字來填a[8]這個坑锋谐。
這次從i開始向后找一個大于key的數,當i=3截酷,符合條件涮拗,a[8] = a[3] ; j-- ; 將a[3]挖出再填到上一個坑中。

數組:72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
0 1 2 3 4 5 6 7 8 9

此時 i = 3; j = 7; key=72
再重復上面的步驟迂苛,先從后向前找三热,再從前向后找。
從j開始向前找三幻,當j=5就漾,符合條件,將a[5]挖出填到上一個坑中念搬,a[3] = a[5]; i++;
從i開始向后找抑堡,當i=5時,由于i==j退出朗徊。
此時首妖,i = j = 5,而a[5]剛好又是上次挖的坑爷恳,因此將key填入a[5]有缆。

數組:48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9

可以看出a[5]前面的數字都小于它,a[5]后面的數字都大于它温亲。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復上述步驟就可以了妒貌。

數組:48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9

3 平均時間復雜度:O(N*logN)
4 java代碼實現:
  public static void quickSort(int a[],int l,int r){
    if(l>=r)
      return;
     
    int i = l; int j = r; int key = a[l];//選擇第一個數為key
    
    while(i<j){
        
        while(i<j && a[j]>=key)//從右向左找第一個小于key的值
            j--;
        if(i<j){
            a[i] = a[j];
            i++;
        }
        
        while(i<j && a[i]<key)//從左向右找第一個大于key的值
            i++;
        
        if(i<j){
            a[j] = a[i];
            j--;
        }
    }
    //i == j
    a[i] = key;
    quickSort(a, l, i-1);//遞歸調用
    quickSort(a, i+1, r);//遞歸調用
}

key值的選取可以有多種形式,例如中間數或者隨機數铸豁,分別會對算法的復雜度產生不同的影響。

六. 歸并排序(Merge Sort)
1 基本思想:參考

歸并排序是建立在歸并操作上的一種有效的排序算法菊碟。該算法是采用分治法的一個非常典型的應用节芥。
首先考慮下如何將2個有序數列合并。這個非常簡單逆害,只要從比較2個數列的第一個數头镊,誰小就先取誰,取了后就在對應數列中刪除這個數魄幕。然后再進行比較相艇,如果有數列為空,那直接將另一個數列的數據依次取出即可纯陨。

//將有序數組a[]和b[]合并到c[]中

void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;

i = j = k = 0;
while (i < n && j < m)
{
    if (a[i] < b[j])
        c[k++] = a[i++];
    else
        c[k++] = b[j++]; 
}

while (i < n)
    c[k++] = a[i++];

while (j < m)
    c[k++] = b[j++];
}

解決了上面的合并有序數列問題坛芽,再來看歸并排序留储,其的基本思路就是將數組分成2組A,B咙轩,如果這2組組內的數據都是有序的获讳,那么就可以很方便的將這2組數據進行排序。如何讓這2組組內數據有序了活喊?
可以將A丐膝,B組各自再分成2組。依次類推钾菊,當分出來的小組只有1個數據時帅矗,可以認為這個小組組內已經達到了有序,然后再合并相鄰的2個小組就可以了煞烫。這樣通過先遞歸的分解數列浑此,再合并數列就完成了歸并排序。

2 過程:
image
3 平均時間復雜度:O(NlogN)

歸并排序的效率是比較高的红竭,設數列長為N尤勋,將數列分開成小數列一共要logN步,每步都是一個合并有序數列的過程茵宪,時間復雜度可以記為O(N)最冰,故一共為O(N*logN)。

4 java代碼實現:
public static void merge_sort(int a[],int first,int last,int temp[]){
 
 if(first < last){
     int middle = (first + last)/2;
     merge_sort(a,first,middle,temp);//左半部分排好序
     merge_sort(a,middle+1,last,temp);//右半部分排好序
     mergeArray(a,first,middle,last,temp); //合并左右部分
 }

}

 //合并 :將兩個序列a[first-middle],a[middle+1-end]合并
 public static void mergeArray(int a[],int first,int middle,int end,int temp[]){     
 int i = first;
 int m = middle;
 int j = middle+1;
 int n = end;
 int k = 0; 
 while(i<=m && j<=n){
     if(a[i] <= a[j]){
         temp[k] = a[i];
         k++;
         i++;
     }else{
         temp[k] = a[j];
         k++;
         j++;
     }
 }   
 while(i<=m){
     temp[k] = a[i];
     k++;
     i++;
 }   
 while(j<=n){
     temp[k] = a[j];
     k++;
     j++; 
 }
 
 for(int ii=0;ii<k;ii++){
     a[first + ii] = temp[ii];
 }

}

三. 堆排序(HeapSort)
1 基本思想:
image

** 圖示:** (88,85,83,73,72,60,57,48,42,6)

image
3 平均時間復雜度:O(NlogN)

由于每次重新恢復堆的時間復雜度為O(logN)稀火,共N - 1次重新恢復堆操作暖哨,再加上前面建立堆時N / 2次向下調整,每次調整時間復雜度也為O(logN)凰狞。二次操作時間相加還是O(N * logN)篇裁。

4 java代碼實現:
//構建最小堆
public static void MakeMinHeap(int a[], int n){
for(int i=(n-1)/2 ; i>=0 ; i--){
    MinHeapFixdown(a,i,n);
}
 }
  //從i節(jié)點開始調整,n為節(jié)點總數 從0開始計算 i節(jié)點的子節(jié)點為 2*i+1, 2*i+2  
   public static void MinHeapFixdown(int a[],int i,int n){
  
  int j = 2*i+1; //子節(jié)點
  int temp = 0;
  
  while(j<n){
      //在左右子節(jié)點中尋找最小的
      if(j+1<n && a[j+1]<a[j]){   
          j++;
      }
      
      if(a[i] <= a[j])
          break;
      
      //較大節(jié)點下移
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      
      i = j;
      j = 2*i+1;
  }

}

  public static void MinHeap_Sort(int a[],int n){
 int temp = 0;
 MakeMinHeap(a,n);
 
 for(int i=n-1;i>0;i--){
     temp = a[0];
     a[0] = a[i];
     a[i] = temp; 
     MinHeapFixdown(a,0,i);
 }   

}

八. 基數排序(RadixSort)
1 基本思想:

BinSort想法非常簡單,首先創(chuàng)建數組A[MaxValue]赡若;然后將每個數放到相應的位置上(例如17放在下標17的數組位置)达布;最后遍歷數組,即為排序后的結果逾冬。

2 過程:

** 圖示:**


image

BinSort
** 問題:**
當序列中存在較大值時黍聂,BinSort 的排序方法會浪費大量的空間開銷。

RadixSort

1 基本思想:

基數排序是在BinSort的基礎上身腻,通過基數的限制來減少空間的開銷产还。

2 過程:
image
image

(1)首先確定基數為10,數組的長度也就是10.每個數34都會在這10個數中尋找自己的位置嘀趟。
(2)不同于BinSort會直接將數34放在數組的下標34處脐区,基數排序是將34分開為3和4,第一輪排序根據最末位放在數組的下標4處她按,第二輪排序根據倒數第二位放在數組的下標3處牛隅,然后遍歷數組即可炕柔。

3 平均時間復雜度:O(d(n+r))
4 java代碼實現:
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
  
  //A:原數組
  //temp:臨時數組
  //n:序列的數字個數
  //k:最大的位數2
  //r:基數10
  //cnt:存儲bin[i]的個數
  
  for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
      
      //初始化
      for(int j=0;j<r;j++){
          cnt[j] = 0;
      }
      //計算每個箱子的數字個數
      for(int j=0;j<n;j++){
          cnt[(A[j]/rtok)%r]++;
      }
      //cnt[j]的個數修改為前j個箱子一共有幾個數字
      for(int j=1;j<r;j++){
          cnt[j] = cnt[j-1] + cnt[j];
      }
      for(int j = n-1;j>=0;j--){      //重點理解
          cnt[(A[j]/rtok)%r]--;
          temp[cnt[(A[j]/rtok)%r]] = A[j];
      }
      for(int j=0;j<n;j++){
          A[j] = temp[j];
      }
  }

}

九 二分查找排序

一.基本思想

1.二分插入排序的基本思想和插入排序一致;都是將某個元素插入到已經有序的序列的正確的位置倔叼;

2.和直接插入排序的最大區(qū)別是汗唱,元素A[i]的位置的方法不一樣;直接插入排序是從A[i-1]往前一個個比較丈攒,從而找到正確的位置哩罪;而二分插入排序,利用前i-1個元素已經是有序的特點結合二分查找的特點巡验,找到正確的位置际插,從而將A[i]插入,并保持新的序列依舊有序显设;

3.時間復雜度:

T(n) = O(n);

     public static void sort(int[] A)  {
     int len =A.length;
     int key = 0;
     int low = high = mid =0;
     for(int i =0 ;i<len;i++)  {
         key = A[i];
         low = 0;
         high = i-1;            
         while(low<=high){    
          mid = (high + low)/2;  
          if(key<A[mid]){
               high = mid -1;
          }
          else{
                  low = mid+1;
           }
         }
       for(int j = i-1;j>=high+1;j--){
              A[j+1] =A[j];
       }
       A[j+1] =key;
     }

}

//http://www.reibang.com/p/ae97c3ceea8d

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末框弛,一起剝皮案震驚了整個濱河市,隨后出現的幾起案子捕捂,更是在濱河造成了極大的恐慌瑟枫,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,657評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件指攒,死亡現場離奇詭異慷妙,居然都是意外死亡,警方通過查閱死者的電腦和手機允悦,發(fā)現死者居然都...
    沈念sama閱讀 92,889評論 3 394
  • 文/潘曉璐 我一進店門膝擂,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人隙弛,你說我怎么就攤上這事架馋。” “怎么了全闷?”我有些...
    開封第一講書人閱讀 164,057評論 0 354
  • 文/不壞的土叔 我叫張陵叉寂,是天一觀的道長。 經常有香客問我总珠,道長办绝,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,509評論 1 293
  • 正文 為了忘掉前任姚淆,我火速辦了婚禮,結果婚禮上屡律,老公的妹妹穿的比我還像新娘腌逢。我一直安慰自己,他們只是感情好超埋,可當我...
    茶點故事閱讀 67,562評論 6 392
  • 文/花漫 我一把揭開白布搏讶。 她就那樣靜靜地躺著佳鳖,像睡著了一般。 火紅的嫁衣襯著肌膚如雪媒惕。 梳的紋絲不亂的頭發(fā)上系吩,一...
    開封第一講書人閱讀 51,443評論 1 302
  • 那天,我揣著相機與錄音妒蔚,去河邊找鬼穿挨。 笑死,一個胖子當著我的面吹牛肴盏,可吹牛的內容都是我干的科盛。 我是一名探鬼主播,決...
    沈念sama閱讀 40,251評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼菜皂,長吁一口氣:“原來是場噩夢啊……” “哼贞绵!你這毒婦竟也來了?” 一聲冷哼從身側響起恍飘,我...
    開封第一講書人閱讀 39,129評論 0 276
  • 序言:老撾萬榮一對情侶失蹤榨崩,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后章母,有當地人在樹林里發(fā)現了一具尸體母蛛,經...
    沈念sama閱讀 45,561評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,779評論 3 335
  • 正文 我和宋清朗相戀三年胳施,在試婚紗的時候發(fā)現自己被綠了溯祸。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,902評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡舞肆,死狀恐怖焦辅,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情椿胯,我是刑警寧澤筷登,帶...
    沈念sama閱讀 35,621評論 5 345
  • 正文 年R本政府宣布,位于F島的核電站哩盲,受9級特大地震影響前方,放射性物質發(fā)生泄漏。R本人自食惡果不足惜廉油,卻給世界環(huán)境...
    茶點故事閱讀 41,220評論 3 328
  • 文/蒙蒙 一惠险、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧抒线,春花似錦班巩、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽逊桦。三九已至,卻和暖如春抑进,著一層夾襖步出監(jiān)牢的瞬間强经,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評論 1 269
  • 我被黑心中介騙來泰國打工寺渗, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留匿情,地道東北人。 一個月前我還...
    沈念sama閱讀 48,025評論 2 370
  • 正文 我出身青樓户秤,卻偏偏與公主長得像码秉,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子鸡号,可洞房花燭夜當晚...
    茶點故事閱讀 44,843評論 2 354