廢話不多說，直接上代碼！

Talk is cheap.Show me the code.

#include <iostream> #include <string> #include "stdio.h"using namespace std;void PrintArr(string str,int arr[], int len ,bool bisSorted = true) {cout << str;for (int i = 0; i < len; i++){cout << arr[i] << " ";}cout << endl; }//交換數(shù)值 //統(tǒng)一封裝接口 void SwapValue(int &a, int &b) {int tmp = 0;tmp = a;a = b;b = tmp; }//冒泡排序 void BubbleSort(int arr[], int len) {int i, j = 0;for (i = 0;i< len -1;i++){for (j = 0;j < len -1 - i; j++){if (arr[j] > arr[j + 1]){SwapValue(arr[j], arr[j + 1]);}}} }//插入排序 void InsertionSort(int arr[],int len) {int i, j= 0;//在要排序的一組數(shù)中，假定前n-1個(gè)數(shù)已經(jīng)排好序，現(xiàn)將第n個(gè)數(shù)插到前面的有序數(shù)列中，//使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。for (i = 0; i < len - 1; i++){for (j = i + 1; j > 0; j--){if (arr[j] < arr[j - 1]){SwapValue(arr[j],arr[j - 1]);}else{break;}}} }//希爾排序 void ShellSort(int a[], int len) {int i, j, k, tmp, gap; // gap 為步長for (gap = len / 2; gap > 0; gap /= 2) { // 步長初始化為數(shù)組長度的一半，每次遍歷后步長減半,for (i = 0; i < gap; ++i) { // 變量 i 為每次分組的第一個(gè)元素下標(biāo) for (j = i + gap; j < len; j += gap) { //對(duì)步長為gap的元素進(jìn)行直插排序，當(dāng)gap為1時(shí)，就是直插排序tmp = a[j]; // 備份a[i]的值k = j - gap; // j初始化為i的前一個(gè)元素（與i相差gap長度）while (k >= 0 && a[k] > tmp) {a[k + gap] = a[k]; // 將在a[i]前且比tmp的值大的元素向后移動(dòng)一位k -= gap;}a[k + gap] = tmp;}}} }//快速排序 void QuickSort(int *a, int left, int right) {if (left >= right)/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個(gè)組了*/{return;}int i = left;int j = right;int key = a[left];while (i < j) /*控制在當(dāng)組內(nèi)尋找一遍*/{while (i < j && key <= a[j])/*而尋找結(jié)束的條件就是，1，找到一個(gè)小于或者大于key的數(shù)（大于或小于取決于你想升序還是降序）2，沒有符合條件1的，并且i與j的大小沒有反轉(zhuǎn)*/{j--;/*向前尋找*/}a[i] = a[j];/*找到一個(gè)這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是a[left]，那么就是給key）*/while (i < j && key >= a[i])/*這是i在當(dāng)組內(nèi)向前尋找，同上，不過注意與key的大小關(guān)系停止循環(huán)和上面相反，因?yàn)榕判蛩枷胧前褦?shù)往兩邊扔，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/{i++;}a[j] = a[i];}a[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/QuickSort(a, left, i - 1);/*最后用同樣的方式對(duì)分出來的左邊的小組進(jìn)行同上的做法*/QuickSort(a, i + 1, right);/*用同樣的方式對(duì)分出來的右邊的小組進(jìn)行同上的做法*//*當(dāng)然最后可能會(huì)出現(xiàn)很多分左右，直到每一組的i = j 為止*/ }//選擇排序 void SelectionSort(int arr[], int len) {int i, j = 0;for (i = 0; i < len - 1; i++){int min = i;for (j = i + 1; j < len; j++) //走訪未排序的元素{if (arr[j] < arr[min]) //找到目前最小值{min = j; //記錄最小值}}//做交換SwapValue(arr[min], arr[i]);} }//計(jì)數(shù)排序 void CountSort(int data[], int n) {int i, j, count, *data_p, temp;data_p = (int*)malloc(sizeof(int)*n);for (i = 0; i < n; i++)//初始化data_p{data_p[i] = 0;}for (i = 0; i < n; i++){count = 0;for (j = 0; j < n; j++)//掃描待排序數(shù)組{if (data[j] < data[i])//統(tǒng)計(jì)比data[i]值小的值的個(gè)數(shù){count++;}}while (data_p[count] != 0)//對(duì)于相等非0的數(shù)據(jù)，應(yīng)向后措一位。數(shù)據(jù)為0時(shí)，因數(shù)組data_p被初始化為0，故不受影響。{/* 注意此處應(yīng)使用while循環(huán)進(jìn)行判斷，若用if條件則超過三個(gè)重復(fù)值后有0出現(xiàn) */count++;}data_p[count] = data[i];//存放到data_p中的對(duì)應(yīng)位置}//用于檢查當(dāng)有多個(gè)數(shù)相同時(shí)的情況i = 0, j = n;while (i < j){if (data_p[i] == 0){temp = i - 1;data_p[i] = data_p[temp];}//of ifi++;}//of whilefor (i = 0; i < n; i++)//把排序完的數(shù)據(jù)復(fù)制到data中{data[i] = data_p[i];}free(data_p);//釋放data_p }/** 桶排序** 參數(shù)說明：* a -- 待排序數(shù)組* n -- 數(shù)組a的長度* max -- 數(shù)組a中最大值的范圍*/ void BucketSort(int a[], int n, int max) {int i, j;int *buckets;if (a == NULL || n < 1 || max < 1)return;// 創(chuàng)建一個(gè)容量為max的數(shù)組buckets，并且將buckets中的所有數(shù)據(jù)都初始化為0。if ((buckets = (int *)malloc(max * sizeof(int))) == NULL)return;memset(buckets, 0, max * sizeof(int));// 1. 計(jì)數(shù)for (i = 0; i < n; i++)buckets[a[i]]++;// 2. 排序for (i = 0, j = 0; i < max; i++)while ((buckets[i]--) > 0)a[j++] = i;free(buckets); }// 遞歸的方式實(shí)現(xiàn)歸并排序 #define MAXSIZE 10 // 實(shí)現(xiàn)歸并，并把結(jié)果存放到list1 void merging(int *list1, int list1_size, int *list2, int list2_size) {int i, j, k, m;int temp[MAXSIZE];i = j = k = 0;while (i < list1_size && j < list2_size){if (list1[i] < list2[j]){temp[k] = list1[i];k++;i++;}else{temp[k++] = list2[j++];}}while (i < list1_size){temp[k++] = list1[i++];}while (j < list2_size){temp[k++] = list2[j++];}for (m = 0; m < (list1_size + list2_size); m++){list1[m] = temp[m];} }//歸并排序 void MergeSort(int k[], int n) {if (n > 1){/**list1是左半部分，list2是右半部分*/int *list1 = k;int list1_size = n / 2;int *list2 = k + list1_size;int list2_size = n - list1_size;MergeSort(list1, list1_size);MergeSort(list2, list2_size);// 把兩個(gè)合在一起merging(list1, list1_size, list2, list2_size);} }//基數(shù)排序 int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù) {int maxData = data[0]; ///< 最大數(shù)/// 先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個(gè)數(shù)判斷其位數(shù)，稍微優(yōu)化點(diǎn)。for (int i = 1; i < n; ++i){if (maxData < data[i])maxData = data[i];}int d = 1;int p = 10;while (maxData >= p){//p *= 10; // Maybe overflowmaxData /= 10;++d;}return d;/* int d = 1; //保存最大的位數(shù)int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d;*/ } void RadixSort(int data[], int n) {int d = maxbit(data, n);int *tmp = new int[n];int *count = new int[10]; //計(jì)數(shù)器int i, j, k;int radix = 1;for (i = 1; i <= d; i++) //進(jìn)行d次排序{for (j = 0; j < 10; j++)count[j] = 0; //每次分配前清空計(jì)數(shù)器for (j = 0; j < n; j++){k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)count[k]++;}for (j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶for (j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}for (j = 0; j < n; j++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中data[j] = tmp[j];radix = radix * 10;}delete[]tmp;delete[]count; }//堆排序 void max_heapify(int arr[], int start, int end) {//建立父節(jié)點(diǎn)下標(biāo)和子節(jié)點(diǎn)下標(biāo)int dad = start;int son = dad * 2 + 1;while (son <= end) { // 若子節(jié)點(diǎn)下標(biāo)在范圍內(nèi)才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) { // 先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的son++;}if (arr[dad] > arr[son]) {// 如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)return;}else { // 否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較SwapValue(arr[dad], arr[son]);dad = son;son = dad * 2 + 1;}} }void HeapSort(int arr[], int len) {int i;// 初始化，i從最后一個(gè)父節(jié)點(diǎn)開始調(diào)整for (i = len / 2 - 1; i >= 0; i--) {max_heapify(arr, i, len - 1);}// 先將第一個(gè)元素和已排好元素前一位做交換，然后再重新調(diào)整，直到排序完畢f(xié)or (i = len - 1; i > 0; i--) {SwapValue(arr[0], arr[i]);max_heapify(arr, 0, i - 1);} }int main() {cout << "Sort Collection\n";/****************************************************/cout << "\n------------------------------------------------\n";int arr1[] = {2, 4, 6, 5, 8, 1,3,7};int len1 = (int) sizeof(arr1) / sizeof(arr1[0]);PrintArr("arr original:", arr1, len1);BubbleSort(arr1, len1);PrintArr("arr Bubble-Sort :", arr1, len1);/****************************************************/cout << "\n------------------------------------------------\n";int arr2[] = { 2, 4, 6, 5, 8, 1,3,7 };int len2 = (int) sizeof(arr2) / sizeof(arr2[0]);PrintArr("arr original:", arr2, len2);InsertionSort(arr2, len2);PrintArr("arr Insertion-Sort :", arr2, len2);/****************************************************/cout << "\n------------------------------------------------\n";int arr3[] = { 2, 4, 6, 5, 8, 1,3,7 };int len3 = (int) sizeof(arr3) / sizeof(arr3[0]);PrintArr("arr original:", arr3, len3);ShellSort(arr3, len3);PrintArr("arr Shell's-Sort :", arr3, len3);/****************************************************/cout << "\n------------------------------------------------\n";int arr4[] = { 2, 4, 6, 5, 8, 1,3,7 };int len4 = (int) sizeof(arr4) / sizeof(arr4[0]);PrintArr("arr original:", arr4, len4);QuickSort(arr4, 0, len4-1);PrintArr("arr Quick-Sort:", arr4, len4);/****************************************************/cout << "\n------------------------------------------------\n";int arr5[] = { 2, 4, 6, 5, 8, 1,3,7 };int len5 = (int) sizeof(arr5) / sizeof(arr5[0]);PrintArr("arr original:", arr5, len5);SelectionSort(arr5, len5);PrintArr("arr Selection-Sort :", arr5, len5);/****************************************************/cout << "\n------------------------------------------------\n";int arr6[] = { 2, 4, 6, 5, 8, 1,3,7 };int len6 = (int) sizeof(arr6) / sizeof(arr6[0]);PrintArr("arr original:", arr6, len6);CountSort(arr6, len6);PrintArr("arr Count-Sort :", arr6, len6);/****************************************************/cout << "\n------------------------------------------------\n";int arr7[] = { 2, 4, 6, 5, 8, 1,3,7 };int len7 = (int) sizeof(arr7) / sizeof(arr7[0]);PrintArr("arr original:", arr7, len7);BucketSort(arr7, len7, 10);PrintArr("arr Bucket-Sort :", arr7, len7);/****************************************************/cout << "\n------------------------------------------------\n";int arr8[] = { 2, 4, 6, 5, 8, 1,3,7 };int len8 = (int) sizeof(arr8) / sizeof(arr8[0]);PrintArr("arr original:", arr8, len8);MergeSort(arr8, len8);PrintArr("arr Merge-Sort :", arr8, len8);/****************************************************/cout << "\n------------------------------------------------\n";int arr9[] = { 2, 4, 6, 5, 8, 1,3,7 };int len9 = (int) sizeof(arr9) / sizeof(arr9[0]);PrintArr("arr original:", arr9, len9);RadixSort(arr9, len9);PrintArr("arr Radix-Sort :", arr9, len9);/****************************************************/cout << "\n------------------------------------------------\n";int arr10[] = { 2, 4, 6, 5, 8, 1,3,7 };int len10 = (int) sizeof(arr10) / sizeof(arr10[0]);PrintArr("arr original:", arr10, len10);RadixSort(arr10, len10);PrintArr("arr Heap-Sort :", arr10, len10);system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的【✈️️️排序算法,一文讲尽！Top 10 Sort Algorithms✈️️️】C/C++ 实现经典十大排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。