希尔排序
希尔排序是插排的一种，是插排的改进。
时间复杂度是$\mathcal O(n$^$1.3-2)$
C++代码
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
/*
* 希尔排序的C++实现
* https://www.runoob.com/data-structures/shell-sort.html
*/
template<typename T>
void insert_sort(vector<T> &x) {
/*
* easy understood insert_sort function
* which will be called in function shell_sort
*/
for (int i = 0; i < x.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (x[j + 1] < x[j]) {
T xm = x[j];
x[j] = x[j + 1];
x[j + 1] = xm;
}
}
}
}
template<typename T>
vector<T> get_range_vector(vector<T> &x, int r, int offset = 0) {
/*
* this function helps to take elements from x every r
* if offset is not 0, the first element's index is offset.
*/
// x is a vector
// r is range(or gap)
vector<T> ans((x.size() - offset) / r);
for (int i = offset; i < x.size(); i += r) {
ans[i / r] = x[i];
}
return ans;
}
template<typename T>
void copy_range_x2_raw_x(vector<T> &raw_x, vector<T> &new_x, int gap, int offset) {
for (int i = 0; i < new_x.size(); i++) {
raw_x[i * gap + offset] = new_x[i];
}
}
template<typename T>
void shell_sort(vector<T> &x) {
int t = 2;
int gap = x.size() / 2;
while (gap >= 1) {
for (int i = 0; i < x.size() / t; i++) {
auto ranged_x = get_range_vector(x, gap, i);
insert_sort(ranged_x);
copy_range_x2_raw_x(x, ranged_x, gap, i);
}
t *= 2;
gap /= 2;
}
}
int main() {
// test
vector<int> nums = {-1, 0, 1, 2, -1, -4, 100, 23, 90, 98};
shell_sort(nums);
for (auto n: nums) {
cout << n << ' ';
}
}
运行输出：
-4 -1 -1 0 1 2 23 90 98 100
Python实现
from typing import List
def insert_sort(x: List):
for i in range(len(x)):
for j in list(range(i))[::-1]:
if x[j+1] < x[j]:
xm = x[j]
x[j] = x[j+1]
x[j+1] = xm
return x
# 希尔排序
def shell_sort(x: List):
t: int = 2
gap: int = len(x) // t
while(gap >= 1):
for i in range(len(x) // t):
x[i::gap] = insert_sort(x[i::gap])
t *= 2
gap //= 2
return x