第一节 最快最简单的排序——桶排序
期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有 5 个同学，这 5 个同学分别考了 5 分、3 分、5 分、2 分和 8 分，哎考得真是惨不忍睹（满分是 10 分）。接下来将分数进行从大到小排序，排序后是 8 5 5 3 2。
#include<iostream>
using namespace std;
int main(void){
int a[11];//用来存储0—10分数的人数
for(int i=0;i<11;i++) a[i]=0;//初始化人数为0个
for(int i=1;i<=5;i++){//5个人
int t;
cin>>t;
a[t]++;
}
for(int i=0;i<11;i++){
for(int j=1;j<=a[i];j++){
cout<<i<<" ";
}
}
return 0;
}
以上代码并不是真正得桶排序，这是思想！！a数组就相当于很多个桶，每次循环就向桶中放入数据。桶排序的时间复杂度是O(M+N),其中M是桶的个数，N待排序个数。
现在分别有 5 个人的名字和分数：huhu 5 分、haha 3 分、xixi 5 分、hengheng 2 分和 gaoshou
8 分。请按照分数从高到低，输出他们的名字。即应该输出 gaoshou、huhu、xixi、haha、hengheng。
发现问题了没有？如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输
出的也仅仅是分数，但没有对人本身进行排序。也就是说，我们现在并不知道排序后的分数
原本对应着哪一个人！这该怎么办呢？不要着急，请看下节——冒泡排序。
第二节 邻居好说话——冒泡排序
简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！
如给你 5 个数进行排序（例如这 5 个数是 1、1912345678、2100000000、18000000 和912345678），你也仍然需要 2100000001 个“桶”。
如果现在需要排序的不再是整数而是一小数，比如将 5.56789、2.12、1.1、3.123、4.1234这五个数进行从小到大排序又该怎么办呢？
冒泡排序。它可以很好地解决这两个问题。
冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
“冒泡排序”的原理是：每一趟只能确定将一个数归位。
一下是代码：
//从小到大排序
#include<iostream>
using namespace std;
const int maxn = 100;
int a[maxn];
int main(void){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
////一下是冒泡排序的核心代码
for(int i=1;i<=n-1;i++){//n-1趟
for(int j=0;j<n-i;j++){//这里很关键，自己模拟一下
if(a[j]>a[j+1]){
int temp =a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
将上面代码稍加修改，就可以解决第 1 节遗留的问题，如下。
#include<iostream>
using namespace std;
struct student
{
char name[21];
char score;
};//这里创建了一个结构体用来存储姓名和分数
int main()
{
struct student a[100],t;
int i,j,n;
cin>>n; //输入一个数n
for(i=1;i<=n;i++) //循环读入n个人名和分数
cin>>a[i].name>>a[i].score;
//按分数从高到低进行排序
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j].score<a[j+1].score)//对分数进行比较
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
for(i=1;i<=n;i++)//输出人名
cout<<a[i].name;
return 0;
}
冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N ^2)。这是
一个非常高的时间复杂度,###但是冒泡冒泡排序并不常用！！！###
第 3 节 最常用的排序——快速排序
选择一个基准k，两个哨兵i,j
若基准选择在左边则j先走，否则i先走。
原理：比k大的放在k的右边，比k小的放在k的左边。
二分的思想
#include<iostream>
using namespace std;
int arr[101],n;
void quicksort(int left,int right){//两个哨兵
int i,j,t,temp;
if(left>=right) return;
temp=arr[left];
i=left;
j=right;
while(i!=j){
while(arr[j]>=temp&&i<j){
j--;
}
while(arr[i]<=temp&&i<j){
i++;
}
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
arr[left]=arr[i];
arr[i]=temp;
quicksort(left,i-1);
quicksort(i+1,right);
}
int main(void){
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
quicksort(1,n);
for(int i=1;i<=n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
