C++：排序算法
目录
一、插入排序
1.直接插入排序
2.希尔排序
二、交换排序
1.冒泡排序
2.快速排序
三、选择排序
1.简单选择排序
2.堆排序
四、归并排序
1.二路归并排序的递归实现
2.二路归并排序的非递归实现
一、插入排序
1.直接插入排序
直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都排好序。（记录就是排序问题中的数据元素）
平均时间复杂度为O(n^2)。
直接插入排序是一种稳定的排序方法。
待排序记录基本有序时，直接插入排序的效率很高。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
for (int i = 1; i < nums.size(); i++) //将第1个记录当作有序序列，从第2个记录开始执行插入操作
{
int temp = nums[i]; //暂存当前记录，当前记录之前都是有序的
int j;
for (j = i - 1; j >= 0 && temp < nums[j]; j--) //从后往前遍历有序序列
{
nums[j + 1] = nums[j]; //记录后移1位
}
nums[j + 1] = temp; //插入记录
}2.希尔排序
希尔排序（Shell sort）是对直接插入排序的一种改进，当待排序列基本有序以及待排序记录个数较少时，直接插入排序的效率都很高，于是将序列分割以及让序列向基本有序发展。
希尔排序的基本思想是：先将整个待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序。
时间复杂度为O(nlog2n)~O(n^2)。（前一个2为底数）
由于在希尔排序过程中记录是跳跃移动的，因此希尔排序是不稳定的。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
for (int d = nums.size() / 2; d >= 1; d = d / 2) //以增量d来分割子序列并进行直接插入排序
//最后一趟排序时d=1，即不分割，此时序列已基本有序
{
for (int i = d; i < nums.size(); i++) //从这里开始类似于直接插入排序
{
int temp = nums[i]; //暂存待排序记录
int j;
for (j = i - d; j >= 0 && temp < nums[j]; j -= d)
{
nums[j + d] = nums[j]; //记录后移d位
}
nums[j + d] = temp; //插入记录
}
}二、交换排序
1.冒泡排序
冒泡排序（bubble sort）的基本思想是：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。每趟排序都将使得序列的右边多一个有序记录。
平均时间复杂度为O(n^2)。
冒泡排序是稳定的排序方法。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
for (int i = 0; i < nums.size() - 1; i++) //只需排n-1趟
{
for (int j = 0; j < nums.size() - 1 - i; j++) //遍历无序序列
{
if (nums[j] > nums[j + 1]) //若反序，则交换
{
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}2.快速排序
快速排序（quick sort）是对冒泡排序的一种改进，减少了总的比较次数和移动次数。
快速排序的基本思想是：选定一个轴值（pivot，即比较的基准），将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。可以直接选择第一个记录作为轴值。
平均时间复杂度是O(nlog2n)。（2为底数）
快速排序是不稳定的排序。
快速排序的平均时间性能是迄今为止所有内排序算法中最好的，因此得到广泛应用。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
/*作一次划分，参数是被划分的序列的左右下标*/
int partition(int left, int right)
{
int i = left, j = right;
while (i < j) //多次左、右侧扫描
{
while (i < j && nums[i] <= nums[j]) //j指向比i所指的数还小的数（右侧扫描）
{
j--;
}
if (i < j) //若i还在j左边，交换两数，即把较大者往右放
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
}
while (i < j && nums[i] <= nums[j]) //i指向比j所指的数还大的数（左侧扫描）
{
i++;
}
if (i < j) //若i还在j左边，交换两数，即把较大者往右放
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j--;
}
}
return i; //此时i=j，已划分完毕（i的左边全小于它，右边全大于它）
}
/*快速排序函数，递归执行，参数是待排序序列的左右下标*/
void quick_sort(int left, int right)
{
if (left >= right) //子序列只剩一个记录，无需再排
{
return;
}
else
{
int pivot = partition(left, right); //作一次划分
quick_sort(left, pivot - 1); //对左侧子序列进行快速排序
quick_sort(pivot + 1, right); //对右侧子序列进行快速排序
}
}
quick_sort(0, nums.size() - 1); //调用函数对序列nums进行快速排序三、选择排序
1.简单选择排序
简单选择排序（simple select sort）的基本思想是：在无序序列中找出最小的记录，然后放在无序序列的最左端，重复该过程，直到序列全部有序。
平均时间复杂度为O(n^2)。
简单选择排序是不稳定的排序。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
for (int i = 0; i < nums.size()-1; i++) //只需选择n-1次
{
int index = i; //index存最小数的下标，初始化为最左侧下标
for (int j = i + 1; j < nums.size(); j++) //遍历无序序列
{
if (nums[j] < nums[index]) //若遍历到的数更小，index存其下标
{
index = j;
}
}
if (index != i) //若最小数不在最左侧，则移到最左侧
{
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}2.堆排序
堆排序是简单选择排序的改进，改进的着眼点是在选出最小记录的同时，也找出较小记录，减少了记录的比较次数。
堆排序的基本思想是：首先将待排序序列调整成一个堆，将堆顶移走作为最大者，并将剩余记录再调整成堆，又将堆顶移走作为次大者，依此类推，直到得到整个有序序列。
平均时间复杂度为O(nlog2n)。（2为底数）
堆排序是不稳定的排序。
堆排序对待排序序列的初始状态并不敏感，相对于快速排序，这是堆排序最大的优点。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
/*堆调整，参数为待排序列，被调整节点和最后一个节点的下标（用于防止数组越界）*/
void sift(vector<int>& nums, int sorted_num, int last)
{
int parent(sorted_num); //父节点
int child(2 * sorted_num + 1); //左孩子节点
while (child <= last) //尚未越界
{
//将child指向孩子中的较大者，child<last意味着有右孩子
if (child < last && nums[child] < nums[child + 1])
{
child++; //child+1即指向右孩子
}
if (nums[parent] > nums[child]) //父节点更大，满足堆条件，结束
{
break;
}
else //否则，交换父子节点并更新父子节点
{
int temp = nums[parent];
nums[parent] = nums[child];
nums[child] = temp;
parent = child;
child = 2 * parent + 1;
}
}
}
/*堆排序函数，参数是待排序列*/
void heap_sort(vector<int>& nums)
{
//初始化堆，最后一个分支节点的下标为nums.size()/2-1
for (int i = nums.size() / 2 - 1; i >= 0; i--)
{
sift(nums, i, nums.size() - 1);
}
//将堆顶和最后一个节点交换，再重建堆，每交换一次堆减少一个元素（j--）
for (int j = nums.size() - 1; j > 0; j--)
{
int temp = nums[0];
nums[0] = nums[j];
nums[j] = temp;
sift(nums, 0, j - 1);
}
}
heap_sort(nums); //对序列nums进行堆排序四、归并排序
归并排序（merge sort）的基本思想是：将若干个有序序列逐步归并，最终归并为一个有序序列。
常用的是二路归并排序，其基本思想是：将待排序列划分为两个长度相等的子序列，分别对这两个子序列进行排序，再将这两个有序子序列合并成一个有序序列。
平均时间复杂度为O(nlog2n)。（2为底数）
二路归并排序是一种稳定的排序方法。
1.二路归并排序的递归实现
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
/*用于合并两个相邻子序列[left_1, right_1]和[right_1 + 1, right_2], 得到[left_1, right_2]*/
void merge(int left_1, int right_1, int right_2)
{
int* temp = new int[nums.size()]; //申请一个合并辅助空间
int i = left_1, j = right_1 + 1, k = left_1;
while (i <= right_1 && j <= right_2) //当两个序列都还有待排元素时
{
if (nums[i] <= nums[j]) //取较小者放入辅助空间
{
temp[k++] = nums[i++];
}
else
{
temp[k++] = nums[j++];
}
}
while (i <= right_1) //若第二个序列无待排元素
{
temp[k++] = nums[i++]; //将第一个序列剩余元素全部放入辅助空间
}
while (j <= right_2) //若第一个序列无待排元素
{
temp[k++] = nums[j++]; //将第二个序列剩余元素全部放入辅助空间
}
for (i = left_1; i <= right_2; i++) //将合并结果放回原序列
{
nums[i] = temp[i];
}
delete[] temp; //释放合并辅助空间
}
/*二路归并排序的递归算法，对[left,right]进行排序*/
void merge_sort(int left, int right)
{
if (left == right) //只有1个记录，递归结束
{
return;
}
else
{
int mid = (left + right) / 2; //分割为两个子序列
merge_sort(left, mid); //对前半部分归并排序
merge_sort(mid + 1, right); //对后半部分归并排序
merge(left, mid, right); //将两个子序列归并
}
}
merge_sort(0, nums.size() - 1); //对序列nums归并排序2.二路归并排序的非递归实现
二路归并排序的递归实现是一种自顶向下的方法，形式简洁但效率相对较差。二路归并排序的非递归实现是一种自底向上的方法，算法效率较高，但算法较复杂。
vector<int> nums = { 5,0,1,2,7,3,9,6,4,8 }; //待排序序列
/*用于合并两个相邻子序列[left_1, right_1]和[right_1 + 1, right_2], 得到[left_1, right_2]*/
void merge(int left_1, int right_1, int right_2)
{
int* temp = new int[nums.size()]; //申请一个合并辅助空间
int i = left_1, j = right_1 + 1, k = left_1;
while (i <= right_1 && j <= right_2) //当两个序列都还有待排元素时
{
if (nums[i] <= nums[j]) //取较小者放入辅助空间
{
temp[k++] = nums[i++];
}
else
{
temp[k++] = nums[j++];
}
}
while (i <= right_1) //若第二个序列无待排元素
{
temp[k++] = nums[i++]; //将第一个序列剩余元素全部放入辅助空间
}
while (j <= right_2) //若第一个序列无待排元素
{
temp[k++] = nums[j++]; //将第二个序列剩余元素全部放入辅助空间
}
for (i = left_1; i <= right_2; i++) //将合并结果放回原序列
{
nums[i] = temp[i];
}
delete[] temp; //释放合并辅助空间
}
/*执行一趟归并排序*/
void merge_pass(int h)
{
int i(0);
while (i + 2 * h <= nums.size()) //有两个长度为h的子序列
{
merge(i, i + h - 1, i + 2 * h - 1); //合并前两个子序列
i = i + 2 * h; //准备合并下两个子序列
}
if (i + h < nums.size()) //有两个长度分别等于h和小于h的子序列，合并它们
{
merge(i, i + h - 1, nums.size() - 1);
}
}
/*二路归并排序的非递归算法*/
void merge_sort()
{
int h(1); //初始子序列长度为1
while (h < nums.size())
{
merge_pass(h);
h = 2 * h;
}
}
merge_sort(); //对序列nums归并排序