1、冒泡排序（兩兩比較相鄰的元素僧界，交換位置）
實(shí)現(xiàn)：
private static void BubbleSort(int[] arr,int n){
?? ? for(int i = 0;i
?? ??? ?? ? for(int j = 1;j
?? ??? ??? ?? ? if(arr[j-1] > arr[j]){
?? ??? ??? ??? ?? ? //交換兩個(gè)元素
??? ??? ??? ??? ??? ?? ? int temp = arr[i];
?? ??? ??? ??? ??? ?? ? ?arr[j] = arr[j-1];
?? ??? ??? ??? ??? ??? ??arr[j-1] = temp; ? ??? ??? ??? ??? ?
?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?}?? ??? ??? ??? ?
?? ??? ??? ??? ??? ??? ??? ??? ??? ?}? ????
?? ??? ??? ??? ??? ??? ??? ??? ?} ? ?
?? ??? ??? ??? ??? ??? ??? ??}
特點(diǎn)總結(jié)：
冒泡排序的算法時(shí)間平均復(fù)雜度為O(n2)朋蔫。
空間復(fù)雜度為 O(1)。
冒泡排序?yàn)榉€(wěn)定排序筋帖。
2酗电、選擇排序
1、從待排序序列中典徊，找到關(guān)鍵字最小的元素杭煎；起始假定第一個(gè)元素為最小
2、如果最小元素不是待排序序列的第一個(gè)元素卒落，將其和第一個(gè)元素互換羡铲；
3、從余下的 N - 1 個(gè)元素中儡毕，找出關(guān)鍵字最小的元素也切，重復(fù)1，2步妥曲，直到排序結(jié)束贾费。
實(shí)現(xiàn)：
public static void sort(int[] arr) {?
?int n = arr.length;for(int i = 0; i < n; i++) {?
?int minIndex = i;?
?//for循環(huán) i 之后所有的數(shù)字 找到剩余數(shù)組中最小值得索引
for(int j = i + 1; j < n; j++) {
if(arr[j]< arr[minIndex]) {
?minIndex = j;?
?}
?}
?swap(arr, i, minIndex);?
?}?
?}
?/** * 角標(biāo)的形式 交換元素 */
?private static void swap(int[] arr, int i, int j) {
?int temp = arr[i];
?arr[i] = arr[j];?
?arr[j] = temp;?
?}
選擇排序總結(jié)：
1、選擇排序的算法時(shí)間平均復(fù)雜度為O(n2)檐盟。
2褂萧、選擇排序空間復(fù)雜度為 O(1)。
3葵萎、選擇排序?yàn)椴环€(wěn)定排序导犹。
3、插入排序
插入排序的思想
1羡忘、從第一個(gè)元素開(kāi)始谎痢，該元素可以認(rèn)為已經(jīng)被排序
2、取出下一個(gè)元素卷雕，在已經(jīng)排序的元素序列中從后向前掃描
3节猿、如果該元素（已排序）大于新元素，將該元素移到下一位置
4漫雕、重復(fù)步驟 3滨嘱，直到找到已排序的元素小于或者等于新元素的位置
5、將新元素插入到該位置后
6浸间、重復(fù)步驟 2~5
實(shí)現(xiàn)：
public static void sort(int[] arr) {?
?int n = arr.length;for(int i = 0; i < n; i++) {
?//內(nèi)層循環(huán)比較 i 與前邊所有元素值太雨，如果 j 索引所指的值小于 j- 1 則交換兩者的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
?swap(arr,j-1,j);
?}
?}?
?}
或者這樣實(shí)現(xiàn)：
public static void sort(int[] arr) {
?int n = arr.length;for(int i = 0; i < n; i++) {
?//拎出來(lái)當(dāng)前未排序的這樣牌?
?int e = arr[i];
?//尋找其該放的位置
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
?arr[j]= arr[j-1];
?}
?//循環(huán)結(jié)束后? arr[j] >= arr[j-1] 那么 j 角標(biāo)就是e 應(yīng)該在的位置。
?arr[j] = e;?
?}?
?}
插入排序總結(jié)：
1魁蒜、插入排序的算法時(shí)間平均復(fù)雜度為O(n2)囊扳。
2吩翻、插入排序空間復(fù)雜度為 O(1)。
3锥咸、插入排序?yàn)榉€(wěn)定排序狭瞎。
4、插入排序?qū)τ诮跤行虻臄?shù)組來(lái)說(shuō)效率更高她君，插入排序可用來(lái)優(yōu)化高級(jí)排序算法
4脚作、歸并排序
實(shí)現(xiàn)思想：
1葫哗、申請(qǐng)空間缔刹，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
2劣针、設(shè)定兩個(gè)指針校镐，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3、比較兩個(gè)指針?biāo)赶虻脑剞嗟洌x擇相對(duì)小的元素放入到合并空間鸟廓，并移動(dòng)指針到下一位置
4、重復(fù)步驟3直到某一指針到達(dá)序列尾
5襟己、將另一序列剩下的所有元素直接復(fù)制到合并序列尾
轉(zhuǎn)載自：https://juejin.im/post/5a96d6b15188255efc5f8bbd?utm_source=gold_browser_extension
