UDN-企业互联网技术人气社区

板块导航

浏览  : 874
回复  : 0

[其它] 算法开篇课

[复制链接]
哥屋恩的头像 楼主
发表于 2016-10-17 12:18:32 | 显示全部楼层 |阅读模式
  算法开篇介绍:Algorithm,是指解题方案的准确而完整的描述,代表着用系统的方法描述解决问题的策略机制。

  最快最简单的排序

  首先看题:

  班上有5位同学,分别考了5分,3分,5分,8分,2分,将分数从大到小排序是8,5,5,3,2。有什么好的办法可以编写一段程序,让计算机随机读入5个分数然后将这5个分数从大到小输出。老道的程序员可能各种冒泡,打擂台,这都比较深入了,先往下看:

  我们借助一个一维数组就可以解决这个问题,创建一个a[11]的数组,这样下标分别为a[0]->a[10],分别表示0分,1分…10分,每当有一个分数出现,就在对应的下标位置+1,最后打印即可满足我们现在的要求。

  1.  int main(int argc, const char * argv[]) {
  2.   
  3.   int a[11];
  4.   int scannedNumber;
  5.   
  6.   for (int i = 0; i < 11; i ++) {
  7.     a[i] = 0;
  8.   }
  9.   
  10.   for (int j = 0; j < 5; j ++) {
  11.     scanf("%d", &scannedNumber);
  12.     a[scannedNumber] ++;
  13.   }
  14.   
  15.   for (int k = 10; k >= 0; k --) {
  16.     for (int l = 0; l < a[k]; l ++) {
  17.       printf("%d", k);
  18.     }
  19.   }
  20.   
  21.   return 0;
  22. }
复制代码


  这种排序算法,我们称为桶排序,每个分数都好比一个桶,每出现一次,就在桶中加一点东西。接下来,我们尝试着对数据范围在0~100之间的任意数量数字进行从大到小的排序:

  1. int main(int argc, const char * argv[]) {
  2.   int book[101], scannedNumber;
  3.   int inputCount;
  4.   
  5.   for (int i = 0; i < 101; i ++) {
  6.     book[i] = 0;
  7.   }
  8.   
  9.   printf("Enter numbers you want:");
  10.   scanf("%d", &inputCount);
  11.   
  12.   for (int j = 0; j < inputCount; j ++) {
  13.     scanf("%d", &scannedNumber);
  14.     book[scannedNumber] ++;
  15.   }
  16.   
  17.   for (int k = 100; k >= 0; k --) {
  18.     for (int l = 0; l < book[k]; l ++) {
  19.       printf("%d ", k);
  20.     }
  21.   }
  22.   
  23.   return 0;
  24. }
复制代码


  同样没有什么问题的,我们接下来考虑时间复杂度的问题:代码中第6行,循环了M次(M为桶的个数),第14行循环了N次(输入的数字个数),19行循环了M+N次,所以我们得到时间复杂度为O(2*(M+N)),在说时间复杂度的时候,可以忽略较小的常数,所以最终的时间复杂度为:

 
  1.  O(M+N)
复制代码


  这是一个非常快的排序算法,其实这还不是真正的桶排序,桶排序实际要更复杂,这个只能算简化版。基本上还不能算是一个真正意义的算法,上边的处理如果碰到输出得该分数的同学的信息就显得有点问题了,因为我们只是输出了分数。所以引出第二节:冒泡排序

  冒泡排序

  简化版的桶排序,不仅仅有使用范围的限制,更是浪费空间,如果我们需要排序的范围是0~2100000000,那就要申请2100000001个变量,我们要用这么多的桶来存储每一个数字出现的次数。即时,你只给3个数字(1, 19999, 1999999)排序,也需要2000001个桶,太浪费了。还不止,如果是浮点型呢?那我们接触一个新的算法,冒泡排序!它可以很好的解决这2个问题。冒泡排序的基本思想是,相邻的2个元素,如果顺序错误就把他们位置互换。如果我们要将

  
  1. 12, 35, 99, 18, 76
复制代码


  这几个数从大到小进行排序,越小的越靠后。

  首先:比较第1位和第2位的大小,我们发现12要比35小,所以交换位置,交换后:

 
  1.  35, 12, 99, 18, 76
复制代码


  然后:按照上述的方法,继续往下比较,第2位与第3位….

  
  1. 35, 99, 12, 18, 76
复制代码


  继续:第3位和第4位:

  
  1. 35, 99, 18, 12, 76
复制代码


  继续:第4位和第5位:

 
  1.  35, 99, 18, 76, 12
