ソートアルゴリズム:5.挿入ソートの直接挿入ソート(二分法を含む)


挿入ソート
すべてのレコードの挿入が完了するまで、テーブルの適切な位置.2種類の挿入ソート方法を紹介する:(1)直接挿入ソート(二分挿入ソートを含む)(2)ヒルソート
ソート1を直接挿入する.配列R[0..n-1]にソートするレコードが格納されているものとする.並べ替えプロセスのある中間時点において、Rは、2つのサブ区間R[0..i-1]およびR[i..n-1]に分割され、ここで、
 3.直接挿入ソートの基本動作は、現在の無秩序領域の1番目のレコードR[i]を秩序に挿入することである
領域R[0..i-1]の適切な位置で、R[0..i]を新しい秩序領域に変更する.      4.直接挿入ソートは、順序付け領域を1レコードずつ増加させるため、増分法と呼ばれることが多い.

//      
void insertsort(int a[], int n)
{
	int i, j;
	int temp;
	for (i = 1; i < n; ++i)
	{
		temp = a[i];
		j = i -1;
		while (j >= 0 && temp < a[j])
		{
			a[j + 1] = a[j];
			j--;

		}
		a[j + 1] = temp;

	}
}

//    
void insertsort1(int  a[], int n)
{
	int i, j, low, high, mid;
	int temp;
	for (int i = 1; i < n; ++i)
	{
		temp = a[i];
		low = 0;
		high = i - 1;
		//          
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (temp < a[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
		//        
		for (j = i -1; j >= high + 1; j--)
			a[j + 1] = a[j];
		a[high + 1] = temp;
	}

}
void main()
{
	int a[] = { 15,2,0,9,4,5,6,7 };
	int n = sizeof(a) / sizeof(int);

	//insertsort(a, n);
	insertsort1(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << 1 / 2 << endl;

}