交換排序的基本思想是兩兩比較待排序元素的關鍵字，發現這兩個元素的次序相反時即進行交換，直到沒有反序的元素為止，本次介紹兩種交換排序，即冒泡排序和快速排序，
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(n2)，是一種穩定的排序方法，
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(nlog2n)，是不穩定的排序方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100184.html
標籤：C++
上一篇：C++分治策略實作快速排序
下一篇：長樂國慶集訓Day1