# 基数排序

xiaoxiao2021-02-28  12

#include "stdafx.h" #include <iostream> #include <list> using namespace std; int maxdigit(int data[], int n);//判断最大的数有多少位 void radixsort(int data[], int n);

int main()

{ int data[10] = { 179,206,306,93,859,984,55,9,271,33 }; radixsort(data, 10); cout << "排序后" << endl; for (int i = 0; i < 10; i++) cout << data[i] << " "; cout << endl; cout << "hello" << endl; system("pause");     return 0; } int maxdigit(int data[], int n) { int d = 1; int p = 10; for (int i = 0; i < n; i++) { while (data[i] >= p)//比10大加一位 { p *= 10; ++d; } } return d; } void radixsort(int data[], int n) { int digits = maxdigit(data,n); list<int>lists[10];//定义链表 int d, j, k, factor; for (d = 1, factor=1; d <= digits; factor*=10,d++) { for (j = 0; j < n; j++) { lists[(data[j] / factor) % 10].push_back(data[j]); //%取模去除高位，提出数每一个数的个十百千位 } for (j = k = 0; j < 10; j++) { while (!lists[j].empty()) { data[k++] = lists[j].front(); lists[j].pop_front(); //从链表的头取一个删一个 } } //查看基数排序的中间结果 /* for (int m = 0; m < n; m++) cout << data[m] << " "; cout << endl;*/ } }