? ? ? ? 交換類排序包括冒泡排序和快速排序兩種。

冒泡排序

? ? ? ? 基本介紹

? ? ? ? 冒泡排序是通過重復比較相鄰元素并交換位置實現排序。其核心思想是每一輪遍歷將未排序序列中的最大（或最小）元素"浮動"到正確位置，類似氣泡上升。

? ? ? ? 基本過程是從序列起始位置開始，逐個比較相鄰的兩個元素，以升序為例，若左邊的元素大于右邊的元素則交換兩個元素的位置，每輪遍歷之后都會使一個最大元素移動到最右邊，在下一輪遍歷時就無需再考慮這個元素。

? ? ? ? 實現過程

? ? ? ? 以升序為例，從起始位置開始遍歷，2 < 5，無需交換，5 < 8，無需交換，8 > 3，需要交換。

? ? ? ? ?交換之后繼續比較8,6,8 > 6，需要交換

? ? ? ? ?交換之后繼續比較，8 < 9，無需交換，繼續比較,9 > 1，需要交換

? ? ? ? ?交換之后繼續比較,9 > 4，需要交換

? ? ? ? 交換之后繼續比較,9 > 7，需要交換?

? ? ? ? 最終完成一輪遍歷，將最大的元素移到了右邊，然后繼續后續遍歷，后續遍歷則不用再考慮9了，再找出一個最大值移到右邊，進行size - 1次遍歷即可完成排序。?

