您的位置: 首页  >  文章  >  折半插入排序

折半插入排序

分类: 文章 • 2024-08-12 11:11:46

基本思想

    考虑到 L.r[1..i-1] 是按关键字有序的有序序列，则可以利用折半查找实现“ L.r[1…i-1]中查找 L.r[i] 的插入位置”如此实现的插入排序为折半插入排序。折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。

折半插入排序

[java] view plain copy
  1. package sort.insertionSort;  
  2.   
  3. public class BinaryInsertionSort {  
  4.   
  5.     /** 
  6.      * @param args 
  7.      */  
  8.     //对顺序表L做折半插入排序,利用折半查找快速找到要插入的位置  
  9.     public static void binaryInsertSort(int[] L){  
  10.         for(int i = 2; i <= L.length-1; i++){          
  11.             //利用折半查找找到要插入的位置  
  12.             int low = 1, high = i-1;//在1->i-1的有序子序列中插入第i个元素，使之成为1->i的有序子序列  
  13.             L[0] = L[i];//暂存要插入的元素  
  14.             while(low <= high){  
  15.                 int mid = (low+high)/2;  
  16.                 if(L[0] < L[mid])  
  17.                     high = mid -1;  
  18.                 else  
  19.                     //L[0] >= L[mid]  
  20.                     low = mid+1;//等于当成大于处理，这样后出现的相等值就会排在后面，从而到达“稳定”  
  21.             }  
  22.             //此时high = low-1，且high+1即low的位置即为要插入的位置  
  23.             for(int j = i-1; j >= low; j--)  
  24.                 L[j+1] = L[j];  
  25.             L[low] = L[0];  
  26.         }  
  27.     }  
  28.     public static void main(String[] args) {  
  29.         // TODO Auto-generated method stub  
  30.         int[] test = {0, 53, 27, 36, 15, 69, 42}; //0号单元未使用  
  31.         binaryInsertSort(test);  
  32.         for(int i = 1; i <= test.length-1; i++)  
  33.             System.out.print(test[i]+" ");  
  34.     }  
  35. }  
运行结果：
折半插入排序

    折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同,时间复杂度为O(n^2) 。折半插入排序是“稳定的”。

相关推荐