排序算法-希尔排序(进阶版插入排序)

原理

他就是提高了插入的效率,选定步长,根据步长进行分组然后根据组进行插入排序.

步长不断减少,当减少到1时就是插入排序

时间复杂度最坏情况O(N^2)

其实可以理解成插入排序是根据1来排序,而希尔排序是根据步长来排序的.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void shellSort(vector<int>& v)
{
	//没有元素或元素少于两个不需要排序
	if (v.empty() || v.size() < 2)
	{
		return;
	}
 
	//确定步长
	for (int i = v.size() / 2; i > 0; i /= 2)
	{
		//根据步长进行插入排序
		for (int j = i; j < v.size(); j += i)
		{
			for (int k = j; k > 0; k -= i)
			{
				if (v[k] < v[k - i])	//升序
				{
					swap(v[k], v[k - 1]);
				}
			}
		}
	}
	
}
 
int main()
{
	vector<int> v = { 32,4,7,24,5,245,7,245,657,28 };
 
	shellSort(v);
	for (auto val : v)
	{
		cout << val << " ";
	}
	cout << endl;
 
	return 0;
}