不是同一种。
快速排序(Quicksort)通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2)。在实际应用中,快速排序的平均时间复杂度为O(nlogn)。
折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,可以采用折半查找的方法来加快寻找插入点的速度。折半插入排序算法的时间复杂度为O(n^2)
快速排序代码:
- public static void quickSort(int a[],int start,int end)
- {
- int i,j;
- i = start;
- j = end;
- if((a==null)||(a.length==0))
- return;
- while(i<j)
- {
- while(i<j&&a[i]<=a[j])/*以数组start下标的数据为key,右侧扫描*/
- {
- j--;
- }
- if(i<j)/*右侧扫描,找出第一个比key小的,交换位置*/
- {
- int temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- }
- while(i<j&&a[i]<a[j])/*左侧扫描(此时a[j]中存储着key值)*/
- {
- i++;
- }
- if(i<j)/*找出第一个比key大的,交换位置*/
- {
- int temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- }
- }
- if(i-start>1)
- {
- /*递归调用,把key前面的完成排序*/
- quickSort(a,start,i-1);
- }
- if(end-i>1)
- {
- quickSort(a,i+1,end);/*递归调用,把key后面的完成排序*/
- }
- }
复制代码 折半排序:- private static int[] Sort(int[] arr) {
- int i, j;
- //保存中间插入的值
- int insertNote = 0;
- //将待排序的数列保存起来
- int[] array = arr;
- System.out.println("开始排序:");
- for (i = 1; i < array.length; i++) {
- int low = 0;
- int high = i - 1;
- insertNote = array[i];
- //不断的折半
- while (low <= high) {
- //找出中间值
- int mid = (low + high) / 2;
- //如果大于中间值
- if (array[i] > array[mid]) {
- //在大于中间值的那部分查找
- low = mid+1;
- } else
- //在小于中间值的那部分查找
- high = mid-1;
- }
- //将整体数组向后移
- for ( j=i; j > low; j--) {
- array[j] = array[j - 1];
- }
- //插入到指定的位置
- array[low] = insertNote;
- System.out.println(Arrays.toString(array));
- }
- System.out.println("排序之后:");
- System.out.println(Arrays.toString(array));
- return array;
- }
复制代码 ps:代码我是从网上copy的,没有验证
|