C++自帶排序：
#include <algorithm>
int list[1001];
sort(list,list + 1001);
默認從小到大排序，通過在第三個元素加上cmp，就可以從小到大排序，
排序可以分為內部排序和外部排序兩種，
內部排序：待排序記錄存放在計算機隨機存盤器中（說簡單點，就是記憶體）進行的排序程序，
外部排序：待排序記錄的數量很大，以致于記憶體不能一次容納全部記錄，所以在排序程序中需要對外存進行訪問的排序程序，
衡量效率的方法
內部排序：比較次數，也就是時間復雜度
外部排序：IO次數，也就是讀寫外存的次數
排序方法
內部排序：插入排序、快速排序、選擇排序、歸并排序、基數排序等
外部排序：，多路平衡歸并、置換-選擇排序
1、冒泡排序：
#include <iostream> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void BubbleSort(int arr[], int n) { //從小到大排序 相鄰來兩個數比較，將大的數字往后放 for (int i = 0; i < n - 1; i++) //n-1是因為陣列下標最大為n-1 要進行10輪比較 { //n-1是因為陣列下標最大為n-1 要進行10次比較，再減i是因為每最后的i個元素已經有序不需要繼續排序 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) //兩兩比較，將小的資料放前面 { swap(arr, j + 1, j); //交換arr陣列arr[j+1]和arr[j]的值 } } } } int main() { BubbleSort(a,5); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
2、選擇排序：
#include <iostream> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void SelectSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { swap(arr, i, j); //交換arr陣列arr[i]和arr[j]的值 } } } } int main() { SelectSort(a,5); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
3、插入排序：
#include <iostream> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void InsertSort(int arr[], int n) { int tempVal; for (int i = 1, j; i < n; i++) { tempVal = arr[i]; //保存要插入的值 for (j = i - 1; tempVal < arr[j] && j >= 0; --j) //資料往后移動，給要插入的值騰位 { arr[j + 1] = arr[j]; } arr[j + 1] = tempVal; //插入資料 } } int main() { InsertSort(a,5); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
4、希爾排序：
希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本，但希爾排序是非穩定排序演算法，插入排序是將未排序的數字插入到已排序數列中，而希爾排序是將一個已排序的數列插入到另一個已排序的數列中，
#include <iostream> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void ShellSort(int arr[], int n) { int tempVal, j; int jump = n >> 2; //步長值 while (jump != 0) { for (int i = jump; i < n; i++) { tempVal = arr[i]; //保存待排序的第一個數，也就是待插入的數 for (j = i - jump; j >= 0 && tempVal < arr[j]; j -= jump) { arr[j + jump] = arr[j]; } arr[j + jump] = tempVal; } jump = jump >> 1; //步長值減半 } } int main() { ShellSort(a,5); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
5、歸并排序：
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void _merge_in_arr(int arr[], int left, int mid, int right) { int length = right - left + 1; //定義一個輔助的空間的長度 int *pData = https://www.cnblogs.com/Brimon-zZY/archive/2021/01/07/(int*)malloc(sizeof(int)*length);//分配一個動態記憶體來調整元素的位置 memset(pData, 0, sizeof(int)* length); //合并 int low = left; //左邊區間的起始下標 int hig = mid + 1; //右邊區間的起始下標 int index = 0; //輔助陣列的下標 while (hig <= right)//右區間沒有合并完 { while (low <= mid && arr[low] <= arr[hig])//證明左區間沒有合并完，且左區間的值小于右區間的值 { pData[index] = arr[low]; //把左邊的值放進輔助陣列 low++; //左邊往高位移，下一次需要判斷左邊的新下標 index++; //下一次放進輔助陣列的新下標 } if (low > mid) //證明左區間已經放完 break; while (hig <= right && arr[low] > arr[hig])//證明右區間沒有合并完，且左區間的值大于右區間的值 { pData[index] = arr[hig]; //把右邊的值放進輔助陣列 hig++; //右邊往高位移，下一次需要判斷右邊的新下標 index++; //下一次放進輔助陣列的新下標 } } //到這一步，證明起碼有一個區間已經合并完成 if (hig <= right) //證明右邊沒有完成 memmove(&pData[index], &arr[hig], sizeof(int)* (right - hig + 1)); if (low <= mid) //證明左邊沒有完成 memmove(&pData[index], &arr[low], sizeof(int)* (mid - low + 1)); //把所有區間都合并到了輔助區間 memmove(&arr[left], pData, sizeof(int)* length); free(pData); //釋放空間 } void MergeSort(int arr[], int left, int right) { if (left >= right)//遞回的終止條件，left == right證明這個區間只有一個元素，不需要再拆了 return; int mid = ((right - left) >> 1) + left;//求中點 MergeSort(arr, left, mid); //拆分左 MergeSort(arr, mid + 1, right); //拆分右 //并操作 _merge_in_arr(arr, left, mid, right); } int main() { MergeSort(a,0,4); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
6、桶（基數）排序：
桶排序是典型的空間換時間，在對整數排序中，沒有什么演算法能比它還快，但是非常耗時
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; int a[5] = {1,6,2,8,4}; void swap(int arr[], int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void radix_sort(int arr[], size_t len) { int**temp = (int **)malloc(sizeof(int) * 10); //10行 //申請動態記憶體 輔助陣列temp[10][]; for (int i = 0; i < 10; i++) { temp[i] = (int *)malloc(sizeof(int)*len); } for (int i = 1; i <= 100; i *= 10)//回圈數值可能有的位數 { for (int x = 0; x < 10; ++x)//輔助陣列行回圈 { for (int y = 0; y < len; ++y)//輔助陣列列回圈 { temp[x][y] = -1;//輔助陣列的初始化賦值，-1表示在arr里面不可能出現的數值 } } //arr陣列中的元素放入輔助陣列 for (int m = 0; m < len; ++m) { int index = (arr[m] / i) % 10; temp[index][m] = arr[m]; } //把輔助陣列的內容放回待排序陣列 int k = 0;//待排序的下標 for (int x = 0; x < 10; x++) { for (int y = 0; y < len; ++y) { if (temp[x][y] != -1) arr[k++] = temp[x][y]; } } } //釋放記憶體 for (int i = 0; i < 10; i++) { free(temp[i]); } free(temp); } int main() { radix_sort(a,5); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
我的DEV甚至跑不出來這個的結果Orz，最后還是用Clion跑出來的，
7、快速排序：
將要排序的數列分割成獨立的兩部分，一部分資料比另一部分的資料都要小，整個排序程序可以遞回進行，用到了二分的思想，
快速排序不是一個穩定 的排序演算法，
是對冒泡排序的改進，時間復雜度是O(nlogn).
目前被認為是最好的一種內部排序演算法，
#include <iostream> using namespace std; int a[5] = {1,6,2,8,4}; void qsort(int le, int ri) { int i = le, j = ri, mid = a[(le + ri) / 2]; while(i <= j) { while(a[i] < mid) { //在左邊找大于等于mid的數 i++; } while(a[j] > mid) { //在右邊找小于等于mid的數 j--; } if(i <= j) { swap(a[i],a[j]); //交換 } i++; j--; //繼續找 } /*分別遞回繼續排序*/ if(le < j) { qsort(le,j); } if(i < ri) { qsort(i,ri); } } int main() { qsort(0,4); for(int i = 0; i < 5; i++) { cout << a[i] << " "; } return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/245970.html
標籤：其他
下一篇：Java編程題