算法 - 排序 - 插入排序 (Insertion Sort)

傳回分類：全部文章 >> 基礎知識

傳回上級：算法 - 查找與排序 (Searching and Sorting)

本文将用C++實作插入排序算法。

在檢視本文之前，需要一些程式語言的基礎。

常用插入排序：

直接插入排序 (Direct Insertion Sort) ；
折半插入排序 (Binary Insertion Sort) ，也稱二分插入排序；
希爾排序 (Shell Sort) ，也稱縮小增量排序 (Diminishing Increment Sort) 。

所有排序方法中，統一使用如下庫與結構：

// Author: https://blog.csdn.net/DarkRabbit
// Sorted Dependency

#pragma once

#include <algorithm>
#include <vector>
#include <stack>

template<typename T>
struct MyItem
{
    int key;
    T data;

    MyItem(){ key = -1; }
    MyItem(const int& k) : key(k){ }
    MyItem(const int& k, const T& d) : key(k), data(d){ }
};

資料表統一使用了

std::vector<MyItem<T>>

，如果你使用靜态數組

MyItem<T>[]

或指針數組

MyItem<T>*

，那麼還要傳入元素數量

size

。

示例所用資料：

元素數量為 size = 15 ；
關鍵字為 key = { 123, 122, 565, 22, 3, 64, 73, 44, 287, 6, 9, 83, 25, 42, 13 } 。

文章目錄

算法 - 排序 - 插入排序 (Insertion Sort)
- 1 插入排序簡述 (Introduction)
- 2 性能分析 (Performance Analysis)
- 3 直接插入排序C++代碼 (Direct Insertion Sort C++ Code)
- 4 折半插入排序C++代碼 (Binary Insertion Sort C++ Code)
- 5 希爾排序C++代碼 (Shell Sort C++ Code)

1 插入排序簡述 (Introduction)

插入排序基本思想：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

常用插入排序：

直接插入排序 (Direct Insertion Sort) ；
折半插入排序 (Binary Insertion Sort) ，又稱二分插入排序；
希爾排序 (Shell Sort) ，又稱縮小增量排序 (Diminishing Increment Sort) 。

折半插入排序與直接插入排序隻是在尋找位置有所不同，這是因為前面的元素已經排過序了。

折半插入排序再插入第 i 個元素時，需要經過 ⌈ log ⁡ 2 i ⌉ + 1 \lceil \log_2i \rceil + 1 ⌈log2i⌉+1 次關鍵字比較。

直接插入與折半插入過程：

插入到第 i 個關鍵字時，逆向依次與已經排過序的關鍵字比較：
- 找到比它小的關鍵字的位置 ilow ，關鍵字位置在 ilow 到 i-1 之間的元素整體右移 1 位，然後将它插入到 ilow+1；
- 超出表的範圍，則它最小，它之前元素整體右移 1 位，将它插入到0位置。

希爾排序過程：定義一個增量

gap

将資料表分成長度為 gap 的幾個塊；
對每個塊的對應下标元素（間隔是 gap ）組成的子表進行直接插入排序；
利用公式改變 gap （希爾增量是減半，Hibbard增量為 {2k-1, 2k-1-1, …, 7, 3, 1}）；
循環過程，直到不可再分。

具體插入過程：

key = { 123, 122, 565, 22, 3, 64, 73, 44, 287, 6, 9, 83, 25, 42, 13 }

直接插入排序與折半插入排序：
    插入開始位置 i = 1 , 即 key_1 = 122
        它之前的所有元素為 { 123 } ，
        比較它們，122 < 123 ，則 { 123 } 右移 1位，将 122 放在 key_0 的位置

    i = 2 ，即 key_2 = 565 不動
    i = 3 ，即 key_3 = 22
        它之前的所有元素為 { 122, 123, 565 }
        比較它們，超出表的範圍
        則它最小，将它們右移一位，然後将 22 放在 key_0 的位置
        現在表 { 22, 122, 123, 565 }
    重複過程

詳細過程：
 1: 122 123 565  22   3  64  73  44 287   6   9  83  25  42  13
 2: 122 123 565  22   3  64  73  44 287   6   9  83  25  42  13
 3:  22 122 123 565   3  64  73  44 287   6   9  83  25  42  13
 4:   3  22 122 123 565  64  73  44 287   6   9  83  25  42  13
 5:   3  22  64 122 123 565  73  44 287   6   9  83  25  42  13
 6:   3  22  64  73 122 123 565  44 287   6   9  83  25  42  13
 7:   3  22  44  64  73 122 123 565 287   6   9  83  25  42  13
 8:   3  22  44  64  73 122 123 287 565   6   9  83  25  42  13
 9:   3   6  22  44  64  73 122 123 287 565   9  83  25  42  13
10:   3   6   9  22  44  64  73 122 123 287 565  83  25  42  13
11:   3   6   9  22  44  64  73  83 122 123 287 565  25  42  13
12:   3   6   9  22  25  44  64  73  83 122 123 287 565  42  13
13:   3   6   9  22  25  42  44  64  73  83 122 123 287 565  13
14:   3   6   9  13  22  25  42  44  64  73  83 122 123 287 565

key = { 123, 122, 565, 22, 3, 64, 73, 44, 287, 6, 9, 83, 25, 42, 13 }

希爾排序詳細過程：

1: gap=7
    ( 1):  44 122 565  22   3  64  73 123 287   6   9  83  25  42  13
    ( 2):  44 122 565  22   3  64  73 123 287   6   9  83  25  42  13
    ( 3):  44 122   6  22   3  64  73 123 287 565   9  83  25  42  13
    ( 4):  44 122   6   9   3  64  73 123 287 565  22  83  25  42  13
    ( 5):  44 122   6   9   3  64  73 123 287 565  22  83  25  42  13
    ( 6):  44 122   6   9   3  25  73 123 287 565  22  83  64  42  13
    ( 7):  44 122   6   9   3  25  42 123 287 565  22  83  64  73  13
    ( 8):  13 122   6   9   3  25  42  44 287 565  22  83  64  73 123
