第二篇就来写一些奇妙的排序运算吧。

一、桶排序

当我们对一串数字排序的时候，应该用什么样的方法呢？有很多种啊，冒泡排序，桶排序，快速排序，sort...那第一种就来介绍一下桶排序吧。

桶排序是什么呢？

我们现在有六个数字 6 5 7 9 1 4。我们要对他进行排序？可以怎么办呢？

首先我们发现，我们的数字都是十以内的数字，就像一个人拿着六张卡牌。然后我们面前一共有十个空桶。上面按顺序标上了1-10，接下来，我们把每一张卡牌分别放进他所对应的那个空桶里面，然后，再从1开始往后走，如果桶里有卡牌，我们就把他拿出来，放在上一张牌的上面，最后我们手里的卡牌就是排好顺序的。这就是简化版桶排序的简单思想，是不是感觉很简单呢？就是物品放到容器里，然后容器是标好了顺序的，我们按照容器的顺序把物品拿出来就自然而然是排好序的。

思考一下，我要贴代码了。

#include<stdio.h>
#include<string.h> //数组初始化要加的头文件int main()
{int a[1001];memset(a,0,sizeof(a));/*在写桶排序的时候如果是把数组定义在main里面，不要忘记初始化。
如果是定义在main函数外面则为全局变量数组，就不需要初始化了，已经自动默认为数组的值为0*/int n,m;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&m);a[m]++;}for(int i=0;i<=1000;i++){for(int j=1;j<=a[i];j++){printf("%d ",i);//把桶的编号按照顺序输出}}return 0;
} 

桶排序的时间复杂度是O(M+N)，这个M就是数组的个数，这个N就是1-数组里面的最大值。但是哈，桶排序只能完成排序，但是不能实现两个位置的所有信息都进行交换。 

二、冒泡排序

那么上面的那个桶排序有没有什么缺陷呢，不然我们的冒泡排序也没有登场的余地了不是。当然有，桶排序实在是太太太太太太费空间了。欸？你问为什么。

那就举个栗子吧，你看嗷。我们的数组如果是2 5 7 6 4 8这样的还好，那如果是1 5456456456456156756456 21 54 5 4 6这样的呢，那我们的桶编号是不是要开好大，我们的数组是不是也要变得好大，那么是不是超级费空间，那是不是一不留神就变成了段错误呢？那么接下来就是我们最最最最最最最经典的冒泡排序。

冒泡排序是怎么实现的呢？冒泡排序呢，在我看来就像是小鱼吐泡泡一样。要排序的数字一个一个地交换，向上面冒，向上面走。我们从第一个数字开始，往后走，如果是从小到大排序的话就要改变他的位置和比较的条件。比如1 5 6 4 7 8，要按照从小到大排序的话，1就会往后依次比较，当发现后面的这个数字比他小的时候就交换，很明显，1不需要交换，那么就往下走是5，5往后找，先找6，不需要交换，再往后走，找到了4，需要和4交换就进行交换，然后再往后，发现都不需要交换就回到刚刚的位置找到了6，重复上面5找位置的方法，以此类推，就可以把6排好。如果数字拍成一列的话，交换位置，像不像小鱼吐出来的泡泡往上面冒？冒泡排序呢，每次找到一个数字最终的位置，最后就能把所有的数字放到他该放到的顺序位置上。

接下来就是，代码实现。

#include<stdio.h>int a[100000]
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n-1;i++){for(int j=1;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=1;i<=n;i++){scanf("%d",a[i]);}return 0; 
}

这个是个单纯的数组进行排序，那如果是加上别的东西呢？字符串或者是别的需要跟着那个应该排序的数据一起进行交换呢？很简单，我们直接把要排序的东西存进结构体。

