1.冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
void bubbleSort(vector<int> &nums) {
int N = nums.size();
for (int i = 0; i < N - 1; i++) { // 外循环
for (int j = 0; j < N - i - 1; j++) { // 内循环
if (nums[j] > nums[j + 1]) {
// 交换 nums[j], nums[j + 1]
swap(nums[j], nums[j + 1]);
}
}
}
}
复杂度分析：
时间复杂度： O(N^2)
空间复杂度： O(1)
2.选择排序
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
（1）初始状态：无序区为R[1..n]，有序区为空；
（2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
（3）n-1趟结束，数组有序化了。
void selectionSort(vector<int> &nums) {
int N = nums.size();
int minIndex;
for (int i = 0; i < N-1 ; i++) { // 外循环
minIndex=i;
for (int j = i+1; j < N ; j++) { // 内循环
if (nums[j] < nums[minIndex])
minIndex = j;
}
swap(nums [i], nums[minIndex]);
}
}
复杂度分析：
时间复杂度： O(N^2)
空间复杂度： O(1)
3.插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
（1）从第一个元素开始，该元素可以认为已经被排序；
（2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
（5）将新元素插入到该位置后；
（6）重复步骤2~5。
void insertSort(vector<int> &nums) {
int N = nums.size();
int temp,preIndex;
for (int i = 1; i < N; i++) {
temp=nums[i];
preIndex=i-1;
//步骤（3）
while(preIndex>=0 && temp<=nums[preIndex]){
nums[preIndex+1]=nums[preIndex];
preIndex--;
}
//步骤（5）
nums[preIndex+1]=temp;
}
}
复杂度分析：
时间复杂度： O(N^2)
空间复杂度： O(1)
4.希尔排序
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
（1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
（2）按增量序列个数k，对序列进行k 趟排序；
（3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
void shellSort(vector<int> &nums) {
int N = nums.size();
int gap;
for(gap = N/2; gap>0; gap=gap/2) {
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行????????????
for(int i = gap; i < N; i++) {
int j = i;
int temp = nums[i];
while (j-gap >= 0 && temp < nums[j-gap]) {
nums[j] = nums[j-gap];
j = j-gap;
}
nums[j] = temp;
}
}
}
5.归并排序
归并排序（Merge Sort）体现了分而治之的算法思想，具体为：
「分」： 不断将数组从 中点位置 划分开，将原数组的排序问题转化为子数组的排序问题；
「治」： 划分到子数组长度为 1 时，开始向上合并，不断将 左右两个较短排序数组 合并为 一个较长排序数组，直至合并至原数组时完成排序；
算法流程
1.递归划分：
a.计算数组中点 m ，递归划分左子数组 mergesort(l, m) 和右子数组 mergesort(m + 1, r) ；
b.当 l≥r 时，代表子数组长度为 1 或 0 ，此时 终止划分 ，开始合并；
2.合并子数组：
a.暂存数组 numsnums 闭区间 [l, r]内的元素至辅助数组 temp ；
b.循环合并： 设置双指针 pre , post 分别指向temp 的左 / 右子数组的首元素；
注意： numsnums 子数组的左边界、中点、右边界分别为 l , m , r ，
而辅助数组 temp 中的对应索引为 0 , m−l, r−l ；
当 pre == m - l + 1时： 代表左子数组已合并完，因此添加右子数组元素 temp[post] ，并执行 post = post + 1；
否则，当 post == r−l+1 时： 代表右子数组已合并完，因此添加左子数组元素 temp[pre] ，并执行 pre = pre +1 ；
否则，当 temp[pre]≤temp[post] 时： 添加左子数组元素 temp[pre] ，并执行 pre = pre + 1；
否则（即当 temp[pre ] > temp[post]时）： 添加右子数组元素 temp[post] ，并执行 post =post +1 ；
void mergesort(vector<int> & nums, int l, int r){
if(l>=r) return;
//递归划分
m=(l+r)/2;
mergesort(nums, l, m);
mergesort(nums,m+1,r);
//合并
int temp[r-l+1];//新建temp，暂存左右数组
for(int i=l;i<=r;i++){
temp[i]=nums[i];
}
int pre=0,post=m+1-l;
for(int i=l;i<=r;i++){
if(pre==m+1-l) nums[i]=temp[post++];//左子数组已合并完
else if(post==r-l+1) nums[i]=temp[pre++];//右子数组已合并完
else if(temp[pre]<=temp[post]) nums[i]=temp[pre++];//右子数组已合并完
else if(temp[pre]>temp[post]) nums[i]=temp[post++];//右子数组已合并完
}
}
复杂度分析：
时间复杂度：O(NlogN)
空间复杂度：O(N)
6.快速排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
（1）从数列中挑出一个元素，称为 “基准”（pivot）；
（2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
int partition(vector<int>& nums, int l, int r) {
// 以 nums[l] 作为基准数
int i = l, j = r;
while (i < j) {
while (i < j && nums[j] >= nums[l]) j--;
while (i < j && nums[i] <= nums[l]) i++;
swap(nums[i], nums[j]);
}
swap(nums[i], nums[l]);
return i;
}
void quickSort(vector<int>& nums, int l, int r) {
// 子数组长度为 1 时终止递归
if (l >= r) return;
// 哨兵划分操作
int i = partition(nums, l, r);
// 递归左（右）子数组执行哨兵划分
quickSort(nums, l, i - 1);
quickSort(nums, i + 1, r);
}
7.堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
** 算法描述**
（1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
（2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
（3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
#include <iostream>
#include <vector>
using namespace std;
vector<int> nums={2,3,5,4,6,1};
int N = nums.size();
void heapify(vector<int> &nums, int i) { // 堆化
int N = nums.size();
int left = 2*i+1;
int right = 2* i+2;
int largest = i;
if (left < N && nums[left] > nums[largest]) {
largest = left;
}
if (right < N && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums[i],nums[largest]);
heapify(nums, largest);
}
}
void buildMaxHeap(vector<int> &nums) { // 建立大顶堆
for (int i = N/2; i >= 0; i--) {
heapify(nums, i);
}
}
void heapSort(vector<int> &nums) {
buildMaxHeap(nums);
for (int i = nums.size() - 1; i > 0; i--) {
swap(nums[0],nums[i]);
N--;
heapify(nums, 0);
}
}
int main()
{
//int nums[6]={2,3,5,4,6,1};
heapSort(nums);
for(int i=0;i<6;i++){
cout << nums[i];
}
return 0;
}
