C++折半挿入ソートを実現

「C++インプリメンテーションダイレクト挿入ソート」では、挿入ソートの基本的な操作が1つの順序テーブルで検索および挿入されるため、この「検索」操作は「折半検索」で実現でき、これによって行われる挿入ソートは折半挿入ソートと呼ばれる
次のようになります.

#include<iostream>
using namespace std;

#define SIZE_A 9

int main(){

	void myshow(int*  p,int length);//      
	int list[SIZE_A]={-1,49,38,65,97,76,13,27,49};
	cout<<"   ："<<endl;
	myshow(list,SIZE_A);
	//      ，  【0】    ，           【1】～【length-1】
	for(int i=2;i<sizeof(list)/sizeof(int);i++){
		list[0]=list[i];//           【0】
		
		int low=1;
		int high=i-1;
		
		while(low<=high){// 【low】 【high】            
			int middle=(low+high)/2;//  
			if(list[0]<list[middle]){//        
				high=middle-1;

			}else{//        
				low=middle+1;
			}

		}//while
		for(int j=i-1;j>=high+1;j--){//    
			list[j+1]=list[j];
		}
		list[high+1]=list[0];//  

	}//for
	
	cout<<"   ："<<endl;
	myshow(list,SIZE_A);
	return 0;

}
/*
description:
              。
parameter：
int* p:            
int length:      
*/
void myshow(int*  p,int length){
	for(int i=0;i<length;i++){
		cout<<*(p+i)<<"\t";
	}
	cout<<endl;
}

実行結果:
時間と空間の複雑さの分析
スペースの複雑さ:
上記の実装から、折りたたみ挿入ソートに必要な補助空間は、直接挿入ソートと同じである(いずれも補助空間、すなわち哨兵が必要である).
時間の複雑さ:
半角挿入ソートは、キーワードの比較回数を減らすだけで、記録された移動回数は変わりません.したがって,折半挿入ソートの時間的複雑さはO(n*n)のままである.