受桶排序思想的啟發(fā)，想到了這個算法。不同之處在于，桶排序是對于每個bucket各自排序，而本算法桶內(nèi)部不需要排序。

功能

本算法可以在有限空間內(nèi)，將任意有理數(shù)排序，平均時間復(fù)雜度為O(n)

輸入：需要排序的數(shù)（正有理數(shù) / 負(fù)有理數(shù) / 0）
輸出：本算法排序結(jié)果 + 用于比對的標(biāo)準(zhǔn)答案

思路

利用桶排序的思想，不同之處在于(在不浪費的基礎(chǔ)上)建立足夠多的桶（同時保證桶的數(shù)量為有限個），每個桶只存存放相同數(shù)值的元素

1、找到精度最高的數(shù)，（精度最高的數(shù)，也就是小數(shù)點后面位數(shù)最多，記其小數(shù)點后位數(shù)為len）
2、找到待排序元素的最大值max，最小值min
3、建立桶，建立哈希函數(shù)，將數(shù)據(jù)放入桶中
4、遍歷桶，逆推函數(shù)，輸出

例如，要排序的數(shù)字為：-4 2.1 2 1 5，則桶的個數(shù)為(max-min)*10^len+1=91個，這樣能保證所有值不同的元素都有且只有一個桶可放。值相同的元素放在相同的桶中。映射關(guān)系如下:

運行結(jié)果示例

請輸入你要排序的數(shù)字個數(shù)：20 5 -6.2 -6.3 2.22 2.23 1 8.2 10 10 8.3 8.4 10 2.2 3.5 2.2 7 0 5.1 7 4.2 小數(shù)點后最多 2 位 最小：-6.3 最大：10 桶的個數(shù)：1631排序后: 元素 重復(fù)次數(shù) -6.3 1 -6.2 1 0 1 1 1 2.2 2 2.22 1 2.23 1 3.5 1 4.2 1 5 1 5.1 1 7 2 8.2 1 8.3 1 8.4 1 10 3正確答案 -6.3 -6.2 0 1 2.2 2.2 2.22 2.23 3.5 4.2 5 5.1 7 7 8.2 8.3 8.4 10 10 10

代碼

第45、46行使用了字符串處理有關(guān)的函數(shù)，如果說整個算法不是嚴(yán)格意義上的O(n)的話，大概是因為這兩行吧…

#include<iostream> #include<string> #include<vector> #include<time.h> #include<algorithm> #include<math.h> #define SWAP(a,b) {Node t;t=a;a=b;b=t;}using namespace std;class Node//被排序的元素 { public:double val;int afterPoint; };int mysort(Node a1, Node a2)//此函數(shù)未在算法中調(diào)用 僅用于檢測結(jié)果正確性 {return a1.val < a2.val; }int main() {//總元素個數(shù)srand((int)time(NULL));int total;cout << "請輸入你要排序的數(shù)字個數(shù)：";cin >> total;/*--------------------------------------以下為O(n)排序算法--------------------------------------*///讀取每一個元素 并記錄最大的小數(shù)點后數(shù)字位數(shù) 如:2.555的afterPoint=3 1.2的afterPoint=1string str;vector <Node> arr;Node oneNode;int afterPointMax = 0;int i;cout << "請輸入你要排序的數(shù)字：\n";for (i = 0; i < total; i++){cin >> str;oneNode.val = atof(str.c_str());//string to doubleint pointPlace = str.find_first_of(".");//小數(shù)點位置oneNode.afterPoint = (pointPlace == -1 ? 0 : str.length() - pointPlace - 1);//計算小數(shù)點后面的位數(shù) afterPointMax = (afterPointMax > oneNode.afterPoint ? afterPointMax : oneNode.afterPoint);//記錄最大的小數(shù)位數(shù)arr.push_back(oneNode);}cout << "小數(shù)點后最多 " << afterPointMax << " 位" << endl;//同時找最大最小//偶數(shù)個 分兩半 一半含有最大 一半含有最小 O(n/2)double max, min;for (i = 0; i < total / 2; i++){if (arr[i].val > arr[total / 2 + i].val){SWAP(arr[i], arr[total / 2 + i]);//小的放左邊}}//找最小 O(n/2)min = arr[0].val;for (i = 0; i < total / 2; i++){if (arr[i].val < min){min = arr[i].val;}}//找最大 O(n/2)max = arr[total / 2].val;for (i = total / 2; i < total; i++){if (arr[i].val > max){max = arr[i].val;}}//如果最后元素輪空 再加一次比較if (total % 2 != 0){if (arr[total - 1].val < min)min = arr[total - 1].val;if (arr[total - 1].val > max)max = arr[total - 1].val;}//輸出cout << "最小：" << min << endl;cout << "最大：" << max << endl;//桶的個數(shù)double bucketNum;bucketNum = (max - min)*pow(10, afterPointMax) + 1;cout << "桶的個數(shù)：" << bucketNum << endl;//定義桶并初始化為0int* bucket = new int[(int)bucketNum];for (i = 0; i < bucketNum; i++){bucket[i] = 0;}//類似構(gòu)建一個哈希函數(shù)int t;for (i = 0; i < total; i++){t = pow(10, afterPointMax);bucket[(int)((arr[i].val - min) / (max - min)*(bucketNum - 1) + 0.5)]++;//0.5用于強制四舍五入}//函數(shù)逆推并輸出排序結(jié)果cout << "\n排序后:\n元素\t重復(fù)次數(shù)\n";for (i = 0; i < bucketNum; i++){if (bucket[i] != 0){cout << (i / (bucketNum - 1)*(max - min)) + min << "\t";cout << bucket[i] << endl;}}/*--------------------------------------以上為O(n)排序算法--------------------------------------*///正確性檢測：以下輸出正確答案作為對比cout << "\n正確答案\n";sort(arr.begin(), arr.end(), mysort);for (i = 0; i < total; i++){cout << arr[i].val << endl;}cout << endl;system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析 自创O(n)排序算法 适用于任何有理数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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