快速排序与折半排序是一个概念吗？？
求代码快速排序，与折半排序

不是同一种。

快速排序（Quicksort）通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。

折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。折半插入排序算法的时间复杂度为O(n^2)

快速排序代码：

1.         public static void quickSort(int a[],int start,int end)
   
2.         {
   
3.             int i,j;
   
4.             i = start;
   
5.             j = end;
   
6.             if((a==null)||(a.length==0))
   
7.                 return;
   
8.             while(i<j)
   
9.             {
   
10.                 while(i<j&&a[i]<=a[j])/*以数组start下标的数据为key，右侧扫描*/
    
11.                 {
    
12.                     j--;
    
13.                 }
    
14.                 if(i<j)/*右侧扫描，找出第一个比key小的，交换位置*/
    
15.                 {
    
16.                     int temp = a[i];
    
17.                     a[i] = a[j];
    
18.                     a[j] = temp;
    
19.                 }
    
20.                 while(i<j&&a[i]<a[j])/*左侧扫描（此时a[j]中存储着key值）*/
    
21.                 {
    
22.                     i++;
    
23.                 }
    
24.                 if(i<j)/*找出第一个比key大的，交换位置*/
    
25.                 {
    
26.                     int temp = a[i];
    
27.                     a[i] = a[j];
    
28.                     a[j] = temp;
    
29.                 }
    
30.             }
    
31.             if(i-start>1)
    
32.             {
    
33.         /*递归调用，把key前面的完成排序*/
    
34.                 quickSort(a,start,i-1);
    
35.             }
    
36.             if(end-i>1)
    
37.             {
    
38.                 quickSort(a,i+1,end);/*递归调用，把key后面的完成排序*/
    
39.             }
    
40.         }

复制代码

折半排序：

1.     private static int[] Sort(int[] arr) {
   
2.         int i, j;
   
3.         //保存中间插入的值
   
4.         int insertNote = 0;
   
5.         //将待排序的数列保存起来
   
6.         int[] array = arr;
   
7.         System.out.println("开始排序：");
   
8.         for (i = 1; i < array.length; i++) {
   
9.             int low = 0;
   
10.             int high = i - 1;
    
11.             insertNote = array[i];
    
12.             //不断的折半
    
13.             while (low <= high) {
    
14.                 //找出中间值
    
15.                 int mid = (low + high) / 2;
    
16.                 //如果大于中间值
    
17.                 if (array[i] > array[mid]) {
    
18.                     //在大于中间值的那部分查找
    
19.                     low = mid+1;
    
20.                 } else
    
21.                     //在小于中间值的那部分查找
    
22.                     high = mid-1;
    
23.             }
    
24.           //将整体数组向后移
    
25.             for ( j=i; j > low; j--) {
    
26.                 array[j] = array[j - 1];
    
27.             }
    
28.          //插入到指定的位置
    
29.             array[low] = insertNote;
    
30.             System.out.println(Arrays.toString(array));
    
31.         }
    
32.         System.out.println("排序之后：");
    
33.         System.out.println(Arrays.toString(array));
    
34.         return array;
    
35.     }
    

复制代码

ps:代码我是从网上copy的，没有验证

好的！谢谢，有人说快速排序与折半排序是一样的，把我弄蒙了！！:lol

折半不是查找吗？怎么变排序了

Coup_D`etat 发表于 2014-6-26 11:08
折半不是查找吗？怎么变排序了

同问！!!!!!