在有序序列中插入一个元素，保持序列有序，有序长度不断增加。

直接插入排序

直接插入排序：采用顺序查找法查找插入位置。

  • 原始数据越接近有序，排序速度越快。
  • 时间复杂度=O(n2)，空间复杂度=O(1)。稳定排序。

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        insert_sort(arr);
        // insert_sort1(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    // for + while 实现
    private static void insert_sort(int[] arr)
    {
        int length = arr.Length;
        // 以第一个元素为基准元素，下标为0
        // 从第二个元素开始进行直接插入排序，下标为1
        for (int i = 1; i < length; i++)
        {
            // 临时保存需要进行插入的元素
            int insert_elem = arr[i];
            // 记录当前需要进行插入排序的元素的位置
            int position = i;
            // 从 position 向前遍历，大于插入元素则后移，直至找到目标元素插入位置
            while (position > 0 && arr[position - 1] > insert_elem)
            {
                // 后移
                arr[position] = arr[position - 1];
                // 向前遍历
                position--;
            }
            if (position != i)
            {
                // 将目标元素插入到指定位置
                arr[position] = insert_elem;
            }
        }
    }
    
    // 两个 for 循环
    private static void insert_sort1(int[] arr)
    {
        int i, j;
        int length = arr.Length;
        for (i = 1; i < length; i++)
        {
            // 临时存储目标元素
            int temp = arr[i];
            // 从目标元素的前一个元素开始向前遍历
            // 直到遍历下标 <= 0，并且遍历元素大于目标元素时
            // 将大于目标元素的元素向后移
            for (j = i - 1; j >= 0 && arr[j] > temp; j--)
            {
                arr[j + 1] = arr[j];
            }
            // 将目标元素插入到指定位置
            arr[j + 1] = temp;
        }
    }
}

输出：

未排序前的数组：
5 7 3 8 6 9
排序后的数组：
3 5 6 7 8 9

折半插入排序

折半插入排序：减少比较次数，但没有减少移动次数。

  • 平均性能优于直接插入排序。

  • 时间复杂度=O(n2)，空间复杂度=O(1)。稳定排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        half_sort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static void half_sort(int[] arr)
    {
        int temp, low, high, mid;
        for (int i = 1; i < arr.Length; i++)
        {
            low = 0; // 左边第一个元素位置
            high = i - 1; // 待排元素的前一个元素
            temp = arr[i]; // 待排元素临时存储
            while (low <= high) // 当 high < low 时退出循环
            {
                mid = low + (high - low) / 2; // 取排好数组中的中间元素位置
                if (arr[mid] > temp)
                {
                    // 如果中间元素大于待排元素，则high向前移动，继续比较
                    high = mid - 1;
                }
                else
                {
                    // 如果中间元素小于待排元素，则low向后移动，继续比较
                    low = mid + 1;
                }
            }
            for (int j = i - 1; j >= high + 1; j--)
            {
                arr[j + 1] = arr[j];
            }
            arr[high + 1] = temp;
        }
    }
}

输出：

未排序前的数组：
5 7 3 8 6 9
排序后的数组：
3 5 6 7 8 9

希尔排序

希尔排序：先将整个代排序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

  • 缩小增量，多遍插入排序。

  • 时间复杂度=O(n1.25~1.6n1.25)，空间复杂度=O(1)，不稳定排序。不适合在链式存储结构上实现。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        shell_sort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
    
    private static void shell_sort(int[] arr)
    {
        int length = arr.Length;
        int interval = 1; // 初始化间隔为1
        // 计算最大间隔
        while (interval < length / 3)
        {
            interval = interval * 3 + 1;
        }
        // 根据间隔数，不断划分子序列，并对各子序列排序
        while (interval > 0)
        {
            int i, j, temp;
            for (i = interval; i < length; i++)
            {
                temp = arr[i];
                j = i;
                while (j > interval - 1 && arr[j - interval] >= temp)
                {
                    arr[j] = arr[j - interval];
                    j -= interval;
                }
                if (j != i)
                {
                    arr[j] = temp;
                }
            }
            // 计算新间隔
            interval = (interval - 1) / 3;
        }
    }
}

输出：

未排序前的数组：
5 7 3 8 6 9
排序后的数组：
3 5 6 7 8 9