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

插入排序的思想如下：

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;
    }
}

 

评论

2 楼 北极的。鱼 2015-04-02  

希尔排序类似直接插入

void shellsort(int a[], int n)  
{  
    int j, gap;  
      
    for (gap = n / 2; gap > 0; gap /= 2)  
        for (j = gap; j < n; j++)//从数组第gap个元素开始  
            if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序  
            {  
                int temp = a[j];  
                int k = j - gap;  
                while (k >= 0 && a[k] > temp)  
                {  
                    a[k + gap] = a[k];  
                    k -= gap;  
                }  
                a[k + gap] = temp;  
            }  
}  

1 楼 北极的。鱼 2015-01-10  

总结：
插入排序就是选择基准点，在有序数列中从后往前扫描。