各大排序算法再次整理
冒泡排序
/*
原理是相鄰的數兩兩交換,按照從小到大或者從大到小的順序進行交換,
這樣一趟過去后,最大或最小的數字被交換到了最后一位,
然后再從頭開始進行兩兩比較交換,直到倒數第二位時結束；
*/
#include<stdio.h> #include<iostream> using namespace std; void Bubble_sort(int a[], int n) { int i, j; int temp; //所有排序完整 for (i = 0; i < n-1 ; i++) { for (j = 0; j < n-1-i ; j++) { if (a[j]>a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1]= temp; } } } //一趟排序后的結果 /* for (j = 0; j < n-1; j++) { if (a[j]>a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } }*/ } int main() { int a[101]; int n,i,j; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; Bubble_sort(a, n); for (i = 0; i < n; i++) cout << a[i] << " "; cout<<endl; return 0; }
//由于冒泡排序算法本身就是一種低效算法，即使判斷了在某種條件下已經排序好直接退出，也是十分的耗時
簡單選擇排序
/*
選擇排序:每趟從待排序部分[i,n]中選擇最小的元素，
令其與待排序部分的第一個元素A[i]進行交換，這樣元
素A[i]就會與當前有序區間[1,i-1]形成新的有序區間[1,i]
于是在n趟操作后，所有元素就會是有序的。
總共進行n趟操作，算法復雜度：O(n^2)
*/
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; void slect_sort(int a[],int n) { int i, j, k,temp; for (i = 0; i < n; i++)//進行n趟操作 { k = i; for (j = i; j < n; j++)//選出[i,n]中最小的元素，下標為k { if (a[j] < a[k]) { k = j; } } temp = a[i];//交換a[k]與a[i] a[i] = a[k]; a[k] = temp; } } int main() { int num[50]; int N,i; cin >> N; for (i = 0; i < N; i++) cin >> num[i]; slect_sort(num, N); for (i = 0; i < N; i++) cout << num[i]<<" "; cout << endl; return 0; }
直接插入排序
/*
直接插入排序:每趟從范圍[i，i-1]中尋找某個位置j，（此時A[j]~a[i-1]會后移一位至A[j+1]~A[i]）
使得將A[i]插入位置j后，范圍[1,i]有序。
總共進行n-1趟操作，算法復雜度：O(n^2)
*/
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; void insert_sort(int a[],int n) { int i, j, k,temp; for (i = 1; i < n; i++)//進行n-1趟排序操作 { temp=a[i];//temp臨時存放A[i], j = i;//j從i開始往前枚舉 while (j>0 && temp < a[j - 1])//只要temp小于簽一份元素A[j-1] { a[j] = a[j - 1];//把A[j-1]后移動一位至a[j] j--; } a[j] = temp;//插入位置為j } } int main() { int num[50]; int N,i; cin >> N; for (i = 0; i < N; i++) cin >> num[i]; insert_sort(num, N); for (i = 0; i < N; i++) cout << num[i]<<" "; cout << endl; return 0; }
快速排序
/*
快速排序具有最好的平均性能（average behavior），但最壞性能（worst case behavior）和插入排序
相同，也是O(n^2)。比如一個序列5,4,3,2,1，要排為1,2,3,4,5。按照快速排序方法，每次只會有一個數據進入正確順序，不能把數據分成大小相當的兩份，很明顯，排序的過程就成了一個歪脖子樹，樹的深度為n，那時間復雜度就成了O(n^2)。盡管如此，需要排序的情況幾乎都是亂序的，自然性能就保證了。據書上的測試圖來看，在數據量小于20的時候，插入排序具有最好的性能。當大于20時，快速排序具有最好的性能，歸并(merge sort)和堆排序(heap sort)也望塵莫及，盡管復雜度都為nlog2(n)。
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。
（2）快速排序的基本思想
設當前待排序的無序區為R[low..high]，利用分治法可將快速排序的基本思想描述為：
①分解：
在R[low..high]中任選一個記錄作為基準(Pivot)，以此基準將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置(pivotpos)上，它無須參加后續的排序。
注意：
劃分的關鍵是要求出基準記錄所在的位置pivotpos。劃分的結果可以簡單地表示為(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③組合：
因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什么，可看作是空操作。
2、快速排序算法QuickSort
void QuickSort(SeqList R，int low，int high)
{ //對R[low..high]快速排序
int pivotpos； //劃分后的基準記錄的位置
if(low<high){//僅當區間長度大于1時才須排序
pivotpos=Partition(R，low，high)； //對R[low..high]做劃分
QuickSort(R，low，pivotpos-1)； //對左區間遞歸排序
QuickSort(R，pivotpos+1，high)； //對右區間遞歸排序
}
} //QuickSort
*/
#include<iostream> #include<cstdio> #include <cstring> #include<math.h> #include<algorithm> using namespace std; void quick_sort(int a[], int low,int high) { if (low >= high)/*如果左邊索引大于或者等于右邊的索引就代表已經整理完成一個組了*/ { return; } int first, last, key; first = low; last = high; key = a[first];/*用字表的第一個記錄作為樞軸*/ while (first < last) /*控制在當組內尋找一遍*/ { while (first < last&&a[last] >= key) /*而尋找結束的條件就是，1，找到一個小于或者大于key的數（大于或小于取決于你想升 序還是降序）2，沒有符合條件1的，并且i與j的大小沒有反轉*/ { last--;/*向前尋找*/ } a[first] = a[last]; /*找到一個這樣的數后就把它賦給前面的被拿走的i的值（如果第一次循環且key是 a[left]，那么就是給key）*/ while (first < last&&a[first] <= key) /*這是i在當組內向前尋找，同上，不過注意與key的大小關系停止循環和上面相反， 因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關系相反*/ { first++; } a[last] = a[first]; } a[first] = key;/*當在當組內找完一遍以后就把中間數key回歸*/ quick_sort(a, low, first - 1);/*最后用同樣的方式對分出來的左邊的小組進行同上的做法*/ quick_sort(a, first + 1, high);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/ /*當然最后可能會出現很多分左右，直到每一組的i = j 為止*/ } int main() { int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; quick_sort(a, 0,8); int i; for (i = 0; i < 9; i++) printf("%d\n", a[i]); return 0; }
浙公網安備 33010602011771號