免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項超值服

開通VIP
5分鐘了解折半插入排序

前言 折半插入排序(Binary Insertion Sort)是對直接插入排序算法的一種改進(jìn)。

插入排序思想介紹

折半插入排序與直接插入排序算法原理相同。只是,在向已排序的數(shù)據(jù)中插入數(shù)據(jù)時,采用來折半查找(二分查找)。先取已經(jīng)排序的序列的中間元素,與待插入的數(shù)據(jù)進(jìn)行比較,如果中間元素的值大于待插入的數(shù)據(jù),那么待插入的數(shù)據(jù)屬于數(shù)組的前半部分,否則屬于后半部分。依次類推,不斷縮小范圍,確定要插入的位置。

算法說明:

待排序數(shù)據(jù):21,6,7,4

取第一個元素作為有序表,剩余的元素作為無序表

     其中有序表:2;無序表:1,6,74

第一次比較,從無序表中取出第一個數(shù) 1,與中間值2比較,1<2,1插到2的前面,得到

     有序表:12;無序表:6,7,4

第二次比較,從無序表中取出第一個數(shù) 6,與中間值1比較,6>1,要放在1的后面,再與后半?yún)^(qū)(有序表:2)的中間值2比較,6>2,6插入到2的后面,得到

     有序表:1,2,6;無序表:7,4

第三次比較,從無序表中取出第一個數(shù) 7,與中間值2比較,7>2,7放在2后面,再與后半?yún)^(qū)(有序表:6)的中間值6比較,7>6,7放在6后面,得到

     有序表:1,26,7;無序表:4

第四次比較,從無序表中取出第一個數(shù) 4與中間值2比較,4>24放在2后面,再與后半?yún)^(qū)(有序表:6,7)的中間值6比較,4<6,4放在6前面,最終得到:

     1,2,4,67

折半插入排序的代碼實現(xiàn)

1. private void binaryInsertSort(int arr[]){  

2.   

3.         int low = 0;  

4.         int high = 0;  

5.         int m = 0;// 中間位置  

6.         for(int i = 1; i < arr.length; i++){  

7.             low = 0;  

8.             high = i-1;  

9.             while(low <= high){  

10.                 m = (low+high)/2;  

11.                 if(arr[m] > arr[i])  

12.                     high = m - 1;  

13.                 else  

14.                     low = m + 1;  

15.             }  

16.             //統(tǒng)一移動元素,將待排序元素插入到指定位置  

17.             temp = arr[i];  

18.             for(int j=i; j > high+1; j--){  

19.                 arr[j] = arr[j-1];  

20.             }  

21.             arr[high+1] = temp;  

22.         }          

23.     }  

總結(jié)

折半插入排序相對穩(wěn)定,相對于直接插入排序,減少了比較次數(shù);但是相對直接插入排序,移動次數(shù)不變。

本站僅提供存儲服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點擊舉報。
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
常見排序算法(冒泡,選擇,快速)的C語言實現(xiàn)
冒泡排序,經(jīng)典的排序算法
排序算法 --- 插入排序
各種排序算法總結(jié)
冒泡排序、插入排序與選擇排序
8大經(jīng)典排序算法
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點擊這里聯(lián)系客服!

聯(lián)系客服