面試時常常考察的java排序算法--選擇排序、冒泡排序、插入排序

​注：本文是從java語言角度對三種排序算法進行分析比較。​

一、選擇排序

核心思想：

​依次拿目前元素和其後面的元素比較大小，滿足條件就互換值​

public static int[] shunxu(int[] arr){
  int len = arr.length;
  int temp = 0;
  
  for (int i = 0; i < len-1; i++) {
    for (int j = i+1; j < len; j++) {
      if(arr[i] > arr[j]){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}      

解讀：

arr[i]是目前元素，範圍是[0,arr.length-1)

arr[j]是目前元素後面的元素，範圍是[i+1,arr.length)

時間複雜度：

最好的情況是所有數字都是有序的，對于n位的數組，時間複雜度為O(n);

最壞的情況是把順序的排列變成逆序，或者把逆序的數列變成順序。在這種情況下，每一次比較都需要進行交換運算。對于n位的數組，則有比較次數為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，這就得到了最大的比較次數。是以時間複雜度為o(n(n-1)/2)

二、冒泡排序

核心思想：

​依次拿相鄰的元素做比較，滿足條件就互換值。​

​每輪比較找到一個最值（最大或者最小），把其放到末尾​

public static int[] maopao(int[] arr){
  int len = arr.length;
  int temp = 0;
  
  for (int i = 0; i < len-1; i++) {
    for (int j = 0; j < len-1-i; j++) {
      if(arr[j] > arr[j+1]){
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}      

解讀：

外層for循環表示比較輪數，範圍是[0,arr.length-1)，總共比較了length-1輪

内層for循環表示第 i 輪比較的次數，範圍是[0,arr.length-1-i)

每一輪都會産生一個最值（最大值或最小值），則下一輪就少比較一次

外層for循環控制比較的總輪數，該循環是以内層for循環的變量 j 作為數組的下标進行比較

時間複雜度：

最好的情況同選擇排序，即所有數字都是有序的，對于n位的數組，時間複雜度為O(n);

最壞的情況同順序排序，是把順序的排列變成逆序，或者把逆序的數列變成順序。在這種情況下，每一次比較都需要進行交換運算。對于n位的數組，則有比較次數為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，這就得到了最大的比較次數。所有時間複雜度為o(n(n-1)/2)

三、插入排序

核心思想：

​假設前面的數字是有序的，依次拿目前元素與前面元素做比較，滿足條件就互換值​

public static int[] charu(int[] arr){
  int len = arr.length;
  int temp = 0;
  
  for (int i = 1; i < len; i++) {
    for (int j = i; j > 0; j--) {
      if(arr[j] > arr[j-1]){
        temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
      }else{
        break;
      }
    }
  }
  return arr;
}      

解讀：

外層for循環控制輪數，範圍是[1,arr.length)

從第2個數字開始，與前面的數字比較，滿足條件就互換值，否則就放到目前位置（代碼中有break）

時間複雜度：

最好的情況跟上面的相同，是所有數字都是有序的，對于n位的數組，時間複雜度為O(n);

最壞的情況跟上面的相同，是把順序的排列變成逆序，或者把逆序的數列變成順序。在這種情況下，每一次比較都需要進行交換運算。對于n位的數組，則有比較次數為 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2，這就得到了最大的比較次數。所有時間複雜度為o(n(n-1)/2)

三種排序算法對比

根據時間複雜度來比較，三種排序算法的最好和最壞的值都是相同的。是以，我們無法從時間複雜度上面來對比他們。

我們可以從代碼上面分析，由于插入排序代碼裡有一個​break​，以至于不滿足條件的時候，直接中斷内層for循環的執行。是以，相對于其它算法，它的比較次數相應的會少很多，是以效率會更快。

綜合考慮的情況下，插入排序>=冒泡排序>=選擇排序

與其它排序對比：

關注公衆号：​程式員高手之路​

​回複“java項目”，免費擷取java項目視訊教程​