? ? ? ? 代碼展示

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void sort(int *a,int len)
{//len個元素需要排序len - 1次for (int i = 0; i < len - 1; i++){//單輪循環可以找出來一個最大/最小并移到邊上，下一輪循環就不考慮該元素，len - 1次之后只剩下一個元素，無需排序for (int j = 0; j < len - i - 1; j++){if(a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}//打印每輪排序的結果for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}}int main(int argc, char const *argv[])
{sort(array,9);return 0;
}

? ? ? ? 代碼優化?

????????如果在排序過程中，我們發現在某一次遍歷過程中都沒有發生元素交換，那么我們就可以認為序列已經排序完成，此時沒有必要遍歷size - 1次。遍歷size - 1次一定可以使序列有序，但是有些序列執行更少次數的遍歷就已經有序了。所以我們可以減少這些無意義的遍歷，設置一個標志位swap_flag來記錄遍歷過程中是否發生了交換，若無交換則提前結束排序。

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void sort(int *a,int len)
{//len個元素需要排序len - 1次for (int i = 0; i < len - 1; i++){//記錄該輪循環是否發生了交換int swap_flag = 0;//單輪循環可以找出來一個最大/最小并移到邊上，下一輪循環就不考慮該元素，len - 1次之后只剩下一個元素，無需排序for (int j = 0; j < len - i - 1; j++){if(a[j] > a[j + 1]){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;swap_flag = 1;}}//如果本輪循環沒有發生交換，則已經全部有序，跳出循環。if(swap_flag == 0)break;for (int j = 0; j < len; j++){printf("%d ",a[j]);}printf("\n");}}int main(int argc, char const *argv[])
{sort(array,9);return 0;
}

? ? ? ?優化效果對比

????????未經優化的冒泡排序運行結果如下，完整進行了8次(size - 1)遍歷。

? ? ? ? 經優化的冒泡排序運行結果如下，進行了7次遍歷，對于不同的序列，優化效果有所不同。運行結果僅打印了6次是因為break寫在了打印之前，排序完成之后的后一次遍歷才能檢測到排序已完成。

?快速排序

? ? ? ? 基本介紹

????????快速排序的思想是通過一個基準值，把一組數據分成兩個部分（一邊小，一邊大），然后，在對兩個部分，分別找一個基準值，再次進行排序，直至每一個小部分不可再分，所得到的整個數組就成為了有序數組。

? ? ? ? 快速排序的基本過程是先選擇一個數作為基準值 (這里用的是第一個數，key)，進行一次排序，(以升序為例)然后將所有比'基準值小的數'放在基準值的'左邊'， 將所有比'基準值大的數'放在基準值的'右邊'，然后再對兩邊的，各自'再取一個數作為基準值'，然后再次排序（遞歸[自己調自己]）。

? ? ? ? 實現過程

? ? ? ? 定義兩個指示器，low和high，分別指向首尾。定義一個i,j分別指向low和high，用于遍歷。

? ? ? ? ?從 j 開始逐個向左開始和基準值相比較。7大于key，不移動，4 > key，不移動，1 < key，要移動到左邊。由于已經用key保存了基準值，所以放到左邊是可以直接在a[i]處賦值。

? ? ? ? 之后再從左邊開始，1 < key，不動，5 > key，需要移動到右邊，直接在右邊賦值為5即可。放在這里的原因是因為這里的元素已經在前面被移動到了其他位置，不用擔心數據丟失，而且下標位置也屬于右邊。

? ? ? ? 這樣完成一輪之后，發現一開始不符合規律的5已經移到了右邊，不符合規律的1已經移到了左邊。然后繼續移動指示器，尋找不符合規律的元素。從 j 處繼續，9 > key，不移動，6 > key，不移動，3 > key，不移動，8 > key，不移動，比較完8之后，發現 i 已經等于 j 了，此時結束，發現基準值應該插入到 i? 、 j 處，在i 、j 處插入基準值。

? ? ? ? ?然后我們發現，基準值2的左邊都比他小，右邊都比他大，就以基準值為界限，分為了兩部分。

????????然后再對左邊和右邊分別找基準值再進行排序，之后再對分成的兩部分排序，一直遞歸，直到不可再分為止。

????????遞歸最重要的是要找到終止條件，否則就會一直套娃，這里的終止條件是不可再分，不可再分具體表現在哪呢？在本例中，進行一輪之后，以2為界限分為左右兩部分，左邊部分是[low,i - 1],右邊部分是[i + 1,high]，不可再分就代表只有一個元素，即low = i - 1,i + 1 = high時就是不可再分，再加上一個數學限制條件，low應該小于i - 1，所以最終的終止條件是low >= i-1和high <= i+1.

? ? ? ? ?代碼展示

#include <stdio.h>int array[10] = {2,5,8,3,6,9,1,4,7};void quick_sort(int *a,int low,int high)
{//定義兩端的下標int i = low,j = high;//選擇一個基準值，這里選擇第一個元素int key = a[i];//循環之后的結果是，比基準值小的都放在左邊，比基準值大的都放在右邊//同時i,j都在向中間靠近，當i = j時循環跳出，就找到了區分左右的邊界(i、j)//之后a[i] = key是將基準值放在中間的分界。//條件設置為i < j就是因為當i，j相遇時，即找到了分界線的位置（i、j），然后將基準值插入到這個位置上//外層循環一次的結果是將不屬于兩邊的元素互換（比如位于左邊但是沒有小于基準值）while (i < j){//從右邊開始，右邊的元素應比基準值大，尋找不符合的元素while (i < j && a[j] >= key)j--;//將不符合的元素放到左邊，直接覆蓋是因為：//第一次循環，a[i]是基準值，已經用key保存，所以可以覆蓋//之后的循環，a[i]也是不符合條件的元素，已經在上一次循環中被移動，所以可以覆蓋a[i] = a[j];//從左邊開始，左邊的元素應比基準值小，尋找不符合的元素while (i < j && a[i] <= key)i++;//將不符合的元素放到右邊，直接覆蓋是因為a[j]的值已經在上邊被移動了。a[j] = a[i];}//循環結束，i，j相遇//上述循環中，由于基準值已經用key保存了，所以其所在位置充當了一個交換緩沖的角色，//a[i],a[j]的每次移動都讓自己之前的地方成為了下一個移動的目的地a[i] = key;//對基準值左右兩邊的元素再進行快排，直到無法再分//i,j的位置就是基準值，左邊就是[low,i - 1],右邊就是[i + 1,high]//不可再分的條件就是i - 1 和 low不滿足i - 1 > low,i + 1 和 high不滿足i + 1 < highif(i - 1 > low)quick_sort(a,low,i - 1);if(i + 1 < high)quick_sort(a,i + 1,high);
}int main(int argc, char const *argv[])
{quick_sort(array,0,8);for (int j = 0; j < 9; j++){printf("%d ",array[j]);}printf("\n");return 0;
}