复制代码


  经过4次比较之后,最小的数字已经到了最后一位,一位一位的比,大的就往前换,就像一个气泡,所以称为冒泡。到这里,我们只是将其中的一个数字归位了,继续重复上面的过程:继续比较第1位与第2位,第2位与第3位,第3位与第4位,你会发现,第5位不需要比较了,因为他已经是最小的了。第二次比较后:

 
  1.  99, 35, 76, 18, 12
复制代码


  接下来的几次都是这样,有几个数字,比较的次数是n-1趟。冒泡的原则是,每次比较只将1个数组归位。接下来我们代码实现:

  1. int main(int argc, const char * argv[]) {
  2.   int a[20], scannedNumber, input;
  3.   
  4.   scanf("%d", &input);
  5.   
  6.   for (int i = 1; i <= input; i ++) {
  7.     scanf("%d", &scannedNumber);
  8.     a[i] = scannedNumber;
  9.   }
  10.   
  11.   // 共有INPUT个数字,所以只需要排INPUT-1次即可
  12.   for (int i = 1; i <= input - 1; i ++) {
  13.    
  14.     // INPUT-I 意味着,每一次外层循环后,都有一个数字归位
  15.     for (int j = 1; j <= input - i ; j ++) {
  16.       
  17.       // 交换
  18.       if ( a[j] < a[j + 1] ) {
  19.         int temp = a[j];
  20.         a[j] = a[j + 1];
  21.         a[j + 1] = temp;
  22.       }
  23.     }
  24.   }
  25.   
  26.   for (int i = 1; i <= input; i ++) {
  27.     printf("%d ", a[i]);
  28.   }
  29.   
  30.   return 0;
  31. }
复制代码


  将上边的代码稍稍修改,就可以解决前面桶排序无法做到的输出学生信息以及浮点数的问题:

  1. struct Student {
  2.   char name[20];
  3.   float score;
  4. };
  5. int main(int argc, const char * argv[]) {
  6.   
  7.   struct Student s[100];
  8.   int scannedNumber;
  9.   
  10.   scanf("%d", &scannedNumber);
  11.   
  12.   for (int i = 1; i <= scannedNumber; i ++) {
  13.     scanf("%s %f", s[i].name, &s[i].score);
  14.   }
  15.   
  16.   // 控制排序次数
  17.   for (int j = 1; j <= scannedNumber - 1; j ++) {
  18.     for (int k = 1; k <= scannedNumber - j; k ++) {
  19.       if (s[k].score < s[k+1].score) {
  20.         struct Student temp = s[k];
  21.         s[k] = s[k + 1];
  22.         s[k + 1] = temp;
  23.       }
  24.     }
  25.   }
  26.   
  27.   for (int l = 1; l <= scannedNumber; l ++) {
  28.     printf("%s, %.2f\n", s[l].name, s[l].score);
  29.   }
  30.   
  31.   return 0;
  32. }
复制代码


  完美搞定了。输入:

  1. dylan 81.5
  2. alice 64.6
  3. peter 91.4
  4. bobo 31.9
  5. amy 67
复制代码


  输出:

  1. peter, 91.40
  2. dylan, 81.50
  3. amy, 67.00
  4. alice, 64.60
  5. bobo, 31.90
复制代码


  冒泡排序的核心部分是嵌套循环,不难看出,冒泡循环的复杂度是:

 
  1.  O(N^2)
复制代码

  这是一个很高的时间复杂度,冒泡排序除了它迷人的名字,以时间复杂度来看,没什么好推荐的,想要更好的排序么?

  快速排序

  冒泡排序算是我们学习的第一个算法,但是时间浪费的极多。假定计算机运行10亿次/秒,桶排序需要10亿+1个位置,但只需要0.1s,冒泡排序则需要1千万秒。接下来我们了解快速排序。首先记住快速排序的核心方法:设,基准数为左边第一个数,保证基准数左边全部比它小,右边全部比它大;所以2个起点,最左边、最右边。共同向中间触发,右边先走(注意,左边为基准数,一定要先从右往左,先想想为什么,后面给出解释),先从右边向左边找一个比基准数小的数字,然后从左边向右边找一个比基准数大的数字,交换他们。当左右碰面的时候,交换当前数字与基准数的位置。当基准数确认位置之后,基准数左边、右边分为2个子列(有一点点2分味道,以后讲),在进行设置基准数,寻找。这里用到了递归,所以我们来模拟一下过程,假定有这样一个数列:

 
  1.  6, 1, 2, 7, 9, 3, 4, 5, 10, 8
复制代码


  我们以最左边的6为初始基准数,从左向右找一个大于6的数,从右向左找一个小于6的数字,并交换,我们发现,从右向左第一个小于6的数字是5,从左向右第一个大于6的数字是7,交换他们的位置

 
  1.  6, 1, 2, 5, 9, 3, 4, 7, 10, 8
