内容纲要
插入排序和希尔排序
简单的插入排序
原理
思路很简单,不断地将待排序元素插入到已排序序列中,当插入最后一个元素时,整个序列即完成排序
可视化插入排序算法
代码实现
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)