数据结构——简易版桶排序，冒泡排序，快速排序（C实现)
问题：用户输入10个数字（范围0~10），从小到大排序。
一.简单的桶排序 —— O(M+N)
M:桶的个数 N：待排序的个数
步骤：
数组建桶book[i]，初始化book[i]均为0，数组角标即为该数字。（book[1]存1出现的次数，初始为0）
用户输入，for循环，从0到10，进行计数。（输入t，book[t]++）
遍历所有桶，出现几次就打印几次。
#include<stdio.h>int main(){// 创建11个桶，每个桶初始存0int book[11], i, j,t;for( i = 0; i<11; i++)book[i] = 0 ;// 让用户输入5个数字,每次读入的存进去 计数++for( i = 0; i < 5 ; i++){scanf("%d",&t);book[t]++ ;}// 全部存到了桶中，打印出来每个桶for ( i = 0 ; i<=11;i++)for(j = 0; j<book[i];j++)printf("%d ",i);return 0;}
上述弊端：
非常浪费空间。且若排小数无法实现。除此之外，我们假设存的是分数，但排名的是人名，也无法实现。
二.冒泡排序 —— O(N²）
基本思想：每次比较相邻元素，若顺序错误，相邻元素交换。
步骤：
若排n个数，n-1次循环，进行归位（自己不跟自己比）
每一趟：从第一位开始进行相邻两数比较，每一趟就找到了最大的那位往后面放，因此一趟就排好了一个。已经归位的就不用再进行比较。
核心：双重嵌套循环。
下面实例用冒泡排序解决分数比较，最后排列的是人名。
int main(){//先申请一个长度为100的作为备用struct student a[100],k;int i,j,n;// 让用户输入究竟有几个数字printf("请输入您需要排序的用户的个数：");scanf("%d",&n);for(i=1;i<=n;i++){scanf("%s %d",&a[i].name,&a[i].score);printf("%d %d\n",a[i].name,a[i].score);printf("%d %d\n",&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){k = a[j];a[j] = a[j+1];a[j+1] = k;}}}for(i=1;i<=n;i++)printf("%s\n",a[i].name);return 0;}
弊端：虽然解决了桶排序的弊端，但是时间复杂度高。
三.快速排序 ——O（NlogN)
基本思想：首位数为基准，左右两个各一个哨兵，右边为j,j先出发左移，找到比基准小的停下，左边为i，i找到比基准大的停下。
交换继续移动，重复过程，直到i和j碰头，基准数置于了中间。
两边无序数据继续采用上述步骤。
如下图：
#include<stdio.h>int a[101],n;void quickSort(int left,int right){// 左右端，开始定位int i,j,temp;if(left>right) return;// 定基准，左i 右jint jz = a[left];i = left;j = right;//开始交换 ijwhile(i!=j){//先跑j，后跑i，用j找到小于基准的， 没有用等于号，总有一下i=j 这样我就跳出了while(a[j]>=jz && j>i) j--;while(a[i]<=jz && i<j) i++;//当i比j小的时候，且i和j没有相遇的时候 ，交换。if(i<j){temp = a[i];a[i]=a[j];a[j]=temp;}}// 换完之后把基准给ia[left] = a[i];a[i] = jz;quickSort(left,i-1);quickSort(i+1,right);return;}int main(){int i,j;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);quickSort(1,n);for(i=1;i<=n;i++)printf("%d",a[i]);return 0;}