並べ替え【1】並べ替えを直接挿入

1740 ワード

直接ソートを挿入する前に、まずソートとは何ですか?
1、並べ替え:並べ替えとはファイルの記録を整理し、キーワードの増加(または減少)の順に並べ替えることである
2、安定ソートと不安定ソート:
Ki=Kjであり、並べ替え前のシーケンスのRiがRjより先であると仮定する.
並べ替え後のシーケンスにおいてRiがRjをリードしている場合,並べ替え方法は安定していると呼ぶ.
並べ替え後のシーケンスでRjがRiよりもリードしている場合,並べ替え方法は不安定であると呼ぶ.
3、アルゴリズムの複雑性:このアルゴリズムを実行する時のコンピュータに必要な資源の多少に体現する(時間と空間資源)
アルゴリズムの複雑さは時間と空間の複雑さに分けられる.
4、時間の複雑さ:簡単に言えばプログラムの循環実行の総回数である.アルゴリズムの時間的複雑さは関数です
アルゴリズムの実行時間を定量的に記述します.時間的複雑さは、O(f(n))という大きなO記号で表されることが多い.
5、補助空間:補助空間は並べ替えアルゴリズムを評価する重要な指標であり、補助空間は並べ替え待ちの資源を保管する以外、
アルゴリズムを実行するために必要な他の記憶領域.
次に、直接挿入ソートについて説明します.
まず直接挿入ソートは、ヒルソートと同様に挿入ソートに属し、安定したソートでもあります.
時間複雑度:最良状況:O(n)最悪状況:O(n 2)平均状況:O(n 2);
空間複雑度:O(1)
では、ソートを直接挿入する主な考え方は何でしょうか.
まず、1組のデータを秩序領域と無秩序領域に分け、1番目が秩序領域であり、残りが無秩序領域であると仮定し、次に無秩序領域の1番目と秩序領域を小さい順から大きい順に比較する.
無秩序領域の最後の挿入まで、秩序領域を挿入します.
次に、ソートを直接挿入するコードを書きます.
#include 

void InsertSort(int par_array[], int length)                  //             
{
	int i, j;
	int temp ;

	for (i = 1; i < length; i++)                          //    length-1  
	{
		temp = par_array[i];                          //                   
		for (j = i - 1; j >= 0; j--)
		{
			if (temp < par_array[j])              //                 
			{
				par_array[j + 1] = par_array[j]; //             
			}
			else
			{
				break;
			}
		}
		par_array[j + 1] = temp;                         //      
	}
}

int main1()
{
	int i;
	int a[] = {2, 3, 44, 2, 13, 55, 22, 88, 0, 7};
	int len = sizeof(a) / sizeof(a[0]);                       //      
	
	InsertSort(a, len);

	for (i = 0; i < len; i++)                                 //    
	{
		printf("%d ",a[i]);
	}
	printf("
"); return 0; }