兄弟们好
有个问题我想问一下:

快速排序和折半排序是一样的吗,是不是只是叫法不同而已呢?
如果不是一样的,那他们有什么区别呢?

快速排序是排序方法。
折半查找是是一种查找方法。

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

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

快速排序是一种最常用的排序方式，随机化的快速排序的效率为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
如果问题未解决，请继续追问，如果没有问题了，请将帖子分类 改为“已解决”，谢谢 ...

哦,好的