插入排序

老码农空杯修行记 2020-09-07

276

算法原理

如同整理扑克，把拿起的扑克按照某个顺序拿在手里，接到一张，再接下一张时，判断已接到的牌是不是小于前面接到的，然后插入到合适位置。在序列中假定第一个元素为接到的第一张牌，然后从第二个元素开始接，然后找到合适位置插入，插入排序自左到右逐步有序，扑克接完，手中的扑克也就有序了。

要点

两层循环，外层循环 索引i 模拟揭牌的过程，内层循环 索引 j 用来管理手中已接到的牌，所以两个索引的取值范围

i ∈ [1, n)
j ∈ [0, i)

时间复杂度

n²

推演

待排序列

5, 8, 2, 9, 6

要求：从小到大，按照升序排列
确定外层索引范围 i ∈ [1, 5)
确定内层索引范围 j ∈ [0, i)
排序：新揭牌(紫色)、插入牌(黄色)、空位置(红色)、已排序(绿色)、未接牌(灰色)

接第二张牌：i=1，牌面 8；j ∈ [0，0]，第二张牌从右至左比较，前面只有一张牌，牌面 8 > 5, 无需交换，直接插入最右边

接第三张牌：i=2，牌面为 2；j ∈ [1，0]，手中的牌面大于刚接到的牌面，则先把手中的牌面向右边移动，空出一个插入的位置，以此类推

接第四张牌：i=3，牌面为 9；j ∈ [2，0]，新接的牌面大于手中最右边的牌面 8，所以直接插入到最右边

接第五张牌：i=4，牌面 6 ；j ∈ [3, 0)，手中的牌面大于刚接到的牌面，则先把手中的牌面向右边移动，空出一个插入的位置，以此类推

第5轮：i=5， 超出区间，即没有牌，到此手中的牌面已经排好序

代码演示

// 
// golang language
// 
func InsertSort(pokers []int) {
  size := len(pokers)


  // 外层循环控制揭牌
  for i:=1; i<size; i++ {
    // 新接的牌
    newPoker := pokers[i]


    j := i - 1
    
    // 内层循环控制手中已接的牌
    for j >= 0 {
       // 牌面大于手中最右边的直接结束插入
      if pokers[j] < newPoker {
        break
      }
     
      // 手中左边的扑克向右移动，流出空位置
      pokers[j+1] = pokers[j]
      j -= 1
    }
    // 空位置出插入新接的牌
    pokers[j+1] = newPoker
  }
}

# 
# python language
# 
def insert_sort(pokers):
    size = len(pokers)
    
    for i in range(size):
        # 新接的牌
        newPoker = pokers[i]
        j = i - 1
        
        #  遍历手中已接的牌
        while j >= 0:
            #  牌面比手中最右边的牌面大？
            if newPoker > arr[j]:
                break
            #  向右挪动手动的牌，留出空位置
            pokers[j+1] = arr[j]
            j -= 1
        #  新接牌插入空位置
        pokers[j+1] = newPoker

// 
// c++ language
//


// 比较函数定义，客户具体实现
typedef bool (*compare_data_t)(void*, void*);


// 比较函数
bool compare(void *d1, void* d2) {
    return *((int*)d1) > *((int*)d2);
}


template<class T, int size>
void Sort<T, size>::insert_sort(T* data) {
    int i, j, k;
    // 外层循环控制揭牌
    for (i=1; i<size; i++) {
        // 新接的牌
        T key = data[i];
        
        // 内层循环控制手中的牌
        for (j=i-1; j>=0; j--) {
            // 牌面比较
            if (this->compare_data_(&data[j], &key)) {
                // 向右挪动手中的牌，流出插入位置
                data[j+1] = data[j];
                continue;
            }
            
            break;
        }
        // 新接的牌插入空位置
        data[j+1] = key;
    }
}

数据库

文章转载自老码农空杯修行记，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

插入排序

评论