《啊哈！算法》学习笔记——简单桶排序，冒泡排序，快速排序
简单的桶排序
借助于一个一维数组，利用数组的下标存储需要排序的数字。刚开始的时候，将数组的值进行初始化为0，表示数组下标所代表的数字没有出现过，之后开始处理数字，出现过的数字，则修改数组下标相应数字的值。假如出现数字3，则修改a[3]的值，对应a[3]++。最后循环嵌套按照相应要求输出排序后数字即可。
例：对n个0-1000之间的整数进行从小到大排序。
代码：
#include <stdio.h>
int main(){
int n,i,j,num;
int count[1001]={0}; //将数组的值初始化为0
scanf("%d",&n);
for(i=0;i<n;i++){ //循环输入n个数
scanf("%d",&num);
count[num]++; //将输入数字进行计数
}
//遍历0-1000之间的数字
for(i=0;i<1001;i++){ //从大到小则为for(i=1000;i>=0;i--)
for(j=1;j<=count[i];j++){
printf("%d ",i);
}
}
return 0;
}
输入样例：
10
8 100 50 22 15 6 1 1000 999 0
输出样例：
0 1 6 8 15 22 50 100 999 1000
时间复杂度O(M+N)，如果需要排序的数字范围特别大，则非常的浪费空间。如果出现小数，则不能使用了。
冒泡排序
冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
每一趟排序只能将一个数字归位，如果有n个数进行排序，则要进行n-1趟操作。
代码：
#include <stdio.h>
int main(){
int n,i,j,temp;
int a[100];
scanf("%d",&n);
for(i=0;i<n;i++){ //循环输入n个数
scanf("%d",&a[i]);
}
//冒泡排序核心部分
for(i=0;i<n-1;i++){ //进行n-1趟排序
for(j=0;j<n-i-1;j++){ // -1防止判断索引越界，-i不与每趟排序完成数字比较
if(a[j] > a[j+1]){ //从小到大排序
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
输入样例：
10
8 100 50 22 15 6 1 1000 999 0
输出样例：
0 1 6 8 15 22 50 100 999 1000
时间复杂度O(N2)
快速排序
假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数6作为基准数。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边。
初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量 i 和 j ，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8
此时探测结束，将基准数6与3进行交换
代码：
#include <stdio.h>
int a[1000];
//快速排序核心
void quickSort(int left,int right){
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存储基准数
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[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i];
a[i]=temp;
quickSort(left,i-1);//继续处理左边
quickSort(i+1,right);//继续处理右边
return;
}
int main(){
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quickSort(0,n-1);//调用快速排序
for(i=0;i<n;i++) //输出排序结果
printf("%d ",a[i]);
return 0;
}
输入样例：
10
6 1 2 7 9 3 4 5 10 8
输出样例：
1 2 3 4 5 6 7 8 9 10
平均时间复杂度O(NlogN)，快速排序是基于“二分”思想的一种排序。