在讲解排序算法之前，我们需要先了解一下排序
所谓排序，就是将数据按照我们的想法将其按照一定规律组合在一起
稳定性：一组数据中的数据是否在排序前后都保持的一定的前后顺序关系，比如在排序前a[3]=2 a[5]=2，这时他们有着前后的顺序关系，在排序后，扔保持着第一个2在第二个2的后面，这种就是稳定的，废话不多说，直接上干货
一、插入排序
思想：将待排序的数据插入到已排好的数据中去，比如我们在玩扑克牌时，我们抓起一张牌，就要选择一个合适的位置进行插入，使其保持有序，这样也方便我们出牌
插入某个数据时，将这个数据与其前一个位置的数据进行比较，如果小于前一个位置的数据，即a[i]<a[i-1]，让前一个位置的数据前后挪一个位置，待排序的数据继续和前一个位置进行比较，直到找到一个合适的位置，将其插入即可，（直接交换也可以，比较之后，符合要求直接交换）
不交换
void InsertSort(int* a, int n)
{
for (int i = 0; i <= n - 2; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
```cpp
void InsertSort2(int* a, int n)
{
for (int i = 0; i <= n - 2; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
swap(a[end + 1], a[end]);
end--;
}
else
{
break;
}
}
}
}
1 元素集合越接近有序，直接插入排序算法的时间效率越高
2 时间复杂度O（N^2）
3 空间复杂度 O（1）
4稳定性 ：稳定
二、冒泡排序
思想：一组数据，每趟排一个数据，比如在排升序时，从数据的第二个位置开始进行比较，本数据和前一个数据进行比较，如果前一个数据大于本数据，两数据交换，一趟可以排一个数据，依次排序，当某一趟一个数据都没有交换时，说明数据已经有序，可以定义flag进行标记，如果已经有序，break即可
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
swap(a[j - 1], a[j]);
flag = 1;
}
}
if (flag == 0) break;
}
}
时间复杂度 O（N^2）
空间复杂度 O（1）
稳定性：稳定
三、选择排序
思想：遍历整个数据，找出其中的最大值和最小值，最大值与数据的最后一个位置的数据进行交换，最小值与数据的最左位置的数据进行交换，然后缩小区间（left++ ，right–），继续执行操作
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <=end; i++)
{
if (a[i] < a[mini]) mini = i;
if (a[i] > a[maxi]) maxi = i;
}
swap(a[begin], a[mini]);
if (maxi == begin)
{
maxi = mini;
}
swap(a[end], a[maxi]);
begin++;
end--;
}
}
时间复杂度O（N^2）
空间复杂度O（1）
稳定性 ：不稳定
四、堆排序
思想：堆排序是利用树，将数据建堆，然后根据情况向上或向下调整（升序建大堆，降序建小堆）
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(a[0], a[end]);
AdjustDown(a, end, 0);
end--;
}
}
时间复杂度 O（N*logN）
空间复杂度 O（1）
稳定性： 不稳定
五、希尔排序
思想：分组，组内排序，更改组的大小，无序->接近有序->有序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i += gap)
{
int end = i;
while (end >= 0)
{
if (a[end + gap] < a[end])
{
swap(a[end + gap], a[end]);
end -= gap;
}
else
{
break;
}
}
}
}
}
希尔排序是对直接插入排序的优化
当gap>1时都是预排序，目的是让数组更接近有序，gap=1时，数据已经接近于有序，效率就会高很多
一般gap/3+1
时间复杂度：一般我们认为是O（n^1.3）
空间复杂度O（1）
稳定性： 不稳定
六、快速排序
快速排序是一个非常重要的排序算法，在很多语言的库中，排序函数的底层都是快速排序，这是一个很优秀，很值得我们去学习的方法，也是比较复杂的排序算法
思想：任取待排序元素序列中的元素作为基准值，按照该排序码将集合分为两个子序列，左子序列中所有的元素均小于基准值，右子序列中所有的元素均大于基准值，然后重复该过程
1 hoare 版本快排
在基准值的选取方面有很多方法，随机数选取，三数取中，固定第一个值就为基准值…等等
在数据小到一定范围时，这时候递归也已经很深，我们知道，递归可以理解一棵树，越到下面，叶子越多，所以可以利用其他简单的排序，比如插入排序，将这个小范围数据进行排序
如果升序：左找大于基准值的数，右找小于基准值的数，都找到后交换
void QuickSort1(int* a, int left, int right)
{
//递归出口
if (left >= right) return;
if (right - left + 1 < 10)
{
InsertSort(a, right - left + 1);
}
else
{
int begin = left, end = right;
//int keyi = left;
//int randi = rand() % (right - left+1);//随机数，尽量避免原数据有序，后达到最坏的效果，选出一个随机的数，与原left位置进行交换
// //继续下面逻辑
//randi += left;
//swap(a[left], a[randi]);
int midi = GetMidi(a, left, right);
swap(a[midi], a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left < right && a[left] <= a[keyi])
{
left++;
}
swap(a[left], a[right]);
}
swap(a[keyi], a[left]);
keyi = left;
QuickSort1(a, begin, keyi - 1);
QuickSort1(a, keyi + 1, end);
}
}
2 前后指针法
初始时，基准值，prev都在数据起始位置，cur在后一个位置
cur不断向后进行遍历，当cur指向位置的数据小于基准值时，prev++，并交换两指针所指的数据，最后基准值数据与prev数据进行交换，递归基准值左右两个小区间的数据
void QuickSort2(int* a, int left, int right)
{
if (left >= right) return;
int prev = left;
int keyi = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] >= a[keyi])
{
cur++;
}
else
{
prev++;
swap(a[prev], a[cur]);
cur++;
}
}
swap(a[keyi], a[prev]);
keyi = prev;
QuickSort2(a, left, keyi - 1);
QuickSort2(a, keyi+1, right);
}
3 分治快速排序
利用随机数取基准值，将数据分为三块，大于基准值，等于基准值，小于基准值
int GetRandomNum(vector<int>& nums, int left, int right)
{
int r = rand();
return (r % (right - left + 1) + left);
}
void qsort(vector<int>& nums, int l, int r)
{
if (l > r) return;
int key = GetRandomNum(nums, l, r);
int n = nums.size();
int left = l - 1, right = r + 1, i = l;
while (i < right)
{
if (nums[i] < key)
{
swap(nums[++left], nums[i++]);
}
else if (nums[i] == key)
{
i++;
}
else
{
swap(nums[--right], nums[i]);
}
}
qsort(nums, l, left);
qsort(nums, right, r);
}
//分治法快速排序（随机数+数组分三块（小于，等于，大于））
void QuickSort3(vector<int>& nums)
{
srand(time(NULL));
qsort(nums, 0, nums.size() - 1);
}
4 非递归版快速排序
利用数据结构栈来代替递归，排序的左右区间不断入栈出栈
void QuickSortNonRe(int* a, int left, int right)
{
stack<int> st;
st.push(right);
st.push(left);
while (!st.empty())
{
int begin = st.top();
st.pop();
int end = st.top();
st.pop();
int prev = begin;
int keyi = begin;
int cur = begin + 1;
while (cur <= right)
{
if (a[cur] >= a[keyi])
{
cur++;
}
else
{
prev++;
swap(a[prev], a[cur]);
cur++;
}
}
swap(a[keyi], a[prev]);
keyi = prev;
if (keyi + 1 < end)
{
st.push(end);
st.push(keyi+1);
}
if (begin < keyi - 1)
{
st.push(keyi-1);
st.push(begin);
}
}
}
时间复杂度O（N*logN）
空间复杂度O（logN）
稳定性：不稳定
七、归并排序
归并排序，分组，分组，再分组，合并，合并，再合并
需要利用额外空间，然后再拷贝回来
void _MergeSort(vector<int>& nums,int left,int right)
{
if (left >= right) return;
int mid = (left + right) >> 1;
_MergeSort(nums, left, mid);
_MergeSort(nums, mid+1, right);
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right)
{
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while (cur1 <= mid) tmp[i++] = nums[cur1++];
while (cur2 <= right) tmp[i++] = nums[cur2++];
for (int i = left; i <= right; i++)
{
nums[i] = tmp[i-left];
}
}
void MergeSort(vector<int>& nums)
{
tmp.resize(nums.size());
_MergeSort(nums, 0, nums.size() - 1);
}
