八大排序演算法JAVA實現（時間複雜度O(n*n)篇）

本文主要描述3個時間複雜度為n²的排序演算法：冒泡排序、選擇排序、插入排序。

1.冒泡排序：由數組頭部開始，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。每次交換完成後，當前數組最大值就會被放在最後。

 1     public int[] bubbleSort(int[] a, int n)
 2     {
 3         for (int j = 0; j < n - 2; j++)
 4         {
 5             for (int i = 0; i < n - j - 1; i++)
 6             {// 如果當前數比下一個大，交換，否則繼續看下一個數
 7                 if (a[i] > a[i + 1])
 8                 {
 9                     int temp = a[i + 1];
10                     a[i + 1] = a[i];
11                     a[i] = temp;
12                 }
13             }
14         }
15         return a;
16     }
17     

傳入參數：a為待排序數組，n為數組長度。

第一個for迴圈，用j的值控制第二個迴圈，即比對數組的長度。由冒泡排序的定義可知，每一次都會將最大值放在最後，所以下一次排的時候就可以少管一個數；

第二個for迴圈，將兩個數比對，大的放在後面。

本題第一個for迴圈是一種小小的優化，可以不使用，直接對整個數組進行交換也是沒有問題的。

2.選擇排序：每次在數組中選擇最小的一個數，將其依次放在數組頭對應位置。

 1     public int[] selectionSort(int[] a, int n)
 2     {
 3         for (int j = 0; j < n - 1; j++)
 4         {//j表示需要在以j開始的數組裡面尋找一個最大值填充j位
 5             int maxi = 0;
 6             for (int i = 0; i < n - j; i++)
 7             {// maxi表示當前序列最大值的下標
 8                 if (a[maxi] < a[i])
 9                 {
10                     maxi = i;
11                 }
12             }
13             if (maxi != n - j - 1)
14             {
15                 int temp = a[n - j - 1];
16                 a[n - j - 1] = a[maxi];
17                 a[maxi] = temp;
18             }
19         }
20         return a;
21     }

3.插入排序：將其模擬為往一個有序數組中插入一個值。關鍵在於需要把有序數組比當前數大的數字一個個往後移動。

 1     public int[] insertionSort(int[] a, int n)
 2     {
 3         for (int i = 1; i < n; i++)
 4         {//認為a[0]只有一個數，是有序的。所以從第二個數開始插入
 5             int nowNum = a[i];
 6             int j = i - 1;
 7             for (; j >= 0; j--)
 8             {//把所有比插入數大的數字往後挪，迴圈結束後就會留出一個空位
 9                 if (nowNum < a[j])
10                 {
11                     a[j + 1] = a[j];
12                 }
13                 else
14                 {
15                     break;
16                 }
17             }
18             a[++j] = nowNum;
19         }
20         return a;
21     }