插入排序和希尔排序

简单的插入排序

原理

思路很简单，不断地将待排序元素插入到已排序序列中，当插入最后一个元素时，整个序列即完成排序

可视化插入排序算法

代码实现

C++代码实现

#include <iostream>
#include <vector>
using namespace std;

void insertion_sort(vector<int> &v){
    for(int i = 1;i < v.size();++i){
        int temp = v[i];
        int j = i - 1;
        while(j >= 0 && temp < v[j]){
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = temp;
    }
}
int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(22);
    v.push_back(12);
    v.push_back(5); 
    insertion_sort(v);
    for(int i = 0;i < 4;i++) cout << v[i] << endl;
    return 0;
}

Python代码实现

def insertion_sort(seq):
    for i in range(1,len(seq)):
        temp = seq[i]   # 保存当前值
        j = i-1 # 前一个元素的下标
        while(j >= 0 and temp < seq[j]):
            seq[j+1] = seq[j]   # 元素后移
            j -= 1  # 继续往前查找
        seq[j+1] = temp # 在该位置插入
    # 在前面已经排好的序列中，找到正确位置插入
    # 对(1,len(seq))的每一个元素进行该操作即可完成序列的排序
# 排序测试
if __name__ == '__main__':
    seq = [3,44,38,5,47,15,36,26,27,50]
    insertion_sort(seq)
    print(seq)

改良插入排序后的希尔排序

原理

插入排序的改良和优化,选择一个间距,将序列分成很多子序列并进行插入排序,降低间距并重复插入排序,直到间距降为1完成排序

具体的实现可以看这篇博客,这里不做赘述
希尔排序

可视化希尔排序算法

代码实现

C++代码实现

#include <iostream>
#include <vector>
using namespace std;

void shell_insert(vector<int> &v,int beg,int gap){
    for(int i = beg + gap;i < v.size();++i){
        int temp = v[i];
        int j = i - gap;
        while(j >= 0 && temp < v[j]){
            v[j+gap] = v[j];
            j -= gap;
        }
        v[j+gap] = temp;
    }
}
void shell_sort(vector<int> &v){
    int gap = v.size() / 2;
    while(gap >= 0){
        int beg = gap - 1;
        shell_insert(v,beg,gap);
        gap--;
    }
}
int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(22);
    v.push_back(12);
    v.push_back(5); 
    shell_sort(v);
    for(int i = 0;i < 4;i++) cout << v[i] << endl;
    return 0;
}

Python代码实现

def shell_insert(seq,beg,gap):
    for i in range(beg+gap,len(seq),gap):
        temp = seq[i]
        j = i - gap
        while(j >= 0 and temp < seq[j]):
            seq[j+gap] = seq[j]
            j -= gap
        seq[j+gap] = temp

def shell_sort(seq):
    gap = len(seq)//2    # 获取初始间距 需要整除
    while(gap > 0):
        beg = gap - 1
        while(beg >= 0):
            shell_insert(seq,beg,gap)
            beg -= 1
        gap //= 2    # 缩小间距，需要整除
# 排序测试
if __name__ == '__main__':
    seq = [3,44,38,5,47,15,36,26,27,50]
    shell_sort(seq)
    print(seq)