A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

喔喔去222

初级黑马

  • 黑马币:

  • 帖子:

  • 精华:

© 喔喔去222 初级黑马   /  2013-10-1 11:36  /  1244 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 杨增坤 于 2013-10-1 21:18 编辑

网上看到的一种选择排序,有大神能注释下我标//的地方吗?看不懂是怎么实现的
  1. public int getMiddle(int[] arr, int low, int high) {
  2.                 int tmp = arr[low];   
  3.                 while (low < high) {
  4.                         while (low < high && arr[high] >= tmp)
  5.                                 high--;
  6.                         arr[low] = arr[high];     //
  7.                         while (low < high && arr[low] <= tmp)
  8.                                 low++;
  9.                         arr[high] = arr[low];    //
  10.                 }  
  11.                 arr[low] = tmp;                  //
  12.                 return low;                     //
  13.         }

  14. public void quick(int[] arr, int low, int high) {
  15.                 if (low < high) {
  16.                         int mid = getMiddle(arr, low, high);  
  17.                         quick(arr, low, mid -1);        
  18.                         quick(arr, mid+1, high);      
  19.                 }
  20.         }
复制代码

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

4 个回复

倒序浏览
这是快速排序,你可以先看一下快排的思想,然后再看代码,估计你就看懂了

评分

参与人数 1黑马币 +1 收起 理由
乔兵 + 1

查看全部评分

回复 使用道具 举报
5、快速排序(Quick Sort)
快速排序是非常优秀的排序算法,初学者可能觉得有点难理解,其实它是一种“分而治之”的思想,把大的拆分为小的,小的再拆分为更小的,所以你一会儿从代码中就能很清楚地看到,用了递归。如图:

其中要选择一个轴值,这个轴值在理想的情况下就是中轴,中轴起的作用就是让其左边的元素比它小,它右边的元素不小于它。(我用了“不小于”而不是“大于”是考虑到元素数值会有重复的情况,在代码中也能看出来,如果把“>=”运算符换成“>”,将会出问题)当然,如果中轴选得不好,选了个最大元素或者最小元素,那情况就比较糟糕,我选轴值的办法是取出第一个元素,中间的元素和最后一个元素,然后从这三个元素中选中间值,这已经可以应付绝大多数情况。

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

回复 使用道具 举报
这个在数据结构里叫做快速排序,建议你找数据结构的书或者网上找相关的内容,看看都能明白。在这上面没有图示直接说是不好讲的。简单的给你注释下,希望对你有帮助
  1. //一趟快速排序(一次划分)
  2. /*
  3. 一次划分后的结果是:tmp左边的元素都比tmp小,右边的元素都比tmp大。
  4. 相当于以tem为界将原数组分成了左右两部分,将左右部分都看做整体,那么(左部、tmp、右部)就是有序的,
  5. 左右俩部分的内部是无序的。想想二叉树
  6. */
  7. public int getMiddle(int[] arr, int low, int high) {
  8.          int tmp = arr[low];
  9.          while (low < high) {
  10.                   while (low < high && arr[high] >= tmp)
  11.                           high--;
  12.                   arr[low] = arr[high];      //将比tmp小的元素移到左端
  13.           while (low < high && arr[low] <= tmp)
  14.                           low++;
  15.                   arr[high] = arr[low];     //将比tmp大的元素移到右端
  16.                   }  
  17.                   arr[low] = tmp;           //将tmp放在正确的位置
  18.                   return low;               //返回tmp位置
  19. }


  20. //快速排序
  21. //不断的对出现的左右部就行划分,递归。最终将得到有序的数组
  22. public void quick(int[] arr, int low, int high) {
  23.         if (low < high) {
  24.                 int mid = getMiddle(arr, low, high);
  25.                 quick(arr, low, mid -1);
  26.                 quick(arr, mid+1, high);      
  27. }
  28. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1 赞一个!

查看全部评分

回复 使用道具 举报
跟你讲原理把。具体的自己理解下。用的是二分的思想。在一个排好顺的数组中,你再把一个元素放进去。你可以把这个元素和数组的中间元素对比。这样就把就把位置缩小一半。循环下去。最终找到这个数应该所在的位置

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马