C# 挿入ソート

C# 、挿入ソート

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class InsertSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            InsertSort(a);  
            return a;  
        }  
        private static void InsertSort(int[] myArray)  
        {  
           int i, j,temp;            for (i = 1; i < myArray.Length; i++)  
            {  
                temp = myArray[i];//保存当前数据，当前数据即待插入的数据          
                //将数组标号i及i之前的元素，排成递增序列  
                for (j = i - 1; j >= 0 && myArray[j] >temp; j--)  
                {  
                    myArray[j + 1] = myArray[j];                 
                }  
                myArray[j + 1] = temp;  
            }  
     }  
  
    }  
}

例1:

キーワード列 T= (13, 6, 3, 31, 9, 27, 5, 11) 直接挿入ソートの途中処理シーケンスを記述してください。

【13】、6、3、31、9、27、5、11

【6、13】、3、31、9、27、5、11

【3、6、13】、31、 9、27、5、11

【3、6、13、31】、9、27、5、11

【3、6、9、13、31】、27、5、11

【3、 6、9、13、27、31】、5、11

【3、5、6、9、13、27、31】、11

【3、5、6、9、11、13、27、 31】

小さなメモ: それぞれの小さなループは、配列 0 から i までの要素の順序を並べ替えるだけです (バブリングと同様)。最悪の場合、2 番目の要素を挿入するときは最初の要素を考慮する必要があり、N 番目の要素を挿入するときは最初の 2 つの要素を考慮する必要があります。 、最初の N 要素 - 1 要素を考慮する必要があります。したがって、最悪の場合の比較回数は 1 + 2 + 3 + ... + (N - 1) となり、等差数列を合計すると N^2 / 2 となるため、最悪の場合の計算量は場合は O (N^2) です。

最良の場合、配列はすでに順序付けされており、要素が挿入されるたびに検査する必要があるのは前の要素だけです。したがって、最良の場合、挿入ソートの時間計算量は O(N) になります。

挿入ソートのスペース複雑さは O(1) です。挿入ソート中は、「取り出した」要素を格納するために余分なスペースを使用するだけでよいため、挿入ソートにはソートを実行するための追加スペースのみが必要です。

スペースの複雑さは、アルゴリズムが動作中に一時的に占有するストレージスペースの量の尺度です。

配列は内部でソートされているので、後続の部分を少しずつ順番に比較して移動させることで相対的な順序を変えずに済むので、挿入ソートは安定したソートアルゴリズムです。

上記は C# 挿入ソートの内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) に注目してください。