Java實現8種排序算法的示例代碼

冒泡排序 O(n2)
 

兩個數比較大小，較大的數下沉，較小的數冒起來。

  public static void bubbleSort(int[] a) {      //臨時變量      int temp;      //i是循環次數,也是冒泡的結果位置下標，5個數組循環5次      for (int i = 0; i < a.length; i++) {        //從最後向前面兩兩對比，j是比較中下標大的值        for (int j = a.length - 1; j > i; j--) {          //讓小的數字排在前面          if (a[j] < a[j - 1]) {            temp = a[j];            a[j] = a[j - 1];            a[j - 1] = temp;          }        }      }    }

選擇排序 O(n2)

在長度為N的無序數組中，第一次遍歷n-1個數，找到最小的數值與第一個元素交換；
 第二次遍歷n-2個數，找到最小的數值與第二個元素交換；
 。。。
 第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。

  public static void selectSort(int[] a) {      //臨時變量      int temp;      //i是循環次數,也是選擇交換的結果的位置下標，5個數組循環5次      for (int i = 0; i < a.length; i++) {        //最小值下標        int min = i;        for (int j = i + 1; j < a.length; j++) {          if (a[min] > a[j]) {            min = j;          }        }        temp = a[i];        a[i] = a[min];        a[min] = temp;      }    }

插入排序 O(n2)

在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的。如此反覆循環，直到全部排好順序。

  public static void insertSort(int[] a) {      int temp;      //i是循環次數,也是插入的隊列的長度，最後一位是a[i]      //所以一開始a[0]是排好的一個隊列，比較a.length-1次，最後一次循環是a[a.length-1]插入a[0]~a[a.length-2]      for (int i = 0; i < a.length - 1; i++) {        //a[j]是要插入的數字，從a[j]往a[0]比較        for (int j = i + 1; j > 0; j--) {          //如果插入的數小，交換位置          if (a[j] < a[j - 1]) {            temp = a[j];            a[j] = a[j - 1];            a[j - 1] = temp;          } else {            //因為默認a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較後面了            break;          }        }      }    }

希爾排序 O(n1.5)
 

在要排序的一組數中，根據某一增量分為若干子序列，並對子序列分別進行插入排序。
 然後逐漸將增量減小,並重覆上述過程。直至增量為1,此時數據序列基本有序,最後進行插入排序。

  public static void shellSort(int[] a) {      int temp;      int d = a.length;      for (; ; ) {        d = d / 2;        //根據差值分組為子序列        for (int k = 0; k < d; k++) {          //此時對每組數列進行插入排序，數組為a[k+d],a[k+2d]...a[k+n*d]          for (int i = k + d; i < a.length; i += d) {            // a[j]是要插入的數字，從a[j]往a[0]比較,跨度為d            for (int j = i; j > k; j -= d) {              //如果插入的數小，交換位置              if (a[j] < a[j - d]) {                temp = a[j];                a[j] = a[j - d];                a[j - d] = temp;              } else {                //因為默認a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較後面了                break;              }            }          }        }        if (d == 1) {          break;        }      }    }

快速排序 O(N*logN)

先從數列中取出一個數作為base值；
 將比這個數小的數全部放在它的左邊，大於或等於它的數全部放在它的右邊；
 對左右兩個小數列重複第二步，直至各區間只有1個數。

  public void quickSort(int a[], int l, int r) {      //左邊必須大於右邊      if (l >= r) {        return;      }      int i = l;      int j = r;      //選擇第一個數為基準      int base = a[l];      while (i < j) {        //從右向左找第一個小於base的值，如果大於左移一位，直到找到小值或者i/j重合        while (i < j && a[j] > base) {          j--;        }        //從左向右找第一個大於base的值,如果小於右移一位，直到找到大值或者i/j重合        while (i < j && a[i] < base) {          i++;        }        //交換        if (i < j) {          int temp = a[j];          a[j] = a[i];          a[i] = temp;        }      }      //將基準值放到i右移到的位置      a[i] = base;      //將i左邊和i右邊分別排序      quickSort(a, l, i - 1);//遞歸調用      quickSort(a, i + 1, r);//遞歸調用    }

歸併排序 O(N*logN)

歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法的一個非常典型的應用。
 首先考慮下如何將2個有序數列合併。
 這個非常簡單，只要從比較2個數列的第一個數，誰小就先取誰，取了後就在對應數列中刪除這個數。
 然後再進行比較，如果有數列為空，那直接將另一個數列的數據依次取出即可。

  private static void mergeSort(int[] a, int first, int last, int temp[]) {      if (first < last) {        //中間值        int middle = (first + last) / 2;        //左半部分排序        mergeSort(a, first, middle, temp);        //右半部分排序        mergeSort(a, middle + 1, last, temp);        //合併左右部分        mergeArray(a, first, middle, last, temp);      }    }      private 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 r = 0; r < k; r++) {        a[first + r] = temp[r];      }    }

堆排序 O(N*logN)
 

利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

  public static void heapSort(int a[]) {      //堆頂最大值和數組最後（葉節點）交換 長度-1 次      for (int i = a.length - 1; i > 0; i--) {        //構建大頂堆（最大堆）        buildHeap(a, i);        //堆頂最大值和數組最後（葉節點）交換        swap(a, 0, i);      }    }      //構建大頂堆（最大堆）    public static void buildHeap(int a[], int lastIndex) {      //排最後的非葉節點為 長度/2-1，從第i檢查到堆頂第0項，上浮大值      for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {        //必定存在的左葉節點，不一定存在的右葉節點        int left = i * 2 + 1;        int right = i * 2 + 2;        //max為左右葉節點中的最大值        int max = left;        if (right <= lastIndex) {          if (a[left] < a[right]) {            max = right;          }        }        //上浮大值        if (a[i] < a[max]) {          swap(a, i, max);        }      }    }      //交換值    public static void swap(int a[], int i, int j) {      int temp = a[i];      a[i] = a[j];      a[j] = temp;    }

基數排序 O(d(n+r))

【d代表關鍵字有d位，n代表n個記錄，r代表r個空隊列】
 基數排序(radix sort)，相對於常見的比較排序，基數排序是一種分配式排序，即通過將所有數字分配到應在的位置最後再覆蓋到原數組完成排序的過程。

  public static void radixSort(int[] a) {      //位數      int digit = 1;      //作為排序後數組的新下標      int newIndex = 0;      //供基數排序使用的二維數組，第一維度固定10位0~9，第二維度根據下標依次存放每次基數排序的結果      int[][] container = new int[10][a.length];      //第一維度每個數組的內容計數，最少為10，防止數組全是個位數時越界，例如五位數組最大值為8，counter.length=5 ，counter[8]就越界      int counterLength = 10;      if (a.length > 10) {        counterLength = a.length;      }      int[] counter = new int[counterLength];      //算出數組中最大的值，用來確定最大位      int max = a[0];      int maxDigit = 0;      for (int i = 0; i < a.length; i++) {        if (a[i] > max) {          max = a[i];        }      }      while (max > 0) {        max /= 10;        maxDigit++;      }      //對每位進行排序      while (digit <= maxDigit) {        //對每個數值該位取餘,container[remainder]，並計數該位置上數值的下標counter[remainder]        for (int num : a) {          int remainder = (num / digit) % 10;          container[remainder][counter[remainder]] = num;          counter[remainder]++;        }        //將上一步放入容器的數值依次覆蓋到遠數組中        for (int i = 0; i < 10; i++) {          for (int j = 0; j < counter[i]; j++) {            a[newIndex] = container[i][j];            newIndex++;          }          counter[i] = 0;        }        digit *= 10;        newIndex = 0;      }    }