首页 > 代码库 > 啊哈算法（一）
啊哈算法（一）
1.最快最简单的排序，桶排序
问题：假设有5个同学，在一场考试中分别取得分数为（满分10）：3 5 8 2 5，如何将他们按从大到小的顺序排列？
解决思路：定义一个长度为11的数组，即a[0]-a[10],下标序号分别对应分数1-10；每一个人得到一个分数n，就使a[n]++，如有两个人得5分，a[5]=2；
然后依次打印数组小标序号，对应的值为n则打印n次。
图形解释：
+1
+1 +1 +1 +1
a[1] a[2] a[3] a[4] a[5] a[6] a7[] a[8] a[9] a[10]
代码如下：
#include <stdio.h>int main() { int a[10] i j t; for(i=0; i<=10; i++){ a[i]=0; //初始化数组的每一项都为0 } for(i=1; i<=5; i++){ scanf("%d",&t); //循环输入5个字 a[t]++; //对应下标的数组值+1 } for(i=0; i<=10; i++){ //遍历数组，从小到大排序 for(j=1; j<=a[i]; j++){ //确定每一项的值，出现几次就打印几次 printf("%d",i) } } getchar(); getchar(); return 0}
总结：桶排序的优点是非常快速的排序；
缺点是浪费空间，如果需要排序的数范围非常啊大：1~999999999，那么就需要申请1000000000个变量(桶)a[999999999]。
运用场景：需要知道各变量出现的次数。
2.冒泡排序
基本思想：每次比较两个相邻的元素，如果他们的顺序错误，就把他们的位置交换。
问题：将12 35 99 18 76 五个数进行从大到小的排序。
解题思路：因为是从大到小排序，所以小的数应该排在后面。每次只比较两个数，判断较小的数是否在右边，否则交换位置；
比较4次后，数组中最小的数将出现在最右边，我们称之为“归位”，这样的一系列比较结束我们称之为“一趟”；(归位 和 趟 是非常重要的概念 ！)
结束一趟后开始第二趟，比较3次，倒数第二小的数将出现在倒数第二的位置......
如此类推。
图形解释：两个数中的较小数会一直往上走，就像冒泡一样。
代码如下：
1 #include <stdio.h> 2 int main(){ 3 int a[100],i,j,t,n; 4 sca9nf("%d",&n) //输入一个数n，表示总共有n个数需要比较 5 for(i=0; i<=n; i++){ 6 scanf("%d",&a[i]) //将数字循环放入数组a中 7 } 8 9 for(i=1; i<=n-1; i++){ //总共需要走n-1趟10 for(j=2; j<=n-i;j++){ //每一趟比较n-i次11 if(a[j] < a[j+1]){ //判断，若小的数在左边，则交换位置12 t = a[j]; 13 a[j] = a[j+1]14 a[j+1] = t15 }16 }17 }18 19 for(i=1; i<=n; i++){ //循环输出数组结果20 printf("%d",a[i]);21 }22 23 getchar();24 getchar();25 return 0;26 }
总结：冒泡排序每次只比较两个数，从数列的前两个开始
若比较n个数，则需要进行n-1趟，共有n-1个数归位，直到最后一个未归位的数，排列才结束
第i趟时，只需要比较n-i次，因为已经有i-1个数归位，不需要与归位的数进行比较
冒泡排序的核心部分是双重嵌套，外层是n-1趟，内层是这一趟要进行n-i次比较
缺点，冒泡排序时间复杂度非常高。
运用场景：对无序数列进行排序
3.快速排序
基本思想：确定基准数K，一般为数列中的第1个数。在数列两边分别向中间进行“探索”，依据判断条件（如按顺序排列），先从右端开始，当右边某一个值大于k时,左边开始
当左边某一值小于k时，左右两个值交换，继续探索，直到两边遍历到同一个值，将这个值与基准值k交换。
问题：对无序数列6 1 2 7 9 3 4 5 10 8进行排序。
解题思路： 确定基准数k（书中设为6），定义i j两个变量，分别从数列两端（a[0]和a[9]）向中间靠拢,当j<k,i>k时，将a[i]和a[j]交换。
若是降序，判断条件改为，当j>k,i<k时，将a[i]和a[j]交换。
图形解释：
k i j
6 1 2 7 9 3 4 5 10 8
k i j
6 1 2 7 9 3 4 5 10 8
k i j 此时j<k,i开始遍历
6 1 2 7 9 3 4 5 10 8
k i j
6 1 2 7 9 3 4 5 10 8
k i j
6 1 2 7 9 3 4 5 10 8 变量i找到了比基准值大的数，满足j<k,i>k，将两个数交换
k i j
6 1 2 5 9 3 4 7 10 8
k i j
6 1 2 5 4 3 9 7 10 8
k i/j
6 1 2 5 4 3 9 7 10 8 最后，i 和 j 相遇，则将它和基准值交换 k <==> i/j
3 1 2 5 4 6 9 7 10 8 这数最后的结果
然后我们将6的左边和右边继续使用同样的方法进行排序即可。
啊哈算法（一）