黑马程序员技术交流社区

标题: 快速排序 [打印本页]
作者: 天，殇心    时间: 2014-6-25 22:27
标题: 快速排序
快速排序与折半排序是一个概念吗？？
求代码快速排序，与折半排序
作者: 崔湖尧    时间: 2014-6-26 08:37
不是同一种。

快速排序（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的，没有验证
作者: 天，殇心    时间: 2014-6-26 11:03
好的！谢谢，有人说快速排序与折半排序是一样的，把我弄蒙了！！:lol
作者: Coup_D`etat    时间: 2014-6-26 11:08
折半不是查找吗？怎么变排序了
作者: 会说话的木头    时间: 2014-6-26 11:21
Coup_D`etat 发表于 2014-6-26 11:08
折半不是查找吗？怎么变排序了

同问！!!!!!



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