<small id="7ktuj"></small>
      <bdo id="7ktuj"></bdo>
        <mark id="7ktuj"></mark>

        <source id="7ktuj"></source>
        <small id="7ktuj"></small>

        ITPub博客

        首頁 > 應用開發 > Java > 排序算法之折半插入排序

        排序算法之折半插入排序

        原創 Java 作者:蝴蝶飛啊飛 時間:2019-10-21 12:12:25 0 刪除 編輯

        1 、介紹。

        將直接插入排序中尋找A[i] 的插入位置的方法改為采用折半比較,即可得到折半插入排序算法。在處理 A[i] 時, A[0] …… A[i-1] 已經按關鍵碼值排好序。所謂折半比較,就是在插入 A[i] 時,取 A[i-1/2] 的關鍵碼值與 A[i] 的關鍵碼值進行比較,如果 A[i] 的關鍵碼值小于 A[i-1/2] 的關鍵碼值,則說明 A[i] 只能插入 A[0] A[i-1/2] 之間,故可以在外匯返傭http://www.kaifx.cn/ A[0] A[i-1/2-1] 之間繼續使用折半比較;否則只能插入 A[i-1/2] A[i-1] 之間,故可以在 A[i-1/2+1] A[i-1] 之間繼續使用折半比較。如此擔負,直到最后能夠確定插入的位置為止。一般在 A[k] A[r] 之間采用折半,其中間結點為 A[k+r/2] ,經過一次比較即可排除一半記錄,把可能插入的區間減小了一半,故稱為折半。執行折半插入排序的前提是文件記錄必須按順序存儲。  

        折半插入排序是穩定排序,不需要額外內存,空間復雜度O(1) 。時間復雜度,最佳情況: O(n^2)   最差情況: O(n^2)   平均情況: O(n^2)

        2 、步驟。

        跟直接插入排序的步驟相似,只不過查找插入點的方法不一樣。直接插入排序是從有序區的最后一個數依次向前找,而折半插入排序是通過折半的方式進行查找。

        (1) 計算 0 ~ i-1 的中間點,用 i 索引處的元素與中間值進行比較,如果 i 索引處的元素大,說明要插入的這個元素應該在中間值和剛加入 i 索引之間,反之,就是在剛開始的位置 到中間值的位置,這樣很簡單的完成了折半;

        (2) 在相應的半個范圍里面找插入的位置時,不斷的用( 1 )步驟縮小范圍,不停的折半,范圍依次縮小為 1/2 1/4 1/8 ....... 快速的確定出第 i 個元素要插在什么地方;

        (3) 確定位置之后,將整個序列后移,并將元素插入到相應位置。

        3 、代碼。

        public static void main(String[] args) {

                System.out.println("------ 開始 ------");

                // 生成生成兩份隨機數組,其中用系統自帶的方法進行排序,到時候進行驗證。

                final int number = 100000;

                int[] sortArray = new int[number];

                int[] sortArrayCopy = new int[number];

                for (int i = 0; i < sortArray.length; i++) {

                    sortArray[i] = (int) (Math.random() * number);

                }

                System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);// 數組復制

                Arrays.sort(sortArrayCopy);

                // 開始排序

                long startTime = System.currentTimeMillis();

                halveInsertSort(sortArray);// 折半插入排序

                System.out.println(" 花費時間: " + (System.currentTimeMillis() - startTime));

                // 跟系統排序之后數組進行比較,查看是否排序成功。

                if (Arrays.equals(sortArray, sortArrayCopy)) {

                    System.out.println(" 排序成功 ");

                } else {

                    System.out.println(" 排序失敗 ");

                }

                System.out.println("------ 結束 ------");

            }

        // 折半插入排序 最佳情況: T(n) = O(n)    最壞情況: T(n) = O(n2)    平均情況: T(n) = O(n2)

        private static void halveInsertSort(int[] array) {

            int flag;

            int low, middle, high;

            for (int i = 1; i < array.length; i++) {//n-1

                flag = array[i];

                low = 0;

                high = i - 1;

                while (low <= high) {// 最后的情況就是 low==high==middle 的判斷

                    middle = (low + high) / 2;

                    if (array[i] > array[middle]) {

                        low = middle + 1;

                    } else {

                        high = middle - 1;

                    }

                }

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

                    array[j] = array[j - 1];

                }

                array[high + 1] = flag;

            }

        }

        public class InsertSort {

            /* 使用折半插入法進行排序 */

            public static void main(String[] args) {

                int array[]=new int[]{9,8,7,6,5,4,3,2,1};  // 把待排序的數存放在數組中

                int i,j,temp;

                int low,high,mid;

                for(i=1;i<array.length;i++){// 需要進行 n-1 趟插入排序

                    temp=array[i];

                    low=0;

                    high=i-1;

                    while(low<=high){  // 折半查找插入位置

                        mid=(low+high)/2;

                        if(array[mid]>temp){

                            high=mid-1;

                        }else{

                            low=mid+1;

                        }

                    }

                    for(j=i-1;j>=low;j--){   // 后移

                        array[j+1]=array[j];

                    }

                    array[low]=temp;  // 插入

                }

                for(i=0;i<array.length;i++){

                    System.out.print(array[i]+" ");

                }

            }

        }

        類型定義頭文件

         #define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */

         typedef int InfoType; /* 定義其它數據項的類型 */

         typedef int KeyType; /* 定義關鍵字類型為整型 */

         typedef struct

         {

           KeyType key; /* 關鍵字項 */

           InfoType otherinfo; /* 其它數據項,具體類型在主程中定義 */

         }RedType; /* 記錄類型 */

         typedef struct

         {

           RedType r[MAXSIZE+1]; /* r[0] 閑置或用作哨兵單元 */

           int length; /* 順序表長度 */

         }SqList; /* 順序表類型 */

        函數文件

        void BinInsertSort(SqList *L)

        /* 折半插入排序 */

        {

            int i,j,mid,low,high;

            DataType t;

            for(i=1;i<L->length;i++)        /* i 個元素已經有序,從第 i+1 個元素開始與前 i 個的有序的關鍵字比較 */

            {

                t=L->data[i+1];             /* 取出第 i+1 個元素,即待排序的元素 */

                low=1,high=i;

                while(low<=high)            /* 利用折半查找思想尋找當前元素的合適位置 */

                {

                    mid=(low+high)/2;

                    if(L->data[mid].key>t.key)

                        high=mid-1;

                    else

                        low=mid+1;

                }

                for(j=i;j>=low;j--)     /* 移動元素,空出要插入的位置 */

                    L->data[j+1]=L->data[j];

                L->data[low]=t;         /* 將當前元素插入合適的位置 */    

            }

        }

        主程序

         #define LT(a,b) ((a)<(b))

         #define N 8

         void print(SqList L)

         {

           int i;

           for(i=1;i<=L.length;i++)

             printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);

           printf("\n");

         }

         void main()

         {

           RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};

           SqList l;

           int i;

           for(i=0;i<N;i++) /* l1.r 賦值 */

             l1.r[i+1]=d[i];

           l.length=N;

           printf(" 排序前 :\n");

           print(l);

           BInsertSort(&l);

           printf(" 折半插入排序后 :\n");

           print(l);

         }


        來自 “ ITPUB博客 ” ,鏈接:http://www.ep4tq.com/69946279/viewspace-2660762/,如需轉載,請注明出處,否則將追究法律責任。

        請登錄后發表評論 登錄
        全部評論
        管他誰是誰非,做自己的主宰,我是這條街最亮的崽!

        注冊時間:2019-08-22

        • 博文量
          49
        • 訪問量
          21835
        妹子图每日分享