データ構造_並べ替えアルゴリズム(並べ替えの挿入)

ソートアルゴリズム
並べ替えの挿入
基本的な考え:挿入順序は、並べ替えられたレコードを、並べ替えられたレコードのすべてが挿入されるまで、そのキーワードのサイズに従って、並べ替えられたレコードのセットの記録の適切な位置に挿入します.
例えば、トランプをして、カードをつかむ時に握った札がきちんと並べられていることを保証します.一枚の札をつかむごとに適当な位置に挿入します.牌をつかむまでに、秩序正しい順序が取れます.
分類:異なる方法を選択して、並べられた記録の中で挿入位置を探すことができます.検索方法によっては、挿入順序は、直接挿入順序、折半検索順序、およびヒル順序に分けられます.
1.直接並べ替えを挿入する

直接的に並べ替えを挿入するのは簡単な並べ替えアルゴリズムであり、基本的な動作は、順序が整った順序テーブルに記録を挿入する

である.

解析:時間複雑度O(n^2)、空間複雑度O(1)、アルゴリズム安定

#include 

//       
void InsertSort(int * S, int n)
{
	int i, j, temp;
	
	for(i = 1; i < n; i++)  //        
	{
		if(S[i] < S[i-1])  //                     
		{
			temp = S[i];  //               
			for(j = i-1; j>=0 && S[j]>temp; j--)
			{
				S[j+1] = S[j];  //               
			} 
			S[j+1] = temp;  //               
		}
	}
}

int main()
{
	int S[8] = {49, 38, 65, 97, 76, 13, 27, 49};
	int i, j;
	
	printf("      ：");
	for(i = 0; i < 8; i++)
	{
		printf("%d ", S[i]);
	}
	printf("
");
	
	InsertSort(S, 8);  //       
	
	printf("           ：");
	for(j = 0; j < 8; j++)
	{
		printf("%d ",S[j]); 
	}
	printf("
");

	return 0;
 } 

2.半値の挿入順序

の折半挿入順序は、直接挿入順序の改善であり、並べ替え中に、半角検索の方法(直接挿入順序検索方法)によって記録の適切な位置を見つける

である.

分析:平均性能は直接挿入順序より優れていますが、半値挿入順序は比較回数を減らしただけで、並べ替え記録移動回数は直接挿入順序と同じです.時間複雑度O(n^2)、空間複雑度O(1)、アルゴリズム安定

#include 

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

int main()
{
	int S[8] = {49, 38, 65, 97, 76, 13, 27, 49};
	int i, j;
	
	printf("      ：");
	for(i = 0; i < 8; i++)
	{
		printf("%d ",S[i]); 
	}
	printf("
");
	
	BInsertSort(S, 8);   //       
	
	printf("           ：");
	for(j = 0; j < 8; j++)
	{
		printf("%d ",S[j]); 
	}
	printf("
");
	
	return 0;
 } 

3.ヒルの並べ替え

ヒルの順序付けは、「縮小増分順序付け」とも呼ばれ、ヒルの順序付けは依然として直接的な挿入順序の改善(記録数とシーケンスの基本的な順序を減らす2つの態様)であり、順序付け中にパケットを使用する方法である.まず、順序付けされた記録シーケンス全体をいくつかのグループに分割し、直接的な挿入順序に参加するデータ量を減少させ、それぞれのパケットに直接挿入順序付けを行い、その後、各グループのデータ量を増加させ、再グループ化する.このように何回かのパケットを並べ替えた後、シーケンス全体に「基本的な順序」が記録されている場合、全体の記録を直接挿入して並べ替えます.

解析:時間複雑度O(nlogn)、空間複雑度O(1)、アルゴリズム不安定性

#include 

void ShellInsert(int * S, int dk, int n)
{
	int i, j, temp;
	for(i = dk; i < n; i++)  //        
	{
		if(S[i] < S[i-dk])
		{
			temp = S[i];
			for(j = i-dk; j>=0 && S[j]>temp; j = j - dk)
			{
				S[j+dk] = S[j];
			}
			S[j+dk] = temp;
		}
	}
}

void ShellSort(int * S, int * dt, int t, int n)
{
	int k;
	for(k = 0; k < t; k++)  //              k    
	{
		ShellInsert(S, dt[k], n);  //               
	 } 
}
	
int main()
{
	int S[10] = {49, 38, 65, 97, 76, 13, 27, 49,55, 4};
	int dt[3] = {5, 3, 1};  //    ，5，3，1 
	int i, j; 
	
	printf("      ：");
	for(i = 0; i < 10; i++)
	{
		printf("%d ",S[i]); 
	}
	printf("
");
	
	ShellSort(S, dt, 3, 10);  //3   ,10           
	
	printf("         ：");
	for(j = 0; j < 10; j++)
	{
		printf("%d ",S[j]); 
	}
	printf("
");
	
	return 0;
 }