复制代码


  接下来,继续向前寻找,左向右发现了9,右向左发现了4,所以交换他们:

 
  1.  6, 1, 2, 5, 4, 3, 9, 7, 10, 8
复制代码


 
  1.  3, 1, 2, 5, 4, 6, 9, 7, 10, 8
复制代码


  这样,基准数字6已经归位,而且左边都是小于6的数字,右边都是大于6的数字。接下来,我们分别处理左边、右边两个数列:

  1. 3, 1, 2, 5, 4
  2. 9, 7, 10, 8
复制代码


  先处理第一个序列,3为基准数:

  1.    i→      ←j
  2. 3, 1, 2, 5, 4
  3.       得
  4. 2, 1, 3, 5, 4
  5.       得
  6. 子串1: 2, 1   -> 1, 2
  7. 子串2: 5, 4   -> 4, 5
复制代码


  因为是右边先开始,所以在2的位置,会碰撞,交换位置即得到了结果。子串9, 7, 10, 8大家自己去分析一下。最终排序结束了。然后我们按照上边的思想来写代码:

  1. int a[11];
  2. int count = 10;
  3. void sort(int left, int right);
  4. int main(int argc, const char * argv[]) {
  5.   
  6.   for (int i = 1; i <= count; i ++) {
  7.     scanf("%d", &a[i]);
  8.   }
  9.   
  10.   sort(1, count);
  11.   
  12.   for (int j = 1; j <= count; j ++) {
  13.     printf("%d ", a[j]);
  14.   }
  15.   
  16.   return 0;
  17. }
  18. void sort(int left, int right) {
  19.   if ( left > right ) {
  20.     return;
  21.   }
  22.   
  23.   // 设置基准数
  24.   int refNum = a[left];
  25.   
  26.   // 设置左右起点
  27.   int lPoint = left;
  28.   int rPoint = right;
  29.   
  30.   // 当没有碰撞的时候,不停的交换
  31.   while (lPoint != rPoint) {
  32.     // 从右边开始找,比基准数小的数字, 然后停止,注意我的判断,如果比基准数大,rPoint向前移动一位,也就是说,如果比基准数字小,rPoint记录的就是这个数字的位置
  33.     while (a[rPoint] >= refNum && lPoint < rPoint) {
  34.       rPoint --;
  35.     }
  36.    
  37.     // 左边找,比基准数大的数字,然后停止
  38.     while (a[lPoint] <= refNum && lPoint < rPoint ) {
  39.       lPoint ++;
  40.     }
  41.    
  42.     // 交换位置
  43.     if ( lPoint < rPoint ) {
  44.       int temp = a[lPoint];
  45.       a[lPoint] = a[rPoint];
  46.       a[rPoint] = temp;
  47.     }
  48.   }
  49.   
  50.   // 归位基准数字,这个时候,左右标记点处于同一个位置上,也就是基准点应该在的位置
  51.   a[left] = a[lPoint];
  52.   a[lPoint] = refNum;
  53.   // 交换之后,开始处理子串,基准数不需要动位置
  54.   sort(left, lPoint - 1);
  55.   sort(lPoint + 1, right);
  56.   
  57.   return ;
  58. }
复制代码


  现在我们来回顾上边的问题左边为基准数,为什么一定要先从右边开始?

  基准数字在左边,假设,左边先开始,找的是比基准数字大的数字:

 
  1.  3, 1, 2, 6, 7
复制代码


  如上,找到数字6的时候,左边停下了,右边开始寻找,发现直接碰撞了,变成了:

 
  1.  6, 1, 2, 3, 7
复制代码


  但是如果从右边开始就会变成

 
  1.  2, 1, 3, 6, 7
复制代码


  总结

  排序的算法还有很多,计数、基数、插入、归并、堆排序等,我们在后边会慢慢的涉及到。当然,快排的时间复杂度怎么算呢?我们想想,最差的情况,就是像冒泡一样,相邻的2个数字不停的交换,为:

  
  1. O(N^2)
复制代码


  快排的最好时间复杂度为(为什么):

  
  1. O(NLogN)
复制代码


  由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。

  练习

  要求对不定数量的数字进行排序,1秒之内完成。

  拿到这道题,我们关注的应当是1s之内,数字是不定量的,我们需要按照上边提供的时间复杂度来讲。假如说现在范围超级大,使用桶排序基本不可能的,因为没法申请那么大的数组,如果数字超级多,使用冒泡排序的时间复杂度又是O(N^2),但是使用快速排序却很好。代码省略了。

  本文结束。

原文作者:佚名  来源:开发者头条
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部