白话经典算法系列之二 直接插入排序

微分 2015-01-08

插入排序的思想如下:

1. 从第一个元素开始,认为他是有序的。

2. 取出下一个元素, 在已经排序的元素序列中从后往前扫描。

3. 如果发现已排序的中的某个元素大于新元素,那么就将该有序元素移到相爱一个位置。

4. 重复步骤3直到找到一个已排序的元素小于等于新元素。

5. 将新元素插入该位置。

6. 重复步骤2-5.

如下是代码:

static void Main(string[] args)
{
    int[] array = { 49, 38, 65, 97, 76, 13, 27,0,34 };
    InsertionSort(array);
    foreach (int num in array)
    {
        Console.Write(num + " ,");
    }
    Console.WriteLine();

    Console.Read();
}

public static void InsertionSort(int[] data)
{
    int count = data.Length;
    for (int i = 1; i < count; i++)
    {
        int t = data[i];
        int j = i;//这是后面无须数列的开始,下面的while即是从临界点往前扫描
        while (j > 0 && data[j - 1] > t)//内部while,每循环一次就完成一次移动
        {
            data[j] = data[j - 1];//只要前一个数大于目标数,就要让出位置
            --j;
        }
        data[j] = t;
    }
}

相关推荐