插入排序:直接插入排序希爾排序 - elvinle－IT工程師數位筆記本

文章出處

一、直接插入排序

1. 思想

直接排序法, 可以分為兩個部分, 一部分是有序的, 一部分是無序的.

從這個圖上, 應該是能看清楚直接插入排序的思想了.

將無序部分的第一個與有序部分進行比較.

從有序部分的后面向前面比較, 然后不斷地挪動有序部分的數據的位置

static void InsertSort(List<int> list)
{
　　 //從第二個數開始循環, 循環n-1次
    for (int i = 1; i < list.Count; i++)
    {
　　　　 //將待排序的數拿出來, 以便后面挪位子
        int temp = list[i];
　　　　 //j就是最后確定的那個最大/最小數的下標
        int j = i; 
        while (j >= 1 && temp < list[j - 1])
        {
　　　　　　 //將滿足條件的數據向后移動一位, 騰空位, 為插入挪位子
            list[j] = list[j - 1];
            j--;
        }
        list[j] = temp;
    }
}

2. 復雜度

直接插入排序的最好情況下, 時間復雜度為O(n), 最壞情況下, 復雜度為O(n²);

證明見:

插入排序及其復雜度分析

3. 直接插入排序vs快速排序

從上面的代碼來看, 直接插入排序需要不斷地挪數據. 如果碰到連續整數, 那么挪動的數據就多了. 針對這種問題, 是否可以改進一下直接插入排序?

在比較的時候, 我是否可以跳著比較?

二、希爾排序

1. 思想

在比較的時候, 引入縮小增量比較的方式.

第一步. 使增量d=count/2, 將每隔d個數看成是一組無序的數, 然后對這組無序的數進行插入排序

第二步. 使增量d=d/2, 和第一步執行相同的操作, 一直到d=1的時候

代碼:

static void ShellSort(List<int> list)
{
    int step = list.Count / 2;
    while (step >= 1)
    {
        for (int i = step; i < list.Count; i++)
        {
            var temp = list[i];
            int j = i;
            while (j >= step && temp < list[j - step])
            {
                list[j] = list[j - step];
                j -= step;
            }
            list[j] = temp;
        }
        step = step / 2;
    }
}

希爾排序與直接插入排序, 中間部分的代碼基本一直, 不同的只是維度, 直接插入排序的維度是固定的1,

而希爾排序的維度是變化的. 從代碼上看, 其實還是蠻簡單的, 就拿著直接插入排序改吧改吧就成了.

2. 復雜度

希爾排序的時間復雜度, 和直接插入排序的最好&最壞時間復雜度居然是一樣的, 同志們, 能相信么.

三、直接插入排序 vs 希爾排序

既然說希爾排序是直接插入排序的改進版, 那么他們究竟誰更厲害些呢? 會不會越改越差了?

static void Test()
{
    //五次比較
    for (int i = 1; i <= 5; i++)
    {
        List<int> list = new List<int>();
        List<int> listA = new List<int>();
        //插入2k個隨機數到數組中
        for (int j = 0; j < 10000; j++)
        {
            Thread.Sleep(1);
            list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));
        }

        listA.AddRange(list);
        Console.WriteLine("\n第" + i + "次比較：{0}...", string.Join(",", list.Take(10)));

        Stopwatch watch = new Stopwatch();
        watch.Start();
        InsertSort(list);
        watch.Stop();
        Console.WriteLine("\n直接插入排序耗費時間：" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + string.Join(",", list.Take(10).ToList()));

        watch.Restart();
        ShellSort(listA);
        watch.Stop();
        Console.WriteLine("\n希爾排序耗費時間：" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + string.Join(",", listA.Take(10).ToList()));
    }
}