算法思考 – 简化版桶排序

通过一个一维数组完成排序

描述

有 N (0 ≤ N ≤ 999999)个 0 到 999999 之间的随机整数 X(0≤ X ≤999999)需要进行排序,请给分别出升序排序与降序排序的结果。

 

输入

输入第一行有一个正整数 N,代表需要排序的随机整数个数。

第二行包含所有需要排序的随机整数,以空格隔开。

 

输出

输出有2行,分别为升序输出与降序输出的结果。

 

输入样例

5
5 9 2 41 7

 

输出样例

2 5 7 9 41
41 9 7 5 2

 

C++ Code

#include<iostream>
using namespace std;

int main() {
	int size = 999999;
	int *arr = new int[size], temp = 0, n = 0;//temp存储每次输入的元素,n存储需要排序的数字个数
	memset(arr, 0, size);//数组的所有元素初始化为0

	cin >> n;//输入需要排序的数字个数
	for (int i = 0; i < n; i++)//在输入的过程中完成排序
	{
		cin >> temp;
		arr[temp]++;
	}

	for (int i = 0; i < size; i++)//升序输出
	{
		for (int j = 0; j < arr[i]; j++) {
			cout << i << " ";
		}
	}
	cout <<  endl;

	for (int i = size; i > 0; i--)//降序输出
	{
		for (int j = 0; j < arr[i]; j++) {
			cout << i << " ";
		}
	}

	getchar(); getchar();//暂停程序
	return 0;
}

核心思想是通过数组的下标来直接表示元素,数组内存储的数字代表该数组下标的数字出现的次数。也就是说,在输入完成的时刻,就已经完成了对数据的排序。

 

缺点也非常明显,随着需要排序的随机整数中的最大值变大,消耗的内存空间也会随着变大。

 

这并不是真正的桶排序,只是一个简化版。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