交換排序的基本思想是兩兩比較待排序元素的關鍵字，發現這兩個元素的次序相反時即進行交換，直到沒有反序的元素為止。本次介紹兩種交換排序，即冒泡排序和快速排序。

1 冒泡排序

1. 1 演算法步驟

　　比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

　　對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。

　　針對所有的元素重覆以上的步驟，除了最後一個。

　　持續每次對越來越少的元素重覆上面的步驟，直到沒有任何一對數字需要比較。

實際上，一旦演算法中的某一趟比較時不出現任何元素交換，說明已經排序好了，就可以結束本演算法。

 1 void BubbleSort(RecType arr[],int n)
 2 {   int i,j;
 3     bool exchange;
 4     for(i=0;i<n-1;i++)
 5     {
 6         exchange=false;             //一趟前exchange置為false
 7         for(j=n-1;j>i;j--)
 8         {
 9             if(arr[j]<arr[j-1])
10             {
11                 swap(arr[j],arr[j-1]);   //元素交換
12                 exchange=true;
13             }
14         }
15         if（！exchange）//本趟沒有發生交換，中途結束演算法
16            return;
17     }
18 }

冒泡排序的平均時間複雜度為O(n²)，是一種穩定的排序方法。

2 快速排序(遞歸的方式做)

快速排序(Quick Sort)使用分治法策略。
它的基本思想是：選擇一個基準數，通過一趟排序將要排序的數據分割成獨立的兩部分；其中一部分的所有數據都比另外一部分的所有數據都要小。然後，再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

快速排序流程：
(1) 從數列中挑出一個基準值。
(2) 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的後面(相同的數可以到任一邊)；在這個分區退出之後，該基準就處於數列的中間位置。
(3) 遞歸地把"基準值前面的子數列"和"基準值後面的子數列"進行排序。

 1 int partition(RecType arr[],int s,int t)
 2 {   int i=s,j=t;
 3     RecType tmp=arr[i];  //以arr[i]為基準
 4     while(i<j)   //從兩端交替掃描，右邊先開始。直到i=j 為止
 5     {   while(j>i && arr[j]>tmp)  //從右向左掃描，找到一個小於tmp的
 6             j--;                  //arr[j]，找到的話，放入arr[i]處
 7         a[i]=a[j];
 8 
 9         while(i<j && tmp>=arr[i]) //從左向右掃描，找到一個大於tmp的
10             i++;                  //arr[i]。找到的話，放入arr[j]處
11         a[j]=a[i];
12 
13     }
14     a[i]=tmp;
15     return i;
16 }
17 
18 void QuickSort(RecType arr[],int s,int t)  //對arr[s,t]的元素進行快速排序 增序
19 {
20     int i;
21     if(s<t)
22     {   i=partition(arr,s,t);
23         QuickSort(arr,s,i-1);//對左區間遞歸排序
24         QuickSort(arr,i+1,t); //對右區間遞歸排序
25     }
26 }

快速排序的平均時間複雜度為O(nlog₂n)，是不穩定的排序方法