Java折半插入排序怎么實現(xiàn)

這篇文章主要講解了“Java折半插入排序怎么實現(xiàn)”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java折半插入排序怎么實現(xiàn)”吧！

插入排序思想介紹

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

算法說明：

待排序數(shù)據(jù)：2，1，6，7，4

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

　　   其中有序表：2；無序表：1，6，7，4

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

　　   有序表：1，2；無序表：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，2，6，7；無序表：4

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

　　   1，2，4，6，7

折半插入排序的代碼實現(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ù)不變。

插入排序思想介紹

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

算法說明：

待排序數(shù)據(jù)：2，1，6，7，4

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

　　   其中有序表：2；無序表：1，6，7，4

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

　　   有序表：1，2；無序表：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，2，6，7；無序表：4

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

　　   1，2，4，6，7

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

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

2.   

3.         int low = ;  

4.         int high = ;  

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

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

7.             low = ;  

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.     }  

感謝各位的閱讀，以上就是“Java折半插入排序怎么實現(xiàn)”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對Java折半插入排序怎么實現(xiàn)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！