歸并排序

排序思想

歸并排序就是將兩個或兩個以上的有序表組合成一個新的有序表

從代碼結(jié)構(gòu)來看，歸并排序類似樹的后序遍歷 —— （參考快速排序，類似樹的先序遍歷）

歸并排序算法分析

歸并排序的時間復雜度是 O(nlogn)，由于我采用的方式是下標元素的交換，所以沒有用到輔助空間，因此空間復雜度是 O(1)，同時也是 穩(wěn)定排序， 由于它是一種分治思想，所以它的元素 不是全局有序 的。

代碼實現(xiàn)

class Solution{ public:int counter = 0;int ans[7] = {23,76,34, 89, 90,34,56};void mergeSort(int low, int high) {if(low>=high) return;int mid = (low + high) / 2;mergeSort(low,mid);mergeSort(mid+1,high);mergeTwoList(low,mid,high);return;} private:void mergeTwoList(int low, int mid, int high) {int i = low;int j = mid+1;int tmp[10] = {0};int flag = low;while(i<=mid&&j<=high) {if(ans[i]<ans[j]) {tmp[flag++] = ans[i++];} else {tmp[flag++] = ans[j++];}}while(i<=mid) tmp[flag++] = ans[i++];while(j<=high) tmp[flag++] = ans[j++];for(int k = low; k <= high; k++) {ans[k]=tmp[k];}return;} };

加工后執(zhí)行的結(jié)果

基數(shù)排序

排序思想

基數(shù)排序不基于比較進行排序，而是采用多關(guān)鍵字的排序思想。也就是說基數(shù)排序?qū)嶋H上是關(guān)于關(guān)鍵字各位的的大小排序的。

通過示例解釋一下

以下 nums[0,6] 的個位數(shù)依次為 {6, 6, 4, 9, 0, 4, 6} ，按這個依據(jù)從小到大排序，{90, 34, 34, 6, 76, 56, 189}

以上 nums[0,6] 的十位數(shù)依次為 {9, 3, 3, 0, 7, 5, 8}，按這個依據(jù)從小到大排序，{6, 34, 34, 56, 76, 189, 90}

以上 nums[0,6] 的百位數(shù)依次為 {0, 0, 0, 0, 0, 1, 0}，按這個依據(jù)從小到大排序，{6, 34, 34, 56, 76, 90, 189}

基數(shù)排序算法分析

基數(shù)排序的時間復雜度是 O(dn)，也就是需要精心 d 趟分配，一趟分配和收集需要 O(n)，空間復雜度是 O(10n)，同時也是 穩(wěn)定排序， 但 不是全局有序 的。

代碼實現(xiàn)

class Solution{ public:void radixSort(vector<int> nums) {vector<vector<int> > tmp;vector<int> list;int anchor = 1;int counter = 0;// lgchor + 1趟排序while(anchor) {tmp.clear();// 需要輔助數(shù)列for(int j = 0; j < 10; j++) {list.clear();list.push_back(j);tmp.push_back(list);}int i = 0; // 按關(guān)鍵字各個位數(shù)排序while(i<7) {int rest = nums[i] % (anchor * 10);int radix = rest / anchor;tmp[radix].push_back(nums[i++]);}// 放在一個列表中nums.clear();for(int j = 0; j < 10; j++) {for(int k = 1; k < tmp[j].size(); k++) {nums.push_back(tmp[j][k]);}if(tmp[j].size()==7) anchor=0;} anchor *= 10;}return;} };

加工后執(zhí)行的結(jié)果

歸并排序測試代碼

#include <stdio.h> #include <vector> using namespace std;class Solution{ public:int counter = 0;int ans[7] = {23,76,34, 89, 90,34,56};void mergeSort(int low, int high) {if(low>=high) return;int mid = (low + high) / 2;mergeSort(low,mid);mergeSort(mid+1,high);mergeTwoList(low,mid,high);printf("第%d輪：", counter++);for(int j = 0; j < 7; j++) {printf(" %d ",ans[j]);if(j!=6) printf(",");}printf("\n");return;} private:void mergeTwoList(int low, int mid, int high) {int i = low;int j = mid+1;int tmp[10] = {0};int flag = low;while(i<=mid&&j<=high) {if(ans[i]<ans[j]) {tmp[flag++] = ans[i++];} else {tmp[flag++] = ans[j++];}}while(i<=mid) tmp[flag++] = ans[i++];while(j<=high) tmp[flag++] = ans[j++];for(int k = low; k <= high; k++) {ans[k]=tmp[k];}return;} };int main() {Solution solution;solution.mergeSort(0,6);return 0; }

基數(shù)排序測試代碼

#include <stdio.h> #include <vector> using namespace std;class Solution{ public:void radixSort(vector<int> nums) {vector<vector<int> > tmp;vector<int> list;int anchor = 1;int counter = 0;while(anchor) {tmp.clear();for(int j = 0; j < 10; j++) {list.clear();list.push_back(j);tmp.push_back(list);}int i = 0; // 第一輪排序while(i<7) {int rest = nums[i] % (anchor * 10);int radix = rest / anchor;tmp[radix].push_back(nums[i++]);}// 放在一個列表中nums.clear();for(int j = 0; j < 10; j++) {for(int k = 1; k < tmp[j].size(); k++) {nums.push_back(tmp[j][k]);}if(tmp[j].size()==7) anchor=0;} anchor *= 10;printf("第%d輪：", counter++);for(int j = 0; j < nums.size(); j++) {printf("%d",nums[j]);if(j!=nums.size()-1) printf(",");}printf("\n");}return;} };int main() {vector<int> v;v.push_back(6);v.push_back(76);v.push_back(34);v.push_back(189);v.push_back(90);v.push_back(34);v.push_back(56);Solution solution;solution.radixSort(v);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【数据结构-排序】4.图解归并排序和基数排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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