排序：基本概念
1.基于插入：
（1）直接插入排序
（2）希尔（shell）排序算法
2.基于交换：
（1）冒泡排序
（2）快速排序
3.基于选择：
（1）简单选择排序
（2）堆排序
4.其他：
（1）归并排序
（2）基于计数的排序
如何判断排序好坏：
1.就地排序/非就地排序（反映空间复杂度）
（1）如果在排序过程中，只使用到了存储数据的空间，没有使用其他额外空间，称为是就地排序
2.内部排序/外部排序
（1）待排序数据能够一次性放到内存中---->内部排序
（2）待排序数据不能够一次性放到内存中---->外部排序
注：目前只有归并排序是外部排序
3.稳定排序/不稳定排序
（1）排序前后相同数据的相对位置没有发生变化---->稳定的
（2）排序前后相同数据的相对位置发生变化---->不稳定的
4.时间复杂度
（1）直接插入排序：在添加新的数据时，我们使用顺序查找（遍历）的方式，找到其要插入的位置，将其插入
//（将数据分为有序区与待排序区，基本所有排序算法都会将数据分为这两个区域）
时间复杂度：O(n^2)
注：第一版代码不稳定，略加优化后稳定，时间复杂度不变
是否稳定：稳定
为就地排序
-折半插入排序 //优化：将直接插入排序中顺序查找换成二分查找，时间复杂度不变，为稳定排序
-2路插入排序 //优化：在折半插入排序基础上，引入一个循环数组，将排序过程中移动次数减少，时间复杂度不变，为非就地排序
注：在使用直接插入排序时，如果表中记录只有个别是无序的，多数保持有序，这种情况下算法的效率也会比较高，此外，如果需要排序数据总量较少，算法效率同样会很高。下述希尔排序便是基于这两点进行改进。
（2）希尔（shell）排序算法（缩小增量排序算法）：在直接插入排序算法的基础上，对待排序数据进行分组，先对每组进行排序，然后不断缩小组数，不断排序，最终缩小为一组。
分组：分成组数与数据下标增量相同，如0--3四个数据，分为0 2，1 3
增量的选择：对n个数据进行排序，依次分为 n/2，n/4，n/8...1组 ---->希尔增量序列
时间复杂度：最坏为O(n^2)
是否稳定：不稳定
为就地排序
//上述为取希尔增量序列时的情况
注：直接插入排序就是增量为一的希尔排序
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
//直接插入排序（不稳定）
void Insert_Sort(vector<int>(&v))
{
//保存待排序数据
int tmp(0);
//保存待排序数据应该所处位置下标
int ind(0);
//第一趟可以不排
for (int i = 1; i < v.size(); ++i)
{
//第二趟开始排序
tmp = v[i];
ind = i;
//有序区0 ---> i - 1
for (int j = 0; j < i; ++j)
{
if (v[j] > tmp)
{
//找第一个大于tmp的数
ind = j;
break;
}
}
//ind到i - 1下标对应数据全部后移
for (int j = i; j > ind; --j)
{
v[j] = v[j - 1];
}
v[ind] = tmp;
}
}
//略加优化，变为稳定版本
void Insert_Sort_2(vector<int>(&v))
{
//保存待排序数据
int tmp(0);
//第一趟可以不排
for (int i = 1; i < v.size(); ++i)
{
//第二趟开始排序
tmp = v[i];
//有序区0 ---> i - 1
//保存待排序数据应该所处位置下标
int j(0);
//从i-1位置往回比较
for (j = i; j > 0; --j)
{
if (tmp < v[j - 1])
{
v[j] = v[j - 1];
}
else
{
break;
}
}
v[j] = tmp;
}
}
void Shell_Sort(vector<int>(&v))
{
//保存待排序数据
int tmp(0);
int k(0);//趟数
//枚举增量/组数
for (int d = v.size() / 2; d >= 1; d /= 2)
{
k++;//记录趟数
//从每一组第二个数开始排序
for (int i = d; i < v.size(); ++i)
{
tmp = v[i];
//保存待排序数据应该所处位置下标
int j(0);
for (j = i - d; j >= 0; j -= d)
{
if (tmp < v[j])
{
v[j + d] = v[j];
}
else
{
break;
}
}
v[j + d] = tmp;
/*for (j = i; j >= d; j -= d)
{
if (tmp < v[j-d])
{
v[j] = v[j - d];
}
else
{
break;
}
}
v[j] = tmp;*/
}
}
}
int main()
{
vector<int> v(10);
int n(0);
cin >> n;
v.resize(n);
for (auto &a : v)
{
cin >> a;
}
Shell_Sort(v);
for (auto a : v)
{
cout << a << ' ';
}
return 0;
}
/*
6
3 1 7 5 2 4
*/
