常见排序算法（一）
排序：
1、排序在计算机数据处理中经常遇到，在日常的数据处理中，一般可以认为有 1/4 的时间用在排序上，而对于程序安装，
多达 50% 的时间花费在对表的排序上。简而言之，排序是将一组杂乱无章的数据按一定的规律顺次排列起来
2、内排与外排：根据排序方法在排序过程中数据元素是否完全在内存而划分，若一部分数据在外存，则为外排，否则，为内排
3、排序算法的稳定性：根据排序后相同元素顺序是否会发生改变而定，
如两个数 a 与 b，a == b 且 a 在 b 的前面，若排序后 a 仍然在 b 的前面，则为稳定的，否则，为不稳定的
4、排序算法的性能评估：算法的执行时间是衡量算法好坏的最重要参数，其时间开销可用算法执行中的数据比较次数与移动次数来衡量
排序算法：
1、时间复杂度：
a、平方阶 (o(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序
b、线性对数阶 (o(nlog2n)) 排序：快速排序、堆排序和归并排序
c、o(n1+§)) 排序，§ 是介于 0 和 1 之间的常数：希尔排序
d、线性阶 (o(n)) 排序：基数排序，桶排序和计数排序
2、稳定性：
a、稳定的排序算法：冒泡排序、插入排序、归并排序、计数排序、桶排序和基数排序
b、不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序
注：稳定性是相对的，例如我们把比较冒泡排序里对两个元素比较的算法改成大于等于，它会变成不稳定的！
3、比较与非比较：
a、比较排序：冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序和堆排序
b、非比较排序：计数排序、桶排序和基数排序
十大经典排序算法：
以下均按非降序排序
1、冒泡排序(bubblesort)：
a、比较相邻两个元素，若前者的大于后者，则交换这两个元素
b、向后移动一项，再执行比较交换操作；当移动到最后一位时，这个元素即为本轮最大值
c、从新从头开始，除了最后一项，执行 a、b 操作，直到排序完成
注：在排序过程中，我们可以设置一个标志判断在一轮排序中是否有交换元素，若一轮排序过后仍无交换，则说明排序已完成
#include <iostream>
#include <vector>
#include <cstdlib>
//采用引用的方式传参，否则传入的只是一个不会改变原数据的形参
void bubblesort(std::vector<int>& nums);
int main()
{
std::vector<int> nums;
int len = 0;
std::cout<<"请输入长度：";
do {
std::cin>>len;
if (len <= 0)
// 标准错误流，输出错误信息
std::cerr<<"请输入正整数：";
} while (len <= 0);
int num = 0;
std::cout<<"输入 "<<len<<" 个数: ";
// size_t 是 unsigned_int 类型，建议在使用下标时使用，但若将负数赋值给它，则会将该数转换为正数，从而产生错误
for (size_t i = 0; i < len; ++i) {
std::cin>>num;
nums.push_back(num);
}
bubblesort(nums);
std::cout<<"排序后的数组：";
// * for 循环
for (int num : nums)
// std::ends 输出空白符，不同电脑的空白符可能不一样
std::cout<<num<<std::ends;
std::cout<<std::endl;
system("pause");
return 0;
}
void bubblesort(std::vector<int>& nums)
{
// 设置交换标志，若一次循环后所有元素都未发生交换，则说明数组已经排列好，可提前退出
bool exchange = false;
size_t len = nums.size();
for (size_t i = 1; i < len; ++i) {
exchange = false;
// 为了方便，我把最小的元素移动到了最前
for (size_t j = len-1; j >= i; j--) {
if (nums[j-1] > nums[j]) {
int temp = nums[j-1];
nums[j-1] = nums[j];
nums[j] = temp;
exchange = true;
}
}
if (!exchange)
return;
}
}
2、选择排序(selectionsort)：
a、在初始序列 r[i...n-1] 中找到最小的元素，放到 r[i] 处，i=0，n=待排对象大小
b、++i
c、重复执行 a、b 操作，直至第 n-1 轮
void selectionsort(std::vector<int>& nums)
{
size_t len = nums.size();
// 在每次循环里选出最小的一个排在前面
for (size_t i = 0; i < len-1; ++i){
int min = i;
for (size_t j = i+1; j < len; ++j){
if (nums[j] < nums[min])
min = j;
}
if (i != min){
int temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
return ;
}
3、简单插入排序(insertionsort)：
a、从第一个元素开始，该元素可以认为已经被排序
b、取出下一个元素，在已经排序的元素序列中从后向前扫描
c、如果该元素大于新元素，将该元素移到下一位置
d、重复操作 c，直到找到已排序的元素小于或等于新元素的位置
e、将新元素插入到该位置后
f、重复操作 b-e
void insertionsort(std::vector<int>& nums)
{
size_t len = nums.size();
for (size_t i = 1; i < len; i++) {
int temp = nums[i];
// 在循环中把较大的数往后移一位
size_t j = i;
while (j > 0 && temp < nums[j-1]) {
nums[j] = nums[j-1];
j--;
}
if (j != i)
nums[j] = temp;
}
return ;
}
4、希尔排序(shellsort)：
a、设对象有 n 个元素，先取整数 gap < n 作为间隔，并将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一子序列中，
在每个子序列中分别施行直接插入排序
b、缩小间隔 gap，如 gap = gap/3 + 1
c、重复 a、b 操作，直到取 gap == 1 为
注：gap 有多种取法，但如果 gap = n/2 或 gap = gap/2 时，只有到最后一步奇数位置才会和偶数位置的数进行比较
void shellsort(std::vector<int>& nums)
{
int gap = 1, len = nums.size();
// 先让间隔 gap 尽量大
while (gap < len)
gap = gap*3+1;
while (gap > 0){
for (int i = gap; i < len; i++){
int temp = nums[i];
int j = i - gap;
// 直接插入排序
while (j >= 0 && nums[j] > temp){
nums[j+gap] = nums[j];
j -= gap;
}
nums[j+gap] = temp;
}
gap /= 3;
}
return ;
}
5、快速排序(quicksort)：
a、从数列中挑出一个元素，称为 “基准”（一般为第一个元素）
b、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
c、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
注：快排的非递归算法可以使用栈来实现
void quicksort(int* arr, int low, int high)
{
int star = low, end = high;
if (star > end)
return ;
int temp = arr[star];
while (star != end) {
// 从后找出小于“基准”的数
while (arr[end] >= temp && star < end)
end--;
// 从前找出大于“基准”的数
while (arr[star] <= temp && star < end)
star++;
// 若还在范围内，则交换这两者
if (star < end) {
int t = arr[star];
arr[star] = arr[end];
arr[end] = arr[star];
}
}
// 把“基准”移动到“中间”
int t = arr[low];
arr[low] = arr[star];
arr[star] = t;
// 递归
quicksort(arr, low, star-1);
quicksort(arr, star+1, high);
return ;
}