並べ替え【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番目と秩序領域を小さい順から大きい順に比較する.
無秩序領域の最後の挿入まで、秩序領域を挿入します.
次に、ソートを直接挿入するコードを書きます.
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;
}