在上篇文章我們詳細介紹了排序的概念與插入排序，大家可以通過下面這個鏈接去看：

排序的概念及插入排序

這篇文章就介紹一下一種排序方式：交換排序。

一，交換排序

基本思想：兩兩比較，如果發生逆序則交換，直到所有記錄都排好序為止。

而交換排序又分為兩種：

????????冒泡排序O(n2)

快速排序O( nlog2n )

1，冒泡排序

A 基本內容

學習過C語言的朋友應該對這個比較熟悉，其基本思想就是：??

每趟不斷將記錄兩兩比較，并按“前小后大” 規則交換

如圖進行一次冒泡排序的過程：

21，25，49， 25*，16，? 08

21，25，25*，16， 08 ， 49

21，25， 16， 08 ，25*，49

21，16， 08 ，25， 25*，49

16，08 ，21， 25， 25*，49

08，16， 21， 25， 25*，49

?冒泡排序的優點：

每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；?

??? 一旦下趟沒有交換，還可提前結束排序

在c語言的代碼中實際就是通過兩個for循環來實現?

void main() 			 
{	int a[11];		/*a[0]不用，之用a[1]~a[10]*/int i,j,t;printf("\nInput 10 numbers: \n");for(i=1;i<=10;i++)	scanf("%d",&a[i]);	printf("\n");for(j=1;j<=9;j++)for(i=1;i<=10-j;i++)if(a[i]>a[i+1])	{t=a[i];a[i]=a[i+1];a[i+1]=t;}//交換for(i=1;i<=10;i++)	printf("%d ",a[i]);   
}

下面是一個例子?

下面這段代碼與上面的區別是，當遇見數組部分有序時，可以提前結束循環，節省不必要的時間。

1. 定義了一個名為bubble_sort的函數，接受一個順序表L作為參數。
2. 初始化變量m為順序表的長度減1，flag為1，表示是否需要繼續排序。
3. 使用while循環進行排序，條件是m > 0且flag == 1。當m等于0時，說明已經遍歷完所有元素；當flag為0時，說明在一次循環中沒有發生任何交換，說明已經排序完成。
4. 在while循環內部，使用for循環遍歷順序表中的元素，從第一個元素到第m個元素。
5. 在for循環內部，比較當前元素L.r[j].key和下一個元素L.r[j+1].key的大小。如果當前元素的鍵值大于下一個元素的鍵值，則交換這兩個元素的位置，并將flag設置為1，表示發生了交換。
6. 每次循環結束后，將m減1，縮小未排序部分的范圍。
7. 當while循環結束時，順序表L中的元素已經按照升序排列。

void bubble_sort(SqList &L){ int m,i,j,flag=1;   RedType x;m=n-1;while((m>0)&&(flag==1)){  flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){  flag=1;x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; //交換}//endifm--;}//endwhile}

B 冒泡排序的算法分析：

最好情況下：?只需 1趟排序，比較次數為 n-1，不移動 ?

while((m>0)&&(flag==1)){  flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){  flag=1;  x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x; } ……     

最壞情況下：?需 n-1趟排序，第i趟比較n-i次，移動3(n-i)次?

冒泡排序

時間復雜度為 o(n2)?

空間復雜度為 o(1)

是一種穩定的排序方法

2，快速排序

A 基本內容

基本思想：

?在數組中，我們通過兩個指針來實現排序過程

?后面也是一樣的操作，我們會發現每趟子表的形成從兩頭向中間交替式逼近，對各子表操作相似，因此我們可采用遞歸算法來實現對數據的排序過程。

// 快速排序算法
void main()
{QSort(L, 1, L.length); // 對數組L進行快速排序
}// 快速排序函數，參數為待排序的數組L，起始下標low和結束下標high
void QSort(SqList &L, int low, int high)
{if (low < high){pivotloc = Partition(L, low, high); // 獲取基準元素的位置QSort(L, low, pivotloc - 1);       // 對基準元素左邊的子數組進行快速排序QSort(L, pivotloc + 1, high);      // 對基準元素右邊的子數組進行快速排序}
}// 劃分函數，參數為待排序的數組L，起始下標low和結束下標high
int Partition(SqList &L, int low, int high)
{L.r[0] = L.r[low]; // 將第一個元素作為基準元素pivotkey = L.r[low].key;while (low < high){// 從右向左找到第一個小于基準元素的下標while (low < high && L.r[high].key >= pivotkey)--high;L.r[low] = L.r[high]; // 將找到的元素放到左邊// 從左向右找到第一個大于基準元素的下標while (low < high && L.r[low].key <= pivotkey)++low;L.r[high] = L.r[low]; // 將找到的元素放到右邊}L.r[low] = L.r[0]; // 將基準元素放到正確的位置return low;        // 返回基準元素的下標
}

?B 快速排序的算法分析：

?最好情況：劃分后，左右子序列長度相同

最壞情況：遞歸樹成為單支樹?

到此交換排序就結束了， 如果文章對你有用的話請點個贊支持一下吧！

下篇文章將更新選擇排序的內容。