概述
排序算法分類
在我們?nèi)粘Ｌ幚頂?shù)據(jù)的時候外构，排序是最經(jīng)常用到，如果一層層的嵌套for循環(huán)會讓代碼的效率變得非常低播掷，這個時候审编，我們就要借用排序的理念來優(yōu)化我們的代碼，目前有十個比較經(jīng)典的排序算法：
1歧匈、冒泡排序
2垒酬、快速排序
3、插入排序
4件炉、希爾排序
5勘究、選擇排序
6、堆排序
7斟冕、歸并排序
8口糕、計數(shù)排序
9、桶排序
10磕蛇、基數(shù)排序
具體的如下圖所示：（圖轉(zhuǎn)自https://www.cnblogs.com/onepixel/articles/7674659.html）
非線性時間比較類排序：通過比較來決定元素間的相對次序景描，由于其時間復(fù)雜度不能突破O(nlogn)，因此稱為非線性時間比較類排序秀撇。
線性時間非比較類排序：不通過比較來決定元素間的相對次序超棺，它可以突破基于比較排序的時間下界，以線性時間運行呵燕，因此稱為線性時間非比較類排序说搅。
算法復(fù)雜度
穩(wěn)定：如果a原本在b前面，而a=b虏等，排序之后a仍然在b的前面。
不穩(wěn)定：如果a原本在b的前面适肠，而a=b霍衫，排序之后 a 可能會出現(xiàn)在 b 的后面。
1侯养、冒泡排序
冒泡排序：
1敦跌、設(shè)置個標識位；
2逛揩、不斷的比較前后兩個元素的大小柠傍，如果前一個值比后一個值大就交換兩個元素的位置，改變標識位的值辩稽，否則不變惧笛，并且指針指向后一個元素；
3逞泄、重復(fù)2的步驟患整，當遇到標識位沒有變化或者循環(huán)結(jié)束拜效，排序完成
代碼塊：
boolean flag = true;
for (int i = 0;i<data.length;i++){
for (int j = 0;j<data.length-i-1;j++){
if (data[j]>data[j+1]){
int temp = data[j+1];
data[j+1] = data[j];
data[j] = temp;
//轉(zhuǎn)換標識位
flag = false;
}
}
if (flag)
//如果沒有進行轉(zhuǎn)換，flag=true各谚，跳出循環(huán)
break;
else
flag = true;
}
2紧憾、快速排序
快速排序：(申明兩個指針，head指向鏈表頭昌渤，tail指向鏈表尾）
從鏈表尾tail開始赴穗，當tail指向元素的值比head大的時候，則tail往前移動一個位置膀息，當tail指向元素的值小于head指向元素的值得時候般眉，交換head和tail所指元素的值，然后從head繼續(xù)開始比較履婉，如果head指向元素的值大于tail指向的值煤篙，則交換head和tail所指元素的值，否則head往后移動一個位置毁腿，直到head=tail的時候辑奈，結(jié)束第一輪循環(huán)。
其實head第一次指向的值已烤，我們稱它為一個基準鸠窗，然后通過上面的思路循環(huán)，最后可以做到這個基準值的左邊是小于它的胯究，基準值得右邊是大于它的稍计，這樣才算完成第一輪的循環(huán)，而左右兩個區(qū)間還是無序數(shù)列裕循，需要通過遞歸的方式蟋恬，一步步對這些無序數(shù)列進行排序。
代碼塊：
public void kpSort(int[] source,int start,int end){
//保留大區(qū)間的頭尾
int i = start;
int j = end;
int value = source[start];
//當i!=j的時候具温，說明本輪循環(huán)還未結(jié)束
while (i<j){
//從鏈表尾開始循環(huán)
while (source[j]>=source[i] && j>i)
j--;
source[i] = source[j];
source[j] = value;
//從鏈表頭開始循環(huán)
while (source[i]<=source[j] && i<j)
i++;
source[j] = source[i];
source[i] = value;
}
//遞歸左右兩個無序區(qū)間的數(shù)列
if (i>start)kpSort(source,start,i-1);
if (j<end)kpSort(source,j+1,end);
}
3冒掌、插入排序
插入排序的思路：
1、從當前排序數(shù)列的第二個元素開始株婴，比較第二個元素與第一個元素的大小怎虫，如果小于則兩個元素互換位置
2、當進行步驟一之后困介，會將指針繼續(xù)指向下一個元素大审，指針前的元素都是排好序的了，那么指針指向下一個元素座哩，比較指針指向元素的值與前一個值的大小徒扶，如果大于則不變，如果小于則將前一個元素后移一位根穷，然后繼續(xù)比較移動元素前一位元素的值酷愧，直到找到比指針指向元素值來的小的值驾诈，則插到該值的后邊
3、循環(huán)第二步操作溶浴，直到數(shù)列尾
這個插入排序還是很好理解的乍迄，也就是當前有個排好序的數(shù)列，如果你要插入一個元素士败，你就需要從后面一個個的往前進行比較闯两，比較的過程中還要將比當前元素大的值往后移動一位，直到找到符合條件的位置谅将，才可以插入漾狼，這樣當前數(shù)列還是一個有序數(shù)列，以此類推循環(huán)到數(shù)列尾饥臂。
代碼塊：
int nowValue;
int preIndex;
for (int i = 1 ;i<data.length;i++){
nowValue = data[i];
preIndex = i-1;
//如果需要比較的前一個元素的索引比0來的大
//或者preIndex所指元素的值大于需要插入的值則后移比較的元素
while (preIndex>=0 && data[preIndex]>nowValue){
data[preIndex+1] = data[preIndex];
preIndex--;
}
data[preIndex+1] = nowValue;
}
4逊躁、希爾排序
希爾排序：希爾排序其實是插入排序的改進版，因為在上面插入排序的過程中隅熙，我們發(fā)現(xiàn)這個排序需要從后面一直往前進行比較稽煤，也就是如果值特別小的情況下，可能還需要進行n次的比較才能進入下一次的插入囚戚，這樣效率上很慢酵熙，在這個基礎(chǔ)上，這個排序算法增多了一個區(qū)間驰坊，也就是保證左邊區(qū)間的值在固定規(guī)則上比右邊來的小匾二，這樣就減少了插入排序可能比較的時間。
代碼塊：
//間隔區(qū)間的值
int grep = data.length/2;
int j;
for (;grep>0;grep/=2){
for (int i = grep;i<data.length;i++){
//nowValue表示當前需要比較元素的值
int nowValue = data[i];
//將當前元素與相隔grep元素的前一個元素進行比較拳芙，找到交換點
for (j = i-grep;j>=0 && data[j]>nowValue;j-=grep){
data[j+grep] = data[j];
}
data[j+grep] = nowValue;
}
}
這個代碼塊最需要注意的其實是最里層的循環(huán)察藐，這個循環(huán)有兩個跳出循環(huán)的條件
1、j>=0:這個條件表示當前指針指向的元素沒有再相隔grep個元素的前一個元素了舟扎，也就是當j為負數(shù)的時候转培，跳出循環(huán)，將比較的值賦值給第一個元素浆竭。
2、data[j]>nowValue:這個條件又是怎么回事呢惨寿，你會發(fā)現(xiàn)我們一開始i是從比較小的值開始的邦泄，也就是從數(shù)組前面的某個位置開始跟相隔grep元素進行比較，在外層裂垦，i的值一直增加顺囊，也就意味著后面j一開始的值也會變得越來越大，然后我們要比較相隔grep元素蕉拢，可能就不止一個了特碳，比如你當前元素可能比相隔2*grep的元素還小诚亚，那么就不可能直接交換了，基于此也可以看出午乓，這個交換也是基于插入排序的站宗，按照插入排序的思路，需要一步步的往前進行比較益愈，直到找到比當前元素還小的值梢灭，就在這個元素后的grep替換元素的值。這個時候蒸其，我們應(yīng)該知道跳出循環(huán)后為啥還有個data[j+grep] = nowValue;語句了敏释，因為如果你要插入的元素剛剛好是第一個元素的情況下（相隔grep前沒有元素），你跳出了循環(huán)摸袁，就沒可能給第一個元素進行賦值操作钥顽，那么最后得到的結(jié)果也就是錯的，這個地方就是為了解決這種情況靠汁。
5蜂大、選擇排序
選擇排序也是一個非常容易理解的排序算法
1、將數(shù)組第一個值作為最小值膀曾，然后遍歷整個數(shù)組县爬，找到真正的最小值，然后跟這個值進行替換
2添谊、循環(huán)一的步驟财喳，直到數(shù)組尾
代碼塊：
int minValue;
int index;
for (int i = 0 ;i<data.length;i++){
minValue = data[i];
index = i;
for (int j = i+1;j<data.length;j++){
if (data[j]<minValue){
minValue = data[j];
index = j;
}
}
data[index] = data[i];
data[i] = minValue;
}
關(guān)于為什么說選擇排序也是不穩(wěn)定排序呢，我舉個例子斩狱，需要排序{5,4,3,5,2}
發(fā)現(xiàn)了什么耳高，我第一次交換的時候，把第一個元素5的值交換到數(shù)組最后所踊，然后再繼續(xù)進行交換的操作泌枪，但是數(shù)組第四個元素5的值會一直在第一個元素5的值得前面，也就是相同元素值排序之后無法保證前后順序秕岛，所以說選擇排序是不穩(wěn)定的排序碌燕。
6、堆排序
堆排序的結(jié)構(gòu)類似于完全二叉樹的結(jié)構(gòu)继薛，有兩種方式進行排序修壕，一種是小根堆，小根堆的根是完全二叉樹中最小的遏考，可以取最小的值保存為數(shù)組的第一個元素慈鸠，以此遞歸，直到數(shù)組結(jié)束灌具；另一種是大根堆青团，大根堆正好和小根堆相反譬巫，大根堆的根是完全二叉樹中最大的，可以取最大的值保存為數(shù)組的最后一個元素督笆，以此遞歸芦昔。
我以大根堆舉例，一個完整的節(jié)點有它的本身節(jié)點胖腾、父節(jié)點烟零、左孩子、右孩子咸作，而大根堆的結(jié)構(gòu)是要保證父節(jié)點肯定比本身節(jié)點來的大锨阿，并且本身節(jié)點、左孩子记罚、右孩子三者中墅诡，本身節(jié)點的值也必須是最大的，只有實現(xiàn)這的規(guī)則才算的上是大根堆桐智。
代碼塊如下：
public static void heapSort(int[] a) {
int i;
//i的第一個取值很重要末早，a.length/2-1的值代表有葉子結(jié)點的最后一個根節(jié)點
//獲取到這個節(jié)點，我們就可以一層層的往上進行調(diào)整
for (i = a.length / 2 -1; i >= 0; i--) {// 構(gòu)建一個大頂堆
adjustHeap(a, i, a.length - 1);
}
for (i = a.length-1; i > 0; i--) {// 將堆頂記錄和當前未經(jīng)排序子序列的最后一個記錄交換
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustHeap(a, 0, i - 1);// 將a中前i-1個記錄重新調(diào)整為大頂堆
}
}
public static void adjustHeap(int[] a, int i, int len) {
int temp, j;
temp = a[i];
//2*i+1代表當前節(jié)點的左孩子
for (j = 2 * i+1; j < len; j = j*2+1) {// 沿關(guān)鍵字較大的孩子結(jié)點向下篩選
//如果左孩子比右孩子小说庭，則將指針指向右孩子
if (j < len && a[j] < a[j + 1])
++j; // j為關(guān)鍵字中較大記錄的下標
//如果左右孩子中最大的一個值不大于根節(jié)點的值然磷，則直接跳出
if (temp >= a[j])
break;
//將左右孩子值中最大的一個并且大于根節(jié)點的值賦值給當前的根節(jié)點
//將指針移到左右孩子中最大的一個，往值大的左或者右二叉樹進行調(diào)整
a[i] = a[j];
i = j;
}
//將最初始指向的值賦值給當前i指向的節(jié)點
a[i] = temp;
}
代碼塊中需要注意幾個點：
第一刊驴，我們建立大頂堆需要獲取到帶有葉子結(jié)點的最后一個根節(jié)點姿搜，從這個根節(jié)點開始往回進行調(diào)整，而這個節(jié)點的值=數(shù)組長度/2-1
第二捆憎，當我們比較完當前節(jié)點和左右孩子中最大的一個值得時候舅柜，同時也要保證左右孩子的下一層結(jié)構(gòu)也符合大頂堆的結(jié)構(gòu)，這樣就需要一層層的往下進行遍歷躲惰，直到?jīng)]有左右孩子為止致份。
7、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法础拨。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用氮块。將已有序的子序列合并，得到完全有序的序列诡宗；即先使每個子序列有序滔蝉，再使子序列段間有序。若將兩個有序表合并成一個有序表僚焦，稱為2-路歸并。
1曙痘、不斷分裂成子序列芳悲，遞歸到左邊界大于等于右邊界返回立肘；
2、將已經(jīng)排序好的子序列不斷合并名扛，直到?jīng)]有子序列谅年，返回結(jié)果。
代碼塊：
public int[] sort(int[] source, int left, int right) {
if (left >= right)
return source;
int mid = (right + left) / 2;
//排序左邊區(qū)域
sort(source, left, mid);
//排序右邊區(qū)域
sort(source, mid + 1, right);
//返回合并的值
return merge(source, left, mid, right);
}
public int[] merge(int[] source, int left, int mid, int right) {
//申請個臨時的數(shù)組空間存儲排序好的子序列
int[] temp = new int[right - left + 1];
//左子序列第一個元素指針
int i = left;
//右子序列第一個元素指針
int j = mid + 1;
//臨時數(shù)組空間索引
int index = 0;
//對左右子序列進行比較大小后插入到臨時數(shù)組
while (i <= mid && j <= right) {
if (source[i] > source[j])
temp[index++] = source[j++];
else
temp[index++] = source[i++];
}
//如果i<=mid說明左子序列已經(jīng)全部插入到臨時數(shù)組空間
//將右子序列剩下的值插入到臨時數(shù)組空間的尾部
while (i <= mid)
temp[index++] = source[i++];
//跟上面正好相反肮韧，右子序列已經(jīng)全部插入融蹂，左子序列剩余部分插入操作
while (j <= right)
temp[index++] = source[j++];
//將臨時數(shù)組數(shù)據(jù)覆蓋本次左右子序列所涉及的數(shù)組范圍
for (int x = 0; x < temp.length; x++)
source[x + left] = temp[x];
return source;
}
在只有十個元素的數(shù)據(jù)量情況下排序費時情況
冒泡排序
選擇排序
插入排序
希爾排序
歸并排序
快速排序
堆排序
總結(jié)
本次學(xué)習(xí)了七種排序算法，受益良多弄企，從上面的時間也可以看出超燃，在數(shù)據(jù)量比較少的時候，歸并排序拘领、快速排序意乓、堆排序其實費時還比較長，所以應(yīng)該根據(jù)不同情況來選擇適合的排序算法约素。
參考鏈接：
https://www.cnblogs.com/onepixel/articles/7674659.html
https://blog.csdn.net/jianyuerensheng/article/details/51263453
https://blog.csdn.net/qq_27680317/article/details/78549875?utm_source=blogxgwz0
https://blog.csdn.net/qq_39776901/article/details/77387923?utm_source=blogxgwz2
https://blog.csdn.net/min996358312/article/details/68068689?utm_source=blogxgwz1
