排序算法

排序算法，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。一般默認(rèn)排序是按照由小到大即升序排列。

冒泡排序

冒泡排序（Bubble Sort）簡單的基于比較的排序算法。每次比較相鄰兩個元素，如果他們的順序錯誤就把他們交換過來。由于較大的數(shù)據(jù)會不斷地向上”冒“，所以以冒泡排序命名。

算法步驟

• 從頭開始，比較相鄰元素，如果順序不對，就交換。
• 每次選出一個局部最大值
• 走過n - 1 趟后，數(shù)組就有序了

動圖

代碼

public class P02_BubbleSort {public static void bubbleSort(int[] arr) {if(arr == null || arr.length < 2) {return;}for(int i = 0;i < arr.length - 1;i++) {for(int j = 0;j < arr.length - 1 - i;j++) {if(arr[j] > arr[j + 1]) {swap(arr,j,j + 1);}}}}public static void swap(int[] arr,int i,int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = {9,8,7,6,5,4,3,2,1};bubbleSort(arr);System.out.println(Arrays.toString(arr));}
}

優(yōu)化

 public static void bubbleSort(int[] arr) {if(arr == null || arr.length < 2) {return;}for(int i = 0;i < arr.length - 1;i++) {boolean success = false; for(int j = 0;j < arr.length - 1 - i;j++) {if(arr[j] > arr[j + 1]) {swap(arr,j,j + 1);success = true;}}if(success == false) {break;// 已經(jīng)有序}}
}

總結(jié)

冒泡排序的時間復(fù)雜度$O(N)$，空間復(fù)雜度$O(1)$，冒泡排序是一種性能比較差的排序，如果不優(yōu)化，那么無論是何種數(shù)據(jù)狀況，都要經(jīng)理$N^2$次比較。冒泡排序大量浪費比較行為，每趟比較只會選擇出一個最大值，所以性能較差。

選擇排序

選擇排序是一種簡單直觀的基于比較的排序算法，性能不受數(shù)據(jù)狀況的左右，就算是已經(jīng)有序的數(shù)據(jù)，也是$O(N^2)$的時間復(fù)雜度。

算法步驟

（不用交換的沒有畫出）

• 0 ~ n - 1 范圍 找到最小值 交換到 0 位置
• 1 ~ n - 1 范圍 找到最小值 交換到 1 位置
• 2 ~ n - 1 范圍 找到最小值 交換到 2 位置
• … …
• n - 2 ~ n - 1 范圍找到較小值 交換到 n - 2 位置
• 排序完成

動圖

代碼

package package01;import java.util.Arrays;public class P01_SelectSort {public static void selectSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) {minIndex = arr[minIndex] < arr[j] ? minIndex : j;}swap(arr, minIndex, i);}}public static void swap(int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = {9,8,7,6,5,4,3,2,1};selectSort(arr);System.out.println(Arrays.toString(arr));}
}

總結(jié)

選擇排序也是一種性能較差的排序算法，性能不受數(shù)據(jù)狀況左右，大量浪費比較行為。

插入排序

插入排序就像打撲克時拿牌一樣，一張一張將撲克牌放到對應(yīng)的位置，也是一個基于比較的排序。只是插入排序受數(shù)據(jù)狀況影響，當(dāng)數(shù)據(jù)狀況趨于有序時，插入排序的速度會非?？?#xff0c;趨于$O(N)$，但是時間復(fù)雜度是最壞情況，所以插入排序的時間復(fù)雜度是$O(N^2)$.

算法步驟

就如上述數(shù)據(jù)，我們要將這組數(shù)字從小到大進(jìn)行排列。從左往右依次考慮每個數(shù)字，讓這個數(shù)字左邊局部有序，考慮完整個數(shù)據(jù)就有序了。

• 考慮前 $1$ 個數(shù) 已經(jīng)有序
• 考慮前 $2$ 個數(shù)，如果前面的數(shù)據(jù)大于當(dāng)前數(shù)則交換，做到局部有序
• 考慮前 $3$ 個數(shù)，如果前面的數(shù)據(jù)大于當(dāng)前數(shù)則交換，做到局部有序
• … …
• 考慮前 $n?1$ 個數(shù)，如果前面的數(shù)據(jù)大于當(dāng)前數(shù)則交換，做到局部有序
• 完成排序

動圖

代碼

package package01;import java.util.Arrays;public class P03_InsertSort {public static void insertSort(int[] arr) {if(arr == null || arr.length < 2) {return;}for(int i = 1;i < arr.length;i++) {for(int j = i - 1;j >= 0 && arr[j] > arr[j + 1];j--) {swap(arr,j,j+1);}}}public static void swap(int[] arr,int i,int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = {0,9,8,7,6,5,4,3,2,1};insertSort(arr);System.out.println(Arrays.toString(arr));}
}

總結(jié)

插入排序的常數(shù)時間要優(yōu)于選擇排序和插入排序，但是其時間復(fù)雜度仍然是$O（N^2）$

如果本篇文章對你有幫助，請點贊、評論、轉(zhuǎn)發(fā)，你的支持是我創(chuàng)作的動力。