一区二区三区日韩精品-日韩经典一区二区三区-五月激情综合丁香婷婷-欧美精品中文字幕专区

搜索
分享

排序算法--折半插入排序（二分查找排序）

 集微筆記 2013-07-31

 

折半插入排序其實就是直接插入排序的一種改進(jìn)，引入了二分查找算法，這樣關(guān)鍵字的比較次數(shù)就會減少，

數(shù)量級為O(nlog^2n)，但是元素移動次數(shù)還是O(n^2)，所以折半插入排序的時間復(fù)雜度是O(n^2)。

另外，折半插入排序是穩(wěn)定的排序算法；

下面是用JAVA寫的算法的兩種實現(xiàn)方式。不過原理都是一樣的

第一種：

  package sort;

Java代碼 復(fù)制代碼 收藏代碼
  1. import java.util.Arrays;   
  2.   
  3. public class BinarySearch1 {   
  4.     public static void main(String args[])   
  5.     {   
  6.         int array[]={49,38,65,97,76,13,27};   
  7.         binarySort(array,array.length);   
  8.         System.out.println("---------排序后的結(jié)果----------");   
  9.         System.out.println(Arrays.toString(array));   
  10.     }   
  11.        
  12.     //二分查找   
  13.     public static int binarySearch(int array[],int low,int high,int temp)   
  14.     {   
  15.         int mid=0;   
  16.         while(low<=high)   
  17.         {   
  18.             mid=(low high)/2;   
  19.             if(array[mid]<temp&&temp<=array[mid 1])   
  20.                 return (mid 1);   
  21.             else if(array[mid]<temp)   
  22.                 low = mid   1;   
  23.             else  
  24.                 high = mid -1;   
  25.         }   
  26.         return high;   
  27.     }   
  28.        
  29.     //二分排序   
  30.     public static void binarySort(int array[],int size)   
  31.     {   
  32.         int i,j,k,temp;   
  33.         for(i=1;i<size;i )   
  34.         {   
  35.             temp=array[i];   
  36.             if(array[i]<array[0])   
  37.                 k=0;   
  38.             else  
  39.                 k = binarySearch(array,0,i,temp);   
  40.                
  41.             for(j=i;j>k;j--)   
  42.             {   
  43.                 array[j]=array[j-1];   
  44.             }   
  45.             array[k]=temp;   
  46.             System.out.println(Arrays.toString(array));   
  47.         }   
  48.     }   
  49. }  
 

運(yùn)行結(jié)果如下：

  [38, 49, 65, 97, 76, 13, 27]

Java代碼 復(fù)制代碼 收藏代碼
  1. [38, 49, 65, 97, 76, 13, 27]   
  2. [38, 49, 65, 97, 76, 13, 27]   
  3. [38, 49, 65, 76, 97, 13, 27]   
  4. [13, 38, 49, 65, 76, 97, 27]   
  5. [13, 27, 38, 49, 65, 76, 97]   
  6. ---------排序后的結(jié)果----------   
  7. [13, 27, 38, 49, 65, 76, 97]  
 

第二種：

 

Java代碼 復(fù)制代碼 收藏代碼
  1. package sort;   
  2.   
  3. import java.util.Arrays;   
  4.   
  5. public class BinarySearch2 {   
  6.     public static void main(String args[])   
  7.     {   
  8.         int array[]={49,38,65,97,76,13,27};   
  9.         binaryInsertSort(array,array.length);   
  10.         System.out.println("------------排序后的結(jié)果-------------");   
  11.         System.out.println(Arrays.toString(array));   
  12.     }   
  13.        
  14.     /**  
  15.      *   
  16.      * @param array 要排序的數(shù)組  
  17.      * @param size 數(shù)組的大小  
  18.      */  
  19.     public static void binaryInsertSort(int []array,int size)   
  20.     {   
  21.         int i,j,temp;   
  22.         int low,high,mid;   
  23.         for(i=1;i<size;i )   
  24.         {   
  25.             //將待插入的元素賦給temp，這個元素前面是有序數(shù)組，用于插入到有序數(shù)組中   
  26.             temp=array[i];   
  27.             low=0;   
  28.             high=i-1;   
  29.             while(low<=high)   
  30.             {   
  31.                 //有序數(shù)組的中間坐標(biāo)，此時用于二分查找，減少查找次數(shù)   
  32.                 mid = (low high)/2;   
  33.                 //如果有序序列中的中間元素大于待排序的元素，則有序序列的中間坐標(biāo)向前搜索，否則向后搜索   
  34.                 if(array[mid]>array[i])   
  35.                     high=mid-1;   
  36.                 else  
  37.                     low = mid   1;   
  38.             }   
  39.             /**  
  40.              * j首先賦值為要插入值的前一個元素的最后的坐標(biāo)，也就是有序數(shù)組中最后一個元素的坐標(biāo)  
  41.              * 然后依次向前掃描有序數(shù)組，然后如果滿足條件則向后移動數(shù)據(jù)  
  42.              */  
  43.                
  44.             for(j=i-1;j>=low;j--)   
  45.             {   
  46.                 array[j 1]=array[j];   
  47.             }   
  48.             //將待排序的元素插入到array數(shù)組中   
  49.             array[low]=temp;   
  50.             System.out.println(Arrays.toString(array));   
  51.         }   
  52.     }   
  53.        
  54. }  

 運(yùn)行結(jié)果：

 

Java代碼 復(fù)制代碼 收藏代碼
  1. [38, 49, 65, 97, 76, 13, 27]   
  2. [38, 49, 65, 97, 76, 13, 27]   
  3. [38, 49, 65, 97, 76, 13, 27]   
  4. [38, 49, 65, 76, 97, 13, 27]   
  5. [13, 38, 49, 65, 76, 97, 27]   
  6. [13, 27, 38, 49, 65, 76, 97]   
  7. ------------排序后的結(jié)果-------------   
  8. [13, 27, 38, 49, 65, 76, 97]  
 

 

 

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多

    91欧美日韩精品在线| 高清不卡视频在线观看| 国产在线一区二区三区不卡 | 91人妻人人澡人人人人精品| 国产三级不卡在线观看视频| 91福利视频日本免费看看| 冬爱琴音一区二区中文字幕| 亚洲精品伦理熟女国产一区二区| 日韩亚洲激情在线观看| 亚洲最新中文字幕一区| 在线观看中文字幕91| 99久久精品国产麻豆| 在线欧美精品二区三区| 日韩亚洲精品国产第二页| 国产av一区二区三区麻豆| 亚洲中文字幕在线视频频道| 欧美色欧美亚洲日在线| 成人欧美精品一区二区三区| 黄色三级日本在线观看| 亚洲欧美国产网爆精品| 久久综合狠狠综合久久综合| 一区二区三区日本高清| 熟妇久久人妻中文字幕| 欧美一区二区三区不卡高清视| 欧美一级黄片欧美精品| 激情丁香激情五月婷婷| av在线免费播放一区二区| 蜜桃传媒视频麻豆第一区| 国产目拍亚洲精品区一区| 国产不卡的视频在线观看| 国产精品香蕉免费手机视频| 国产高清在线不卡一区| 国产又粗又长又爽又猛的视频| 91久久精品国产成人| 国产又粗又猛又大爽又黄| 九九热这里只有精品视频| 欧美极品欧美精品欧美| 午夜精品国产精品久久久| 国产极品粉嫩尤物一区二区| 国产日韩熟女中文字幕| 丰满人妻一二区二区三区av|