C++Binary Search Sort二分検索ソートアルゴリズム

二分ルックアップソートアルゴリズムは実際には挿入ソート法の改良型であり、配列をソート済みとソート済みに分け、初期状態でソートされた部分は最初の要素のみであり、残りはソートされていない部分であり、ソートされた配列の上界が最初の要素であり、下界も最初の要素であり、自然に中間要素も最初の要素である.そして、並べ替えられていない部分の最初の要素(つまり配列全体の最初の要素)は最後の要素に遍歴し、並べ替えられた部分の中間要素と比較して、中間要素より大きい場合は、下界を中間要素+1に置き換えます.中間要素より小さい場合は上界を中間要素-1に置き換えます.位置が見つかるまでループします.位置が見つかったら、挿入位置とその後の要素をすべて1つ後ろに移動し、その要素を挿入します.

void
insertionSort (int N, keytype* A)
{


        /* Lucky you, you get to start from scratch */
        for (int i =1; i=0&&high>=0)
                {
                        int mid =(low + high) / 2;
                        if (A[i] == A[mid]) {
                                low = mid + 1;
                                position = low;
                               break;

                        }
                        if (A[i]>A[mid]) {
                                low = mid + 1;

                        }
                        else {
                                high = mid - 1;
                        }
                 position=low;
                }

                position=low;
                int buffer = A[i];
                int j =i-1;
                while (j>=position)
                        {
                                A[j + 1] = A[j];
                                j--;
                        }
                        A[position]=buffer;
                }



}