首先，對于各個排序算法的原理本文不做講解，可以參考以下兩個部落格：
https://blog.csdn.net/weixin_40205234/article/details/86699088
https://blog.csdn.net/Adusts/article/details/80882649
下面直接上代碼：
#include <iostream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <set>
#include<algorithm>
#include <limits.h>
#include<iomanip>
#include <unordered_set>
#include <assert.h>
#include <math.h>
#include <unordered_map>
using namespace std;
/************二分查找算法*****************/
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int l, r, mid;
l = 0;
r = n - 1;
while (l <= r) {
mid = l + (r - l) / 2;
if (A[mid] == target) {
return mid;
}
else if (A[mid] > target) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
return l;
}
};
/**********************快速排序算法*****************************/
int quick_sort(int *a,int low,int high) // 時間複雜度(O(N*logN))
{
int left = low, right = high;
if (left >= right)
return 0;
int pivot = a[low];
int tmp = 0;
while (left != right){
while ((a[right] >= a[low]) && (left<right))
right--;
while ((a[left] <= a[low]) && (left<right))
left++;
if ((left<right)){
tmp = a[left];
a[left] = a[right];
a[right] = tmp;
}
}
tmp = a[low];
a[low] = a[right];
a[right] = tmp;
quick_sort(a, low, right - 1);
quick_sort(a, right + 1, high);
return 0;
}
int main()
{
int a[9] = {2,3,1,4,5,6,7,0,9};
int low = 0, high = 8;
quick_sort(a,low,high);
for (int i = 0; i < 9;i++)
cout << a[i] << endl;
}
/**********************歸并排序算法*****************************/
/**
* 歸并排序：C++ 時間複雜度(O(N*logN))
*
*
* 将一個數組中的兩個相鄰有序區間合并成一個
*
* 參數說明：
* a -- 包含兩個有序區間的數組
* start -- 第1個有序區間的起始位址。
* mid -- 第1個有序區間的結束位址。也是第2個有序區間的起始位址。
* end -- 第2個有序區間的結束位址。
*/
void merge(int* a, int start, int mid, int end)
{
int *tmp = new int[end - start + 1]; // tmp是彙總2個有序區的臨時區域
int i = start; // 第1個有序區的索引
int j = mid + 1; // 第2個有序區的索引
int k = 0; // 臨時區域的索引
while (i <= mid && j <= end)
{
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++];
// 将排序後的元素，全部都整合到數組a中。
for (i = 0; i < k; i++)
a[start + i] = tmp[i];
delete[] tmp;
}
/*
* 歸并排序(從上往下)
*
* 參數說明：
* a -- 待排序的數組
* start -- 數組的起始位址
* endi -- 數組的結束位址
*/
void mergeSortUp2Down(int* a, int start, int end)
{
if (a == NULL || start >= end)
return;
int mid = (end + start) / 2;
mergeSortUp2Down(a, start, mid); // 遞歸排序a[start...mid]
mergeSortUp2Down(a, mid + 1, end); // 遞歸排序a[mid+1...end]
// a[start...mid] 和 a[mid...end]是兩個有序空間，
// 将它們排序成一個有序空間a[start...end]
merge(a, start, mid, end);
}
/*
* 對數組a做若幹次合并：數組a的總長度為len，将它分為若幹個長度為gap的子數組；
* 将"每2個相鄰的子數組" 進行合并排序。
*
* 參數說明：
* a -- 待排序的數組
* len -- 數組的長度
* gap -- 子數組的長度
*/
void mergeGroups(int* a, int len, int gap)
{
int i;
int twolen = 2 * gap; // 兩個相鄰的子數組的長度
// 将"每2個相鄰的子數組" 進行合并排序。
for(i = 0; i+2*gap-1 < len; i+=(2*gap))
{
merge(a, i, i+gap-1, i+2*gap-1);
}
// 若 i+gap-1 < len-1，則剩餘一個子數組沒有配對。
// 将該子數組合并到已排序的數組中。
if ( i+gap-1 < len-1)
{
merge(a, i, i + gap - 1, len - 1);
}
}
/*
* 歸并排序(從下往上)
*
* 參數說明：
* a -- 待排序的數組
* len -- 數組的長度
*/
void mergeSortDown2Up(int* a, int len)
{
int n;
if (a==NULL || len<=0)
return ;
for(n = 1; n < len; n*=2)
mergeGroups(a, len, n);
}
int main()
{
int i;
int a[] = { 80, 30, 60, 40, 20, 10, 50, 70 };
int ilen = (sizeof(a)) / (sizeof(a[0]));
cout << "before sort:";
for (i = 0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
mergeSortUp2Down(a, 0, ilen - 1); // 歸并排序(從上往下)
//mergeSortDown2Up(a, ilen); // 歸并排序(從下往上)
cout << "after sort:";
for (i = 0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
/**********************冒泡排序算法*****************************/
int main() //O(n2)——n的平方
{
int a[10] = { 0, 1, 5, 8, 7, 6, 3, 9, 4, 2 };
vector<int> res(a, a + 10);
int len = res.size();
for (int i = 0; i<len - 1; i++){
for (int j = 0; j<len - 1 - i; j++){
if (res[j]>res[j + 1]){
int temp = res[j];
res[j] = res[j + 1];
res[j + 1] = temp;
}
}
}
for (int i = 0; i < len; i++)
cout << res[i] << " ";
return 0;
}
/**********************選擇排序算法*****************************/
int main() //O(n2)——n的平方
{
int a[10] = { 0, 1, 5, 8, 7, 6, 3, 9, 4, 2 };
vector<int> arr(a, a + 10);
int len = arr.size();
int minIndex, temp;
for (int i = 0; i<len - 1; i++){
minIndex = i;
for (int j = i + 1; j<len; j++){
if (arr[j]<arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
for (int i = 0; i < len; i++)
cout << arr[i] << " ";
return 0;
}
/**********************插入排序算法*****************************/
int main() //O(n2)——n的平方
{
int a[10] = { 0, 1, 5, 8, 7, 6, 3, 9, 4, 2 };
vector<int> arr(a, a + 10);
int len = arr.size();
int preIndex, current;
for (int i = 1; i<len; i++){
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex]>current){
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
for (int i = 0; i < len; i++)
cout << arr[i] << " ";
return 0;
}
/**********************希爾排序算法*****************************/
int main() //O(n1.3) n的1.3次方
{
int a[10] = { 0, 1, 5, 8, 7, 6, 3, 9, 4, 2 };
vector<int> arr(a, a + 10);
int len = arr.size();
int insertNum;
unsigned gap = len / 2; // initial increment
while (gap) // while gap>=1
{
for (unsigned i = gap; i < len; ++i) // Insertsort within subsequence
{
insertNum = arr[i];//Target number to be inserted into the subsequence
unsigned j = i;
while (j >= gap && insertNum < arr[j - gap])//Find position
{
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = insertNum;
}//end for
gap /= 2;
}//end while(gap)
for(int i = 0; i < len; i++)
cout << arr[i] << " ";
return 0;
}
/**********************堆排序算法*****************************/ // O(nlogn)
void perdown(vector<int> &a, int p, int n) // 這是最大堆
{
int parent, child;
int X;
X = a[p];
for (parent = p; (parent * 2 + 1) < n; parent = child)
{
child = 2 * parent + 1;
if ((child != n - 1) && (a[child] < a[child + 1]))
child++;
if (X>=a[child])
break;
else
a[parent] = a[child];
}
a[parent] = X;
}
int main()
{
int a[10] = { 0, 1, 5, 8, 7, 6, 3, 9, 4, 2 };
vector<int> arr(a, a + 10);
int len = arr.size();
for (int i = len / 2 - 1; i >= 0; i--)
perdown(arr,i,len);
for (int i = len - 1; i>0; i--)
{
swap(arr[0],arr[i]);
perdown(arr, 0, i); //将最大節點沉底，然後采用最大堆排序其餘節點
}
for (int i = 0; i < len; i++)
cout << arr[i] << " ";
return 0;
}
/****************************桶排序算法***********************************/ // O(M+N) M表示桶的個數 N表示資料個數
void bucketsort(vector<int> &res) {
int minvalue = res[0];
int tmp = 0;
for (int i = 1; i < res.size(); i++)
{
if (res[i]<minvalue)
minvalue = res[i];
}
int bucketsize = res.size() / 3; //桶的數量
list<int> *ans = new list<int>[bucketsize];
for (int i = 0; i < res.size(); i++) {
tmp = (res[i] - minvalue) / bucketsize;
ans[tmp].push_back(res[i]);
}
for (int i = 0; i <bucketsize; i++) {
ans[i].sort();
}
for (int i = 0, j = 0; i < res.size(); i++) {
while (ans[j].size() < 1)j++; // 表示桶為空
res[i] = ans[j].front();
ans[j].pop_front();
}
delete[] ans;
}
int main() {
int a[9] = { 9,7,5,6,1,4,3,2,8 };
vector<int> res(a,a+9);
bucketsort(res);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
/*************************基數排序********************************/ // O(N*K) K為桶的個數
void indexsort(vector<int> &res)
{
vector<vector<int> > ans(10, vector<int>(0, 0)); // 10個桶，每個桶存儲根據一位數的排序結果
int mod = 1,count=0,tmp=0;
int maxvalue = res[0];
for (int i = 1; i < res.size(); i++) // 求最大值
{
if (res[i]>maxvalue)
maxvalue = res[i];
}
while (maxvalue) // 求最大位數
{
maxvalue = maxvalue / 10;
count++;
}
for (int i = 0; i < count; i++)
{
for (int j = 0; j < res.size(); j++)
{
tmp = (res[j] /mod)%10;
ans[tmp].push_back(res[j]);
}
mod = mod * 10; // 依次 個十百千萬位
int mid = 0;
for (int j = 0; j < ans.size(); j++)
{
for (int k = 0; k < ans[j].size(); k++)
res[mid++] = ans[j][k]; // 數組重新提取(按先前那一位排序)
ans[j].clear();
}
}
}
int main() {
int a[9] = { 90, 17, 225, 36, 18, 47, 33, 12, 181 };
vector<int> res(a, a + 9);
indexsort(res);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
以上代碼都在本地上跑過了，應該是沒有問題的，大家可以看看原理，然後跟着代碼單步跑一跑，就可以更好的了解原理了
![swmm與lisflood-fp源碼如何一起編譯 CMake指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)