黑马程序员技术交流社区

标题: 数组排序代码看不懂，，大神帮帮忙 [打印本页]
作者: 喔喔去222    时间: 2013-10-1 11:36
标题: 数组排序代码看不懂，，大神帮帮忙
本帖最后由 杨增坤 于 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.         }

  15. public void quick(int[] arr, int low, int high) {
  16.                 if (low < high) {
  17.                         int mid = getMiddle(arr, low, high);  
  18.                         quick(arr, low, mid -1);        
  19.                         quick(arr, mid+1, high);      
  20.                 }
  21.         }
复制代码
作者: IT_JM    时间: 2013-10-1 13:38
这是快速排序，你可以先看一下快排的思想，然后再看代码，估计你就看懂了
作者: IT_JM    时间: 2013-10-1 13:44
5、快速排序（Quick Sort）
快速排序是非常优秀的排序算法，初学者可能觉得有点难理解，其实它是一种“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的，所以你一会儿从代码中就能很清楚地看到，用了递归。如图：

其中要选择一个轴值，这个轴值在理想的情况下就是中轴，中轴起的作用就是让其左边的元素比它小，它右边的元素不小于它。（我用了“不小于”而不是“大于”是考虑到元素数值会有重复的情况，在代码中也能看出来，如果把“>=”运算符换成“>”，将会出问题）当然，如果中轴选得不好，选了个最大元素或者最小元素，那情况就比较糟糕，我选轴值的办法是取出第一个元素，中间的元素和最后一个元素，然后从这三个元素中选中间值，这已经可以应付绝大多数情况。
作者: 摄影勾魂    时间: 2013-10-1 14:13
这个在数据结构里叫做快速排序，建议你找数据结构的书或者网上找相关的内容，看看都能明白。在这上面没有图示直接说是不好讲的。简单的给你注释下，希望对你有帮助
  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. }


  22. //快速排序
  23. //不断的对出现的左右部就行划分，递归。最终将得到有序的数组
  24. public void quick(int[] arr, int low, int high) {
  25.         if (low < high) {
  26.                 int mid = getMiddle(arr, low, high);
  27.                 quick(arr, low, mid -1);
  28.                 quick(arr, mid+1, high);      
  29. }
  30. }
复制代码
作者: 赖龙威    时间: 2013-10-1 17:21
跟你讲原理把。具体的自己理解下。用的是二分的思想。在一个排好顺的数组中，你再把一个元素放进去。你可以把这个元素和数组的中间元素对比。这样就把就把位置缩小一半。循环下去。最终找到这个数应该所在的位置



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2