ソートアルゴリズム_C++(二)挿入ソートの折半挿入ソート

半角挿入ソートは、二分法挿入ソートとも呼ばれます.このソート・アルゴリズムの「折半」とは、無秩序テーブルの要素を秩序テーブルに挿入する場合、どの位置に挿入しますか?秩序テーブルで挿入位置を探す方法は二分ルックアップです.したがって、折半挿入と呼ばれます.
       i         0    1      2     3    4    5     6      7      8    9                                      
元のシーケンス21 25,549 25*16,0862,3871 54
1回目の分析ではなく、6回目のソートが終わった後に例を挙げて説明します.                                
            i        0    1    2     3    4    5    6     7     8    9
6回目終了08 16 21 25 25*49 62 38 71 54
7回目から無秩序表からaを取り出し[7]、まず秩序表の最後のものと比較すると62より小さいことが判明し、a[7]が必ずa[6]の前に置かれることを示した[6].二分ルックアップ法を用いて秩序テーブルにa[7]の挿入位置を探すことを開始する.秩序テーブルの範囲は0-i-1です.low=0、high=i-1で表します.まずa[7]を一時変数tempに格納する.サイクル条件(low<=high):秩序表の中間位置mid=(low+high)/2を求める;tempとa[mid]を比較すると、temp>a[mid]で、temp(すなわちa[7])の最終挿入位置がmid-highの間にあることを説明すると、low=mid+1となる.temp ハイ、ジャンプサイクル。このときlowの位置はtempの最終的な挿入位置である.
【上記ではtemp==a[mid]を考慮していない場合.等しい場合、high=mid-1ですか、それともlow=mid+1ですか.(もしくはtemp>=a[mid]かtemp<=a[mid]か?)この等号の帰属は,折半挿入並べ替えの安定性を決定する.安定性と不安定性の間では,アルゴリズムが安定であることを当然望んでいる.どの状況が安定していますか?シーケンスは、{08 16 21 25 38 49,6225*}赤色が秩序化されていると仮定する.low = 0, high = 6 ,mid = 3.すなわちa[mid]==temp(25*)、temp>=a[mid]を用いる場合low=mid+1;このときtempの挿入位置は{38,49,62}のいくつかの位置にあるに違いない.これは25*が必ず25の右側に現れることを保証し、ソートの安定性を保証する.逆に25の左側に現れ、ソートが不安定です.君はこの理屈だと思うか.この一節は自分で考えたもので,正しいかどうか分からないが,君たちは自分で数えてみなさい.あと二分検索が終わると、tempの位置はhighではなくlowです.
二分検索が終了し,挿入位置i=5が見つかったが,このときに必要なのは[5,6]の要素を[6,7]に順次移動し,tempをa[low]jすなわちa[5]に置くことである.アルゴリズムが終了します.
相変わらずvs 2008 c++
1、Sort.h

#pragma once

typedef struct node{
	int key;
}DataType;

typedef struct {
	DataType *elem;
	int maxSize;
	int num;
}DataList;

class Sort
{
public:
	Sort(void);
	~Sort(void);
	void binaryInsertSort(DataList &L);//      

};

2、Sort.cpp

void Sort::binaryInsertSort( DataList &L )
{
	int i = 0, j = 0, low = 0, high = 0, mid = 0;
	DataType temp;

	for(i = 1; i < L.num; i++)
	{
		if(L.elem[i].key < L.elem[i-1].key)
		{
			low = 0;
			high = i-1;
			temp = L.elem[i];

			while(low <= high)
			{
				mid = (low + high)/2;
				if(temp.key < L.elem[mid].key)
					high = mid - 1;
				else
					low = mid + 1;
			}
			
			for(j = i-1; j >= low; j--)
			{
				L.elem[j+1] = L.elem[j];
			}

			L.elem[low] = temp;
		}
	}
}

前回の直接挿入ソートでは、Lを初期化したり、Lの要素を表示したりする方法はありません.ここでは、後続は後述しない.

void initDataList(DataList &L)
{
	L.maxSize = 20;
	
	L.elem = new DataType[L.maxSize];
	if(NULL == L.elem)
	{
		cout << "      
";
		exit(1);
	}
	
	srand(time_t(NULL));
	L.num = 10;
	for(int i = 0; i < 10; i++)
	{
		L.elem[i].key = rand()%100;
	}

}

void display(const DataList &L)
{
	cout << "DataList    
";

	for(int i = 0; i < L.num; i++)
	{
		cout << L.elem[i].key << " ";
	}

	cout << endl;
}

分析:
最良の場合、n-1回を比較するだけで、移動する必要はありません.
最悪の場合はリスト逆順で,二分ルックアップ法でNlogNを比較する.移動回数O(n^2).
時間複雑度O(Nlogn).
安定した順序付け.
補助空間O(1).