黑马程序员技术交流社区

标题: 关于快速排序的问题 [打印本页]
作者: ぺsimon☆    时间: 2013-4-11 16:45
标题: 关于快速排序的问题
兄弟们好
有个问题我想问一下:

快速排序和折半排序是一样的吗,是不是只是叫法不同而已呢?
如果不是一样的,那他们有什么区别呢?
作者: 庄生晓梦    时间: 2013-4-11 17:09
快速排序是排序方法。
折半查找是是一种查找方法。
作者: 刘林虎    时间: 2013-4-11 17:28

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
作者: 蓝色骨头    时间: 2013-4-11 17:39
本帖最后由 蓝色骨头 于 2013-4-11 17:53 编辑

快速排序和折半排序是一样的吗,是不是只是叫法不同而已呢?

快速排序是一种最常用的排序方式，随机化的快速排序的效率为nlgn，比较排序的最高效率也就是nlgn
下面是随机化快速排序的实现方式
  1. private static void mySwitch(int[] arr, int i, int j){
  2.                 int t  = arr[i];
  3.                 arr[i] = arr[j];
  4.                 arr[j] = t;
  5.         }
  6.         private static int partition(int[] arr, int left, int right){
  7.                 Random rand = new Random();
  8.                 int mid = rand.nextInt(right - left + 1) + left;
  9.                 int i = left - 1;               
  10.                 mySwitch(arr, mid, right);
  11.                 /*
  12.                  * 把 所有比mid小的移到左边
  13.                  * i 记录第一个比mid大的起始位置
  14.                  */
  15.                 for(int j = left; j < right; j++){
  16.                         if(arr[j] <= arr[right]){
  17.                                 i++;
  18.                                 mySwitch(arr, i, j);
  19.                         }
  20.                 }
  21.                 mySwitch(arr, i+1, right);               
  22.                 return i+1;               
  23.         }
  24.         public static void quikSort(int[] arr, int left, int right){
  25.                 if(left>right){
  26.                         return;
  27.                 }
  28.                
  29.                 int[] stack = new int[arr.length];
  30.                 int top = 0;
  31.                 stack[top++] = left;
  32.                 stack[top++] = right;       
  33.                
  34.                 while(top>0){                       
  35.                         int Right = stack[--top];
  36.                         int Left = stack[--top];
  37.                        
  38.                         int p = partition(arr,Left,Right);
  39.                         if(p-Left>1){
  40.                                 stack[top++] = Left;
  41.                                 stack[top++] = p-1;
  42.                         }
  43.                        
  44.                         if(Right-p>1){
  45.                                 stack[top++] = p+1;
  46.                                 stack[top++] = Right;
  47.                         }
  48.                 }
  49.         }
复制代码
折半排序没有听说过，有折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
作者: 黄玉昆    时间: 2013-4-11 19:44
如果问题未解决，请继续追问，如果没有问题了，请将帖子分类 改为“已解决”，谢谢
作者: ぺsimon☆    时间: 2013-4-14 19:33
黄玉昆 发表于 2013-4-11 19:44
如果问题未解决，请继续追问，如果没有问题了，请将帖子分类 改为“已解决”，谢谢 ...

哦,好的



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