排序算法（二）插入排序和希尔排序

• 一、插入排序
• • 1.原理与分析
  • 2.代码实现（C#）
• 二、希尔排序
• • 1.原理与分析
  • 2.代码实现（C#）

先看图：

插入排序是将序列分为排序区和未排序区，将未排序区的数值依次从后往前与排序区数值进行比较，选择到合适的位置插入。

public static void InsertSort(int[] array)
{
	//未排序区索引
	int index;
	//记录待插入的值
	int temp;
    for(index = 1; index < array.Length; index++)
    {
    	int insertPos = index - 1;
    	temp = array[index];
    	while(insertPos >= 0 && array[insertPos] > temp)
    	{
    		array[insertPos + 1] = array[insertPos];
    		insertPos--;
    	}
    	array[insertPos + 1] = temp;
    }
}

先看图：

希尔排序是对插入排序的一种优化，在插入排序的基础上加了步长的概念，在面对较大数据量时，能有效提高插入排序的效率。

public static void ShellSort(int[] array)
{
	int step = array.Length / 2;
    int index;
    int temp;

    while (step >= 1)
    {
    	for (index = 1; index < array.Length; index++)
        {
        	temp = array[index];
            int insertPos = index - step;

            while (insertPos >= 0 && array[insertPos] > temp)
            {
            	array[insertPos + step] = array[insertPos];
                insertPos -= step;
            }

            array[insertPos + step] = temp;
        }

        step /= 2;
     }
}