2: gap=3
    ( 9):   9 122   6  13   3  25  42  44 287 565  22  83  64  73 123
    (10):   9   3   6  13 122  25  42  44 287 565  22  83  64  73 123
    (11):   9   3   6  13 122  25  42  44 287 565  22  83  64  73 123
    (12):   9   3   6  13 122  25  42  44 287 565  22  83  64  73 123
    (13):   9   3   6  13  44  25  42 122 287 565  22  83  64  73 123
    (14):   9   3   6  13  44  25  42 122 287 565  22  83  64  73 123
    (15):   9   3   6  13  44  25  42 122 287 565  22  83  64  73 123
    (16):   9   3   6  13  22  25  42  44 287 565 122  83  64  73 123
    (17):   9   3   6  13  22  25  42  44  83 565 122 287  64  73 123
    (18):   9   3   6  13  22  25  42  44  83  64 122 287 565  73 123
    (19):   9   3   6  13  22  25  42  44  83  64  73 287 565 122 123
    (20):   9   3   6  13  22  25  42  44  83  64  73 123 565 122 287
3: gap=1
    (21):   3   9   6  13  22  25  42  44  83  64  73 123 565 122 287
    (22):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (23):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (24):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (25):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (26):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (27):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (28):   3   6   9  13  22  25  42  44  83  64  73 123 565 122 287
    (29):   3   6   9  13  22  25  42  44  64  83  73 123 565 122 287
    (30):   3   6   9  13  22  25  42  44  64  73  83 123 565 122 287
    (31):   3   6   9  13  22  25  42  44  64  73  83 123 565 122 287
    (32):   3   6   9  13  22  25  42  44  64  73  83 123 565 122 287
    (33):   3   6   9  13  22  25  42  44  64  73  83 122 123 565 287
    (34):   3   6   9  13  22  25  42  44  64  73  83 122 123 287 565

2 性能分析 (Performance Analysis)

排序方法	最好時間	最差時間	平均時間	輔助空間	穩定性
直接插入排序	O(n)	O(n2)	O(n2)	O(1)	穩定
折半插入排序	O(n log2n)	O(n2)	O(n2)	O(1)	穩定
希爾排序	O(n log2n)	O(n2)	與增量算法有關	O(1)	不穩定

注意1：希爾排序時間複雜度和增量算法的選擇有關，标準希爾增量是 O(n2)，Hibbard增量時間複雜度 O(n1.5) 。

注意2：希爾增量的計算是一個複雜的問題，目前希爾增量的常用算法時間複雜度多為 O(n1.3) 到 O(n1.5) 。

3 直接插入排序C++代碼 (Direct Insertion Sort C++ Code)

// Author: https://blog.csdn.net/DarkRabbit
// Direct Insertion Sort

template<typename T>
void DirectSort(std::vector<MyItem<T>>& list, 
                const int& start, 
                const int& end)
{
    for (int i = start + 1; i <= end; i++)
    {
        for (int j = i; 
             j > start && list[j].key < list[j - 1].key; 
             j--) // 比較
        {
            std::swap(list[j], list[j - 1]); // 左移
        }
    }
}

template<typename T>
void DirectSort(std::vector<MyItem<T>>& list)
{
    DirectSort(list, 0, list.size() - 1);
}

4 折半插入排序C++代碼 (Binary Insertion Sort C++ Code)

// Author: https://blog.csdn.net/DarkRabbit
// Binary Insertion Sort
template<typename T>
void BinarySort(std::vector<MyItem<T>>& list)
{
    int left;
    int right;
    int mid;
    for (int i = 1; i < list.size(); i++)
    {
        left = 0;
        right = i - 1;
        while (left <= right) // 二分找位置
        {
            mid = (left + right) / 2;

            if (list[i].key < list[mid].key)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }

        for (int j = i - 1; j >= left; j--) // 右移
        {
            std::swap(list[j + 1], list[j]);
        }
    }
}

5 希爾排序C++代碼 (Shell Sort C++ Code)

// Author: https://blog.csdn.net/DarkRabbit
// Shell Sort
template<typename T>
void ShellSort(std::vector<MyItem<T>>& list, int gap)
{
    if (list.empty())
    {
        return;
    }

    if (gap < 0 || gap >= list.size())
    {
        gap = list.size() / 2;
    }

    for (gap; gap != 0; gap /= 2) // 标準希爾增量
    {
        // 直接插入排序
        for (int i = gap; i < list.size(); i++)
        {
            for (int j = i; 
                 j >= gap && list[j].key < list[j - gap].key; 
                 j -= gap)
            {
                std::swap(list[j], list[j - gap]);
            }
        }
    }
}

template<typename T>
void ShellSort(std::vector<MyItem<T>>& list)
{
    ShellSort(list, list.size() / 2);
}

算法 - 排序 - 插入排序 (Insertion Sort)算法 - 排序 - 插入排序 (Insertion Sort)

算法 - 排序 - 插入排序 (Insertion Sort)

文章目錄

1 插入排序簡述 (Introduction)

2 性能分析 (Performance Analysis)

3 直接插入排序C++代碼 (Direct Insertion Sort C++ Code)

4 折半插入排序C++代碼 (Binary Insertion Sort C++ Code)

5 希爾排序C++代碼 (Shell Sort C++ Code)

繼續閱讀

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

shell排序基本思想及其複雜度分析

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希