排序算法大致分為內部排序和外部排序兩種
內部排序：待排序的記錄全部放到內存中進行排序，時間復雜度也就等于比較的次數
外部排序：數據量很大，內存無法容納，需要對外存進行訪問再排序，把若干段數據一次讀入內存使用內部排序的方法進行排序后寫入外存，再將這若干個已經排序的數據進行歸并，時間復雜度等于IO(訪問外存)的次數
1、冒泡算法
交換排序。屬于比較簡單直觀的排序算法，以升序為例（從小到大），每次比較相鄰的兩個元素，如果左側元素比右側的大，則交換兩個元素的位置，每次把循環中最大的元素放在循環的最后，像冒泡一樣從小到最大。
1.1 算法步驟
- 比較 a[j] 和 a[j+1]，如果 a[j] > a[j+1]，swap交換兩個元素在數組中的位置
- 讓每一對相鄰元素進行以上的比較，直到把最大的值放到比較的數組最后
- 重復以上步驟n-1次
1.2 時間復雜度
? 總共需要比較次數(n為數組元素個數 n >= 1)：
[O(n)=(n-1)+(n-2)+cdots+1=frac{(n-1)*n}{2}\ 取最高次冪O(n)=n^2 ]
1.3 代碼實現
public int[] bubbleSort(int[] arr) {
// 外層循環，數組長度為 n，循環次數為 n-1
for (int i = 0; i < arr.length - 1; i++) {
// 內層循環，循環次數為 n-1-i，找到一個最大值放在，arr[n-1-i]的位置
for (int j = 0; j < arr.length - 1 - i; j++) {
// 比較相鄰的兩個值，把相對大的值放在數組下標大的地方
if (arr[j] > arr[j + 1]) {
// swap交換
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
1.4 圖示
? 如圖，即使第二次循環已經排好序，但是程序不曉得，仍會繼續循環進行排序，最后一次，只有兩個元素進行排序比較，直接排序完成，排序次數 n-1。
2、快速排序
? 交換排序。選擇一個基準值，將數組劃分兩個區域，左側的值全部比右側的值小，然后分別對兩個區域繼續進行區域的劃分與排序，直到排序完成。
2.1 算法步驟
- 從數組中按照一定的規則選擇一個元素作為基準值
- 把基準值與其他元素進行比較，將元素分成兩部分，把所有比基準值小的值放在左側，所有比基準值大的放在右側。即進行區域劃分
- 通過遞歸上述操作，再次將左右兩區域進行區域劃分，完成排序
2.2 時間復雜度
? 對區域劃分取特殊值，假設n為2的冪，每次都將n個數平均劃分，所以第一次對一整個區域進行循環n次劃分2個區域，第二次對兩個區域分別進行循環(frac{n}{2})次，共n次，劃分4個區域，第三次對4個區域分別進行循環(frac{n}{4})次，共計n次，以此類推，最后一次為第log2n次，劃分的每個區域僅有一個元素。即：
[O(n)=n*log_2n ]
2.3 代碼實現
private static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// 左側右側區間再分別進行排序
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
// 以基準值將數組arr的left~right區間進行分區，保證返回的下標左側元素比基準值小，右側比基準值大
private static int partition(int[] arr, int left, int right) {
// 設定基準值為最左側元素，本身不參與循環中的交換，僅在最后放到index的位置
int pivot = left;
// 該index用于標記一個下標，代表當前已經遍歷的元素中，index位置的元素是最后一個比基準值小的元素
// arr[index]本身以及數組左側元素都小于基準值
int index = left;
// 遍歷left+1~right區間（因為基準值自身不需要進行比較交換）
for (int i = left+1; i <= right; i++) {
if (arr[i] < arr[pivot]) {
// 保證從當前遍歷到的最后一個比基準值小的元素的下一個元素開始交換，所以先++再交換
index++;
swap(arr, i, index);
}
}
// 此時index為分界點，arr[index]<arr[index+1]
// 其他元素交換完畢之后arr[index]的值應該為基準值，所以進行元素位置交換
swap(arr, pivot, index);
// 此時arr[index]兩側元素左小右大
return index;
}
// 元素交換
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2.4 圖示
3、直接插入排序
? 插入排序。每一次把一個待排序的記錄，按照值的大小，插入到有序數組的合適位置。
? 相當于把a[n]分割，先排序數組 a[0] ~ a[1]，再 a[0] ~ a[2]，直到 a[0] ~ a[n] 全部排序完成。
3.1 算法步驟
- 第一個元素之前沒有值，認為已經排序
- 取下一個待排序元素，下標為 i，向前進行比較
- 如果待排序元素比待比較元素小，則交換位置
- 重復步驟3直到有一個元素等于或者小于待排序元素，此次內循環結束，a[0] ~ a[i]排序完成
- 重復步驟2~4，直到最后一個元素
3.2 時間復雜度
? 認為第一元素已經排好序，從第二個元素開始向前比較，計算需要比較的次數：
[O(n) = 1+2+3+cdots+n-1= frac{(n-1)*n}{2}\ 即O(n) = n^2 ]
3.3 代碼實現
public static int[] insertionSort(int[] arr){
// 從第二個元素開始到最后一個元素
for (int i = 1; i < arr.length; i++) {
// 向前遍歷
for( int j = i ; j > 0 ; j -- ){
if( arr[j] < arr[j-1] ){
swap( arr, j , j-1 );
}
else{
break;
}
}
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3.4 圖示
4、希爾排序
? 插入排序。因為設計該算法的人叫Shell，所以叫希爾排序，又稱縮小增量排序。思路上是將待排序序列分割成若干個子序列進行直接插入排序，并逐漸縮減少子序列個數，直到針對整體進行一次排序。
4.1 算法步驟
- 設置一個遞減增量序列 $$t_1,t_2,cdots,t_k$$，(t_k)為1
- 按照增量個數k，整體上對序列進行k次排序
- 每次排序，根據增量 t，將序列分割成 (數組長度 / (t_i)) 個子序列，對子序列分別進行直接插入排序，當增量為1時，對序列整體進行一次排序
4.2 時間復雜度
? 希爾排序的時間復雜度和增量的選擇有關，證明的話我是不會，最壞時間復雜度是(O(n^2))，當n在某個范圍內時，可以達到(O(n^{1.3}))
4.3 代碼實現
/**
該代碼與實際算法步驟有區別：
算法步驟是說針對每個子序列進行直接插入排序，實際上對每個子序列的直插排序是交替進行的
**/
public static void shellSort(int[] arr) {
int length = arr.length;
// 記錄需要進行直接插入排序的值
int temp;
// 增量step從length/2遞減到1進行循環
for (int step = length / 2; step >= 1; step /= 2) {
// 進行直插排序，默認第一個元素已經排序完成，從step下標的元素開始向前進行直插
for (int i = step; i < length; i++) {
// 需要對arr[i]進行直接插入排序，記錄該值
temp = arr[i];
// j來記錄temp最后需要插入的位置
int j = i;
while (j -step >= 0 && arr[j-step] > temp) {
arr[j] = arr[j-step];
j -= step;
}
arr[j] = temp;
}
}
}
// 使用直接插入版本的代碼：
private static void shellSort2(int[] arr) {
int len = arr.length;
for (int step = len / 2; step > 0; step = step / 2) {
// 直接插入排序的代碼，只不過向前遍歷時遍歷的數組為i,i-step,i-step-step...
for (int i = step; i < arr.length; i++) {
for (int j = i; j-step >= 0; j -= step) {
if (arr[j] < arr[j - step]) {
swap(arr, j, j - step);
}
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
4.4 圖示
5、簡單選擇排序
? 選擇排序。從未排序序列中查找一個最小值，然后將該值放到已排序序列的末尾位置，循環下去，直到最后一個元素。
5.1 算法步驟
- 從 a[i] 開始，i=0,1,2,...,n，在數組中找到最小值的下標，放到arr[i]，此時 a[0] ~ a[i] 有序，a[i+1] ~ a[n] 待排序
- 待排序序列重復步驟1
- 經過n-1次循環完成排序
5.2 時間復雜度
? 循環次數為n-1，n-2，n-3，(cdots)，1
[O(n) = (n-1)+(n-2)+cdots+1\ O(n) = frac{1}{2}(n^2-n)\ O(n) = n^2 ]
5.3 代碼實現
public static int[] selectionSort(int[] arr){
// 外層循環經過 n-1 輪比較
for (int i = 0; i < arr.length - 1; i++) {
// min用來記錄每次比較過程中最小值的下標
int min = i;
// 0~i已經排序完成，從i向后比較查找后面序列的最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 記錄最小值元下標
min = j;
}
}
// 將找到的最小值和i位置所在的值進行交換
if (i != min) {
swap(arr, i ,min);
}
}
return arr;
}
5.4 圖示
6、堆排序
? 選擇排序。將待排序列構造誠大根堆，根節點則為序列中最大元素，將該節點與最后一個值交換，把剩余的節點重新構建大根堆，繼續進行交換，直到待排序列只剩下一個值。
? 大根堆（大頂堆）：父節點一定大于兩個子節點的值，即：arr[i] > arr[2i+1] && arr[i] > arr[2i+2]
? 將大根堆映射到數組中示例：
6.1 算法步驟
- 將待排序數組構建成大根堆（仍然是無序的），根節點則為數組最大值
- 將根節點和最后一個節點進行交換，則最大值放到了數組尾部，此時 a[0] ~ a[n-1] 無序
- 因為步驟2進行了節點交換，需要對 a[0] ~ a[n-1] 重新構建大根堆
- 重復步驟 2，3 直到全部有序
6.2 時間復雜度
- 初始化大根堆
? 設元素個數為 n，建堆的高度 (k=log_2(n+1))，
? 第 i 層的非葉子節點的最大操作（交換）次數為 k-i
? 第 i 層的節點個數為 (2^{i-1})
? 所以第 i 層總共需要操作 ((k-i)(2^{i-1})) 次，總共需要操作的次數為
[S = (k-1)*2^0 + (k-2)*2^{1}+(k-3)*2^2+cdots+(k-(k-1))*2^{k-1-1} ]
? 用 2S - S計算 S 的值:
[S = 2^1+2^2+cdots+2^{k-1}-(k-1)\ S = 2^k-k-1 ]
? 將 (k=log_2{(n+1)}Approx log_2n) 代入得
[O(n) = n - log_2n-1 \取最高項O(n) = n ]
? 則初始化大根堆的時間復雜度 O(n) = n
2.重新調整堆
? 根節點和待排序數組的最后一個元素 a[i] 交換之后，需要重新調整堆，最大調整次數 = a[i] 所在堆的層數 = (log_2i)，總共需要調整的次數 = ((n-1)(log_2n)) ，所以調整堆的時間復雜度為
[O(n) = nlog_2n ]
總的時間復雜度 (O(n) = n + nlog_2n = nlog_2n)
6.3 代碼實現
public static int[] HeapSort(int[] arr) {
int len = arr.length;
// 對所有元素建立大根堆
buildMaxHeap(arr, len);
// 從數組尾開始進行循環，每次找到待排序序列的最大值
for (int i = arr.length - 1; i > 0; i--) {
// 此時arr[0]為最大值，交換根節點arr[0]和最后一個節點 i
swap(arr, 0, i);
len--;
// 剩余元素重新建堆
heapify(arr, 0, len);
}
return arr;
}
private static void buildMaxHeap(int[] arr, int len) {
for (int i = len / 2; i >= 0; i--) {
heapify(arr, i, len);
}
}
/**
* @param arr 排序數組
* @param parent 父節點下標
* @param len 待排序數組 length
*/
private static void heapify(int[] arr, int parent, int len) {
// 計算父節點的兩個子節點下標
int left = 2 * parent + 1;
int right = 2 * parent + 2;
// largest為父節點和子節點最大值的下標
int largest = parent;
// 比較左右子節點和父節點的大小
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
// 如果當前的最大值不是當前父節點，需要進行元素交換，
// 交換之后的子節點作為父節點時不一定是大根堆，需要重新建堆
if (largest != parent) {
swap(arr, parent, largest);
heapify(arr, largest, len);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
6.4 圖示
初始化大根堆：
循環取堆頂元素排序：建議自己畫二叉樹更明晰
完整動圖：
7、歸并排序
? 將兩個及以上的有序表合并成一個有序表。以下為兩路合并排序。
? 采用分治法，把無序數組兩兩分割，分割數次，然后自下至上將兩個子序列進行排序，然后合并成一個有序數組，逐漸向上進行兩兩合并，直到合并成一個有序數組。
7.1 算法步驟
- 將數組從中間拆分為兩個無序數組
- 通過遞歸繼續執行步驟 1
- 通過兩個指針指向兩個數組的起始位置
- 比較指針指向的兩個元素，把較小的放入合并數組，移動指針向后
- 重復步驟4直到某一個指針到達數組尾部，此時另一個數組的元素全部不小于合并數組元素
- 將另一個數組的元素放入合并數組
- 繼續歸并，直到剩下一個數組
7.2 時間復雜度
? 時間復雜度 = 兩個數組歸并排序的時間復雜度 + 重建大根堆的時間復雜度
? $f(n) = 2f(frac{n}{2})+ n $
? (n = frac{n}{2}) : : (f(frac{n}{2}) = 2f(frac{n}{4}) + frac{n}{4})
? (n=frac{n}{4}) : : (f(frac{n}{4})=2f(frac{n}{8}) + frac{n}{8})
? (cdots)
? (n=frac{n}{2^{m-1}}) : : (f(frac{n}{2^{m-1}}) = 2f(frac{n}{2^m}) + frac{n}{2^{m-1}})
? 即：(f(n) = 2f(frac{n}{2}) + n)
? (=2[2f(frac{n}{4} + frac{n}{4}) + n]) = $ 22f(frac{n}{22}) + 2n$
? (=2^2[f(2f(frac{n}{8}) + frac{n}{4})] + 2n) = (2^3f(frac{n}{2^3}) + 3n)
? (cdots)
? (=2^mf(frac{n}{2^m}) + mn)
? 當數組被分割成僅剩一個元素時，此時分割為(2^mf(1)+mn) 即： (frac{n}{2^m} = 1)
? 則：(m = log_2n)
? 代入得(f(n) = 2^{log_2n}f(1) + n * log_2n = n + nlog_2n)
? 所以歸并排序的時間復雜度為：
[O(n) = nlog_2n ]
7.3 代碼實現
public static int[] MergeSort(int[] arr) {
// 數組中僅有一個元素==已排序
if (arr.length < 2) {
return arr;
}
// 分割數組的下標
int middle = arr.length / 2;
// 將數組分割成arr[0] ~ arr[middle-1] 和 arr[middle] ~ arr[length-1] 兩部分
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
/**
* 可以拆分為
* int[] arr1 = MergeSort(left);
* int[] arr2 = MergeSort(right);
* 對兩個分割后的數組分別再進行歸并排序
* return merge(arr1, arr2);
*/
return merge2(MergeSort(left), MergeSort(right));
}
/**
* 將兩個數組進行合并方法 1
*/
protected static int[] merge1(int[] left, int[] right) {
// 合并后的數組
int[] result = new int[left.length + right.length];
// i 進行計數，直到等于left或者right數組的長度
int i = 0;
// 循環對left和right數組的首個元素進行比較，把小的放入result數組
// 并重新給left或right數組賦值
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
i++;
}
// 此時left或right數組有一個已經遍歷完畢，直接把剩下的元素全部放入result數組
while (left.length > 0) {
result[i] = left[0];
i++;
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i] = right[0];
i++;
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
/**
* 將兩個數組進行合并方法 2
* 個人還是傾向于這個直觀的
*/
private static int[] merge2(int[] left, int[] right) {
// 合并后的結果
int[] result = new int[left.length + right.length];
// i,j分別用于遍歷left，right數組
int i = 0;
int j = 0;
// count用于放入result數組時的下標計數
int count = 0;
// 循環對left和right數組元素進行比較，并把小的賦值給result[count]
// 直到遍歷完left或者right數組
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[count] = left[i];
i++;
} else {
result[count] = right[j];
j++;
}
count++;
}
// 此時left或right數組有一個已經遍歷完畢，直接把剩下的元素全部放入result數組
while (i < left.length) {
result[count] = left[i];
i++;
count++;
}
while (j < right.length) {
result[count] = right[j];
j++;
count++;
}
return result;
}
7.4 圖示
注：兩個圖不是同一個算法過程
8、基數排序
? 取得最大整數的位數，從個位開始進行比較放入新的數組，再收集起來，此時數組按照個位有序排列，再進位進行比較收集，以此類推，直到最高位比較完成，此時數組全部有序。
8.1 算法步驟
- 取得數組最大數的位數
- 根據數組元素個位數的大小放入不同的數組中
- 按照順序將數組中的元素收集起來，此時新的數組按數組元素的個位數有序
- 數組元素進位（十位、百位...）按照該位的大小重復2、3
- 直到按照最大位數進行元素收集后所有元素有序
8.2 時間復雜度
? 設n個數的最大值是k位數，需要的桶（收集元素的數組）為r個，進行一次遍歷元素收集的時間復雜度為O(n+r)，總的時間復雜度就是O(k(n+r))，一般來說，n >> r 且 n >> k，所以可以認為基數排序的時間復雜度為O(n)，也可以認為事件復雜度為O(kn)。
8.3 代碼實現
private static int[] RadixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 使用二維數組作為桶存放數據
// 考慮負數的情況，其中 [0-9]對應負數，[10-19]對應正數 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
// 收集數組中的數據
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
// 自動擴容，并保存數據
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
// 獲取最高位數
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLength(maxValue);
}
// 獲取最大值
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
// 獲取最大值的長度
protected static int getNumLength(long num) {
if (num == 0) {
return 1;
}
int length = 0;
for (long temp = num; temp != 0; temp /= 10) {
length++;
}
return length;
}
8.4 圖示
小伙伴們有興趣想了解內容和更多相關學習資料的請點贊收藏+評論轉發+關注我，后面會有很多干貨。
