#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int nums[N], help[N];
int n;
void quickSort(int l, int r){
if(l >= r) return;
int x = nums[l+r>>1], i = l-1, j = r+1;
while(i < j){
do i++; while(x > nums[i]);
do j--; while(x < nums[j]);
if(i < j)
swap(nums[i], nums[j]);
}
quickSort(l, j), quickSort(j+1, r);
}
void selectSort() {
for(int i = 0; i < n-1; ++i) {
int cur_min = i;
for(int j = i+1; j < n; ++j) {
if(nums[j] < nums[cur_min]) {
cur_min = j;
}
}
swap(nums[i], nums[cur_min]);
}
}
void insertSort() {
for(int i = 1; i < n; ++i) {
auto value = nums[i];
int j = i-1;
while(j >= 0 && nums[j] > value) {
nums[j+1] = nums[j];
--j;
}
nums[j+1] = value;
}
}
void bubbleSort() {
for(int i = 0; i < n-1; ++i) {
bool flag = false;
for(int j = 0; j < n-i-1; ++j) {
if(nums[j] > nums[j+1]) {
swap(nums[j], nums[j+1]);
flag = true;
}
}
if(!flag) break;
}
}
void mergeSort(int l, int r) {
if(l >= r) return ;
int mid = l+r>>1;
int i = l, j = mid+1, cnts = 0;
mergeSort(l, mid), mergeSort(mid+1, r);
while(i <= mid && j <= r) {
help[cnts++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while(i <= mid) help[cnts++] = nums[i++];
while(j <= r) help[cnts++] = nums[j++];
for(int i = 0; i < cnts; ++i) {
nums[l++] = help[i];
}
}
void countSort() {
auto max_value = *max_element(nums, nums+n);
auto min_value = *min_element(nums, nums+n);
vector<int> count(max_value - min_value + 1);
for(int i = 0; i < n; ++i) {
++count[nums[i]-min_value];
}
for(int i = 1; i < count.size(); ++i) {
count[i] = count[i-1] + count[i];
}
int res[n];
for(int i = n-1; i >= 0; --i) {
auto cnts = count[nums[i]-min_value];
res[cnts-1] = nums[i];
--count[nums[i]-min_value];
}
memcpy(nums, res, sizeof res);
}
void radixSort() {
auto max_value = *max_element(nums, nums+n);
int bit = 0, tmp = max_value;
while(tmp) {
tmp /= 10;
++bit;
}
int radix = 1;
vector<int> count(10);
int res[n];
for(int i = 1; i <= bit; ++i) {
memset(res, 0, sizeof res);
for(int j = 0; j < n; ++j) {
++count[nums[j]/radix%10];
}
for(int j = 1; j < 10; ++j) {
count[j] = count[j-1] + count[j];
}
int indx = 0;
for(int j = n-1; j >= 0; --j) {
int cnts = count[nums[j]/radix%10];
res[cnts-1] = nums[j];
--count[nums[j]/radix%10];
}
memcpy(nums, res, sizeof res);
radix *= 10;
}
}
void bucketSort() {
int k = 10;
auto max_value = *max_element(nums, nums+n);
auto min_value = *min_element(nums, nums+n);
int bucket_num = (max_value - min_value) / k + 1;
vector<int> bucket[bucket_num];
for(int i = 0; i < n; ++i) bucket[(nums[i]-min_value)/k].emplace_back(nums[i]);
for(int i = 0; i < bucket_num; ++i) sort(bucket[i].begin(), bucket[i].end());
int indx = 0;
for(int i = 0, j = 0; i < bucket_num; ) {
if(j < bucket[i].size()) nums[indx++] = bucket[i][j++];
else i++, j = 0;
}
}
void down(int u, int sz) {
int tmp = u;
while(2*u <= sz && nums[2*u] < nums[tmp]) tmp = 2*u;
while(2*u+1 <= sz && nums[2*u+1] < nums[tmp]) tmp = 2*u+1;
if(tmp != u) {
swap(nums[tmp], nums[u]);
down(tmp, sz);
}
}
void up(int u) {
while(u/2 && nums[u/2] > nums[u]) {
swap(nums[u/2], nums[u]);
u /= 2;
}
}
void heapSort() {
for(int i = n/2; i; --i) down(i, n);
for(int i = n; i > 1; --i) {
swap(nums[1], nums[i]);
down(1, i-1);
}
}
void shellSort() {
for(int gap = n/2; gap; gap /= 2) {
for(int i = gap; i < n; ++i) {
int tmp = nums[i], j = i;
for( ; j >= gap && tmp < nums[j-gap]; j -= gap) {
nums[j] = nums[j-gap];
}
nums[j] = tmp;
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; ++i) cin >> nums[i];
bucketSort();
for(int i = 0; i < n; ++i) cout << nums[i] << " ";
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)