#include<stdio.h>
struct student{char name[100];int score;
}a[100];int main()
{int n;scanf("%d",&n);student temp; for(int i=1;i<=n;i++){scanf("%s %d",&a[i].name,&a[i].score);}for(int i=1;i<=n-1;i++){for(int j=1;j<=n-i;j++){if(a[j].score>a[j+1].score){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}for(int i=1;i<=n;i++){printf("%s ",a[i].name);}return 0;
}

这样的话就可以把进行标记的东西和我们进行排序的数据一起进行交换了。但是，冒泡排序的时间复杂度是O(n*n)，还是挺高的，但是可以解决掉桶排序所不能实现的带着常量一起交换以及浪费空间的小问题。不过，这么慢，还有没有更快一点的排序呢？肯定是，有的。

三、快速排序 

我不知道大家的老师都是怎么教的，他们会不会告诉你们：“不需要学快速排序，用一个sort就好了啊，一行代码就可以解决的问题。”小鱼要在这里告诉你：“No！”多多益善，sort确实很快但是有时候可能快速排序更好用一点呢？

前两个算法的时间复杂度我们都看到了，桶排序是O(M+N)，冒泡排序是O(N*N)，那么快速排序呢？他的时间复杂度是O(NlogN)；这个已经基本上可以看作是线性O(N)的时间复杂度了。

快速排序呢，其实也蛮好理解的。

首先，我们找一个数组6 5 4 9 1 5 3 4 7 8，这是我随便输出来的一个数组，一共有10个数字，然后我们要对他进行排序，不可以用桶排序，不可以用冒泡排序，不可以用sort哦。（前面说的好像是废话呢）emmmm，来讲一讲如何进行快速排序吧。

我们可以在这个数组里面选择一个数字，为了方便起见，我们就选择第一个数组6作为我们的特殊数字，然后在后面找到一个位置k，这个位置也是个特殊位置，k左边的所有数字都要小于我们的特殊数字，而6右边的数字都要大于6。那么这个位置应该如何去寻找呢，找两个变量i和j，一个从头走，一个从后面走，j从最后一个数字往前找，j要找什么呢？j要找的是不符合我们上面所说的特殊位置的那个数字，也就是要找小于特殊数字的那个数，可能会有一点绕，不过没关系，多思考一下这里，这里读懂了，就可以理解下面的了。然后我们类比j就可以得出i要找的是大于特殊数字的那个数，如果没找到的话（对i，j而言），i往后移动，j往前移动。如果找到的话就把i，j所找到的那两个数字进行交换。如果i和j此时走到了同一个数字的位置，那么这个位子就是我们的特殊位置k，我们就可以把特殊位置换给我们的特殊数字了。

变化的历程就是如下：

6 5 4 9 1 5 3 4 7 8

6 5 4 4 1 5 3 9 7 8

3 5 4 4 1 5 6 9 7 8.

这就是6的变化历程，然后在6的左边和右边重复6的这个改变，就当个小练习，这个就交给你来完成吧。（我看到某巨巨说这个思想是基于二分的思想，有兴趣的同学可以去理解理解哦）

接下来就是代码实现了。（咱还是建议手动模拟一下过程，可以更加清晰地去理解，而且也很有趣）

#include<stdio.h>
int a[1000],n;void quicksort(int left,int right)
{int i,j,t,temp;if(left>right){return ;}temp=a[left];i=left;j=right;while(i!=j){while(a[j]>=temp&&i<j){j--;}while(a[i]<=temp&&i<j){i++;}if(i<j){t=a[j];a[j]=a[i];a[i]=t;}}a[left]=a[i];a[i]=temp;quicksort(left,i-1);quicksort(i+1,right);
} 
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]); }quicksort(1,n);for(int i=1;i<=n;i++){printf("%d ",a[i]);}return 0;
}

这样看来，其实排序算法嘛，奇妙又有趣！啊，差点忘了还有个sort

四、sort

说句实话，sort排序其实挺常用的，为什么这么说呢，因为他简单。只有短短一行。就能实现上面那么一堆的代码实现的功能。 

#include<iostream>
#include<algorithm>
using namespace std;
int a[110000];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);//如果你的数组跟我一样从1开始，那就用这个，如果不是的话，就用
sort(a,a+n);for(int i=1;i<=n;i++){printf("%d ",a[i]);}return 0;
}

既然都讲到这里了，那就再加个sort的结构体排序吧。

#include<iostream>
#include<algorithm>
using namespace std;
struct student{int x,y;
}a[110000];
bool cmp(student a,student b){return a.x>b.x;
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&a[i].x,&a[i].y);}sort(a+1,a+n+1,cmp);//其实只要看上面的bool就可以了for(int i=1;i<=n;i++){printf("%d %d\n",a[i].x,a[i].y);}return 0;
}

大概就这么多了，我没想到我写个总结居然从昨天写到了今天，那么还是那句话，欢迎佬佬们指导和提出建议！下一篇再见啦