アルゴリズムシリーズ——挿入アルゴリズム
3060 ワード
一、順序付け(Insertion Sort)を直接挿入する基本思想は、順序付けされるレコードを1つずつ、前に並べられたサブシーケンスの適切な位置にキーワードサイズで挿入し、すべてのレコード挿入が完了するまで
ここで注意すべき点は、赤い部分のフォントがカードの挿入方法に類比できる点が異なる点です.2つの隣接点に数値を挿入した後、挿入点の後ろのデータは一度に1単位後ろに移動する必要があります.
二、アルゴリズムの説明
例えば1 5 4 7 8を直接挿入ソートする
1.最初の要素から、この要素はすでに並べ替えられていると考えられる
⒉次の要素を取り出し、並べ替えられた要素シーケンスで後から前へスキャンします.
3.エレメント(並べ替えられた)が新しいエレメントより大きい場合は、エレメントを次の位置に移動します.
⒋並べ替えられた要素が新しい要素より小さいか等しい場所が見つかるまで、手順3を繰り返します.
⒌新しい要素を次の場所に挿入
⒍手順2~5を繰り返す
三、コード説明
ソート法
さいさじかんぶんせき
へいきんじかんふくざつさ
あんていど
くうかんふくざつさ
バブルソート
O(n2)
O(n2)
あんてい
O(1)
クイックソート
O(n2)
O(n*log2n)
ふあんてい
O(log2n)~O(n)
ソートの選択
O(n2)
O(n2)
あんてい
O(1)
ツリーのソート
O(n2)
O(n*log2n)
一つではない
O(n)
ソートの挿入
O(n2)
O(n2)
あんてい
O(1)
ヒープのソート
O(n*log2n)
O(n*log2n)
ふあんてい
O(1)
ヒルソート
O
O
ふあんてい
O(1)
一般的なアルゴリズム時間複雑度:O(1):アルゴリズムの実行時間が定数O(n):このアルゴリズムが線形アルゴリズムO(O(n 3):2つのn次行列の乗算O(2 n):n個の要素の集合を持つすべてのサブセットを求めるアルゴリズムO(n!):N個の元素の全配列のアルゴリズムを持つことを求めます
優
O(1)2n)時間的複雑度は、定数次O(1)、対数次O(log 2 n)、線形次O(n)、線形対数次O(nlog 2 n)、平方次O(n 2)、立方次O(n 3)、・・・k次方次O(nk)、指数次O(2 n)の順に数値的にインクリメントされる.
ここで注意すべき点は、赤い部分のフォントがカードの挿入方法に類比できる点が異なる点です.2つの隣接点に数値を挿入した後、挿入点の後ろのデータは一度に1単位後ろに移動する必要があります.
二、アルゴリズムの説明
例えば1 5 4 7 8を直接挿入ソートする
1.最初の要素から、この要素はすでに並べ替えられていると考えられる
⒉次の要素を取り出し、並べ替えられた要素シーケンスで後から前へスキャンします.
3.エレメント(並べ替えられた)が新しいエレメントより大きい場合は、エレメントを次の位置に移動します.
⒋並べ替えられた要素が新しい要素より小さいか等しい場所が見つかるまで、手順3を繰り返します.
⒌新しい要素を次の場所に挿入
⒍手順2~5を繰り返す
三、コード説明
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace InsertSort
{
class Program
{
static void Main(string[] args)
{
Insertsort();
}
private static void Insertsort()
{
// ,
Console.WriteLine(" ");
int temp =0;
int[] arr = { 23, 44, 66, 76, 98, 11, 3, 9, 7 };
//
Console.WriteLine(" ");
foreach(int item in arr)
{
Console.Write(item+"\t");
}
Console.WriteLine();
for (int i = 1; i < arr.Length; i++)
{
for (int j = i; j > 0;j-- ) // : ,
{
if(arr[j]arr[j+1],
{
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
//
Console.WriteLine(" ");
PrintStr(arr);
}
Console.ReadKey();
}
private static void PrintStr(IEnumerablearr)
{
foreach(int item in arr)
{
Console.Write(item + "\t");
}
Console.WriteLine();
}
}
}
ソート法
さいさじかんぶんせき
へいきんじかんふくざつさ
あんていど
くうかんふくざつさ
バブルソート
O(n2)
O(n2)
あんてい
O(1)
クイックソート
O(n2)
O(n*log2n)
ふあんてい
O(log2n)~O(n)
ソートの選択
O(n2)
O(n2)
あんてい
O(1)
ツリーのソート
O(n2)
O(n*log2n)
一つではない
O(n)
ソートの挿入
O(n2)
O(n2)
あんてい
O(1)
ヒープのソート
O(n*log2n)
O(n*log2n)
ふあんてい
O(1)
ヒルソート
O
O
ふあんてい
O(1)
一般的なアルゴリズム時間複雑度:O(1):アルゴリズムの実行時間が定数O(n):このアルゴリズムが線形アルゴリズムO(O(n 3):2つのn次行列の乗算O(2 n):n個の要素の集合を持つすべてのサブセットを求めるアルゴリズムO(n!):N個の元素の全配列のアルゴリズムを持つことを求めます
優
O(1)2n)