A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 天,殇心 中级黑马   /  2014-6-25 22:27  /  1043 人查看  /  4 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

4 个回复

倒序浏览
不是同一种。

快速排序(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
折半不是查找吗?怎么变排序了

同问!!!!!!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马