---

前言

• 什么是排序？

  排序：将一组杂乱无章的数据按一定规律顺次排列起来。即，将无序序列排成一个有序序列（由小到大或由大到小）的运算。

• 排序方法的分类

  按数据存储介质：内部排序和外部排序

  按比较器个数：串行排序和并行排序

  按主要操作：比较排序和基数排序

  按辅助空间：原地排序和非原地排序

  按稳定性：稳定排序和非稳定排序

  按自然性：自然排序和非自然排序

---

一、插入排序

基本思想：

  每步将一个待排序的对象，按其关键码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部循环为止。

插入排序：

  小于 2 的数组，即只有 1 个或没有元素的数组是已经排好序的，这也很好理解。

第一轮：

  2 和 5 比，2 比 5 小，所以保持原序列，当前有序序列为2，5

第二轮：

  5 和 1 比，1 比 5 小，元素 5 后移，然后 2 和 1 比，1 比 2 小，元素 2 也后移（这里要事先将待排序的元素保存下来，不然被后移的元素覆盖就找不到了）

…
重复上面的对比，最终得到排好序的有序序列

代码：

#include<iostream>
#include<vector>
using namespace std;void insertSort(vector<int>& nums)
{int len = nums.size();if (len < 2) return;//数组长度小于2，默认它排好了序for (int i = 1; i < len; ++i){if (nums[i] < nums[i - 1]){int j = i - 1;//指向i之前的数 与i进行对比int temp = nums[i];//先将nums[i]存在变量temp中，while (j>=0 && temp < nums[j]){nums[j + 1] = nums[j];j--;}nums[j + 1] = temp;}}}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){std::cout << *it << " ";}std::cout << std::endl;
}int main()
{vector<int> nums = { 2,5,8,1,0,9,10 };insertSort(nums);print(nums);system("pause");return 0;
}

插排优化-折半插入排序

  折半插入排序是对直接插入排序的优化，利用了二分法的思想。

代码：

#include<iostream>
using namespace std;
#include<vector>/*
折半插入排序
*/void BinsertSort(vector<int>& nums)//{ 5, 7, 3, 2, 8, 9 }
{int len = nums.size();//数组长度for (int i = 1; i < len; ++i){int low = 0, high = i - 1,mid;while (low <= high)//用来查询在哪一部分进行查找{mid = low + (high - low) / 2;if (nums[i] < nums[mid]) high = mid - 1;else low = mid + 1;}int temp = nums[i];for (int j = i; j > high+1; j--)//移动元素 {nums[j] = nums[j - 1];//前面的元素往后移}nums[high+1] = temp;}
}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){std::cout << *it << " ";}std::cout << std::endl;
}
int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 };BinsertSort(nums);print(nums);system("pause");return 0;
}

二、希尔排序

基本思想：

  先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

特点：

• 1）缩小增量

• 2）多遍插入排序

  希尔排序，本质上还是直接插入排序，只要是增加了一个增量序列。

#include<iostream>
using namespace std;
#include<vector>void shellSort(vector<int>& nums)
{int len = nums.size();int gap = len;while (gap > 1){gap /= 2;//每次迭代设置为一半for (int i = 0; i < len-gap; ++i){if (nums[i + gap] < nums[i]){int end = i;int temp = nums[end + gap];while (end >= 0 && temp < nums[end]){nums[end + gap] = nums[end];end-=gap;}nums[end + gap] = temp;}			}}}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){std::cout << *it << " ";}std::cout << std::endl;
}
int main()
{vector<int> nums = { 12, 7, 3, 2, 8, 9, 10, 21, 55, 15, 17 };shellSort(nums);print(nums);system("pause");return 0;
}

三、冒泡排序

  冒泡排序，应该是我们最熟悉的排序算法了，下面我稍微剖解一下：

  冒泡排序就是从首位元素开始，依次对相邻元素进行比较，如果前面的数比后面的数要大，就使这两个数进行交换，否则就不需要操作。

我们预设一个较小的数组 {$5,2,3,1$} ，数组长度为 $4$。
算法开始执行：用首位—5进行去和相邻元素 $2$ 比较有：
$5>2$，交换 $5$ 和 $2$ 得到数组{$2,5,3,1$}，再用 $5$ 和 $3$ 比较：
$5>3$，交换得到{$2,3,5,1$},再用 $5$ 和 $1$比较：
$5>1$，交换得到{$2,3,1,5$},至此没有元素和 $5$ 比较了，第一轮迭代结束
现在数组为：{$2,3,1,5$}
$2<3$，所以不做交换
$3>1$，交换得到{$2,1,3,5$}第二轮结束
现在数组为：{$2,1,3,5$}
$2>1$，交换得到{$1,2,3,5$}结束
现在我们知道目前外循环为 $3$ 层，即$nums.size()-1$
内循环则是依次递减：$nums.size()-1-i$层

代码：

#include<iostream>
using namespace std;
#include<vector>void bubbleSort(vector<int>& nums)
{int len = nums.size();for (int i = 0; i < len - 1; ++i){for (int j = 0; j < len - i - 1; ++j){if (nums[j]>nums[j + 1]){swap(nums[j], nums[j + 1]);}}}
}
void print(vector<int>& nums) {for (auto i : nums) {std::cout << i << " ";}std::cout << std::endl;
}
int main()
{vector<int> nums = { 5, 2, 3, 1 };bubbleSort(nums);print(nums);system("pause");return 0;
}

优化版本：

  冒泡排序的优点在于，不仅能把最大值挤到最后，还能同时部分理顺其他元素。

  怎么对它进行优化？

  我们发现，一旦某一趟比较时不出现记录，则说明已排好序，这时就可以结束本轮算法。所以我们可以设置一个是否有元素交换的额标志$flag$。

代码：

#include<iostream>
using namespace std;
#include<vector>void bubbleSort(vector<int>& nums)
{int len = nums.size();if (len < 2) return;for (int i = 0; i < len - 1; ++i){bool flag = 0;//开始初设置一个标志位falsefor (int j = 0; j < len - i - 1; ++j){if (nums[j]>nums[j + 1]){swap(nums[j], nums[j + 1]);flag = 1;//当发生交换，false变为true，这时还不确定数组是否全部有序，应进行下一次循环}}//但若某一趟中一次元素交换都没有，即依然为flag = false//那么表明所剩待排序列已经有序//不必再进行趟数比较，外层循环应该结束，即此时if (!flag) break; 跳出循环if (!flag){break;}}
}
void print(vector<int>& nums) 
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end();it++){std::cout << *it << " ";}std::cout << std::endl;
}
int main()
{vector<int> nums = { 5, 2, 3, 1 ,10 , 8 , 6 };bubbleSort(nums);print(nums);system("pause");return 0;
}

四、快速排序

  快速排序和冒泡排序都属于交换排序，利用元素之间的交换来进行排序。

基本思想：

• 任取一个元素（如：第一个）为中心

• 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表。

• 对各字表重新选择中心元素并依此规则调整。（递归思想）

• 直到每个子表的元素只剩一个

  具体理论可以参考王卓老师讲的快速排序

#include<iostream>
using namespace std;
#include<vector>/*
快速排序
*/void quickSort(vector<int>& nums,int low,int high)//{ 12, 7, 3, 2, 8, 9, 10, 21, 55, 15, 17 }
{if (low >= high){return;}int len = nums.size();//数组长度int left = low;//左指针指向，左-》右int right = high;//右指针指向，右-》左//选择最左边数据为key，右指针先走，选择最右边数据为Key，左指针先走int key = nums[low];//选出一个key一般为最左或最右/*走的过程中*/while (left < right)//left==right退出循环{//从后往前走，将比基准小的移到前面while (left < right && nums[right]>key){right--;}if (left < right){nums[left++] = nums[right];}//从前往后走，将比第一个大的移到后面while (left < right&&nums[left] <= key){left++;}if (left < right){nums[right--] = nums[left];}nums[left] = key;//递归key前部分quickSort(nums, low, left - 1);//递归key后部分quickSort(nums, left + 1, high);}
}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){std::cout << *it << " ";}std::cout << std::endl;
}int main()
{vector<int> nums = { 12, 7, 3, 2, 8, 9, 10, 21, 55, 15, 17 };int low = 0;int high = nums.size()-1;quickSort(nums, low, high);print(nums);system("pause");return 0;
}

五、选择排序

  什么是选择排序？

  选择排序是从头到尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

#include<iostream>
using namespace std;
#include<vector>void selectSort(vector<int>& nums)
{int minIndex = 0;int len = nums.size();for (int i = 0; i < len; i++){minIndex = i;for (int j = i + 1; j < len; j++){if (nums[j] < nums[minIndex]) minIndex = j;}swap(nums[i], nums[minIndex]);}
}void print(vector<int>& nums)
{for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){std::cout << *it << " ";}std::cout << std::endl;
}
int main()
{vector<int> nums = { 10, 3, 5, 4, 2, 6 };selectSort(nums);print(nums);system("pause");return 0;
}

六、归并排序

  归并排序（Merge Sort）就是将已经有序的子数列合并，得到另一个有序的数列。

  归并排序也就是合并排序。

#include<iostream>
using namespace std;
#include<vector>
/*
归并排序
*///递归
void _mergeSort(vector<int>& nums,vector<int>& nums_temp,int start,int end)
{if (start >= end) return;//表示区间元素小于两个，递归终止int mid = start + (end - start) / 2;//计算排序区间中间的位置int start1 = start, end1 = mid;//区间左边元素的第一和最后一个元素的位置int start2 = mid + 1, end2 = end;//区间右边元素的第一和最后一个元素的位置_mergeSort(nums_temp, nums, start1, end1);//对区间左边元素递归排序_mergeSort(nums_temp, nums, start2, end2);//对区间右边元素递归排序int j = start;//已排序数组nums_temp的计数器//将区间左右两边数组合并到已排序数组中while (start1 <= end1 && start2 <= end2){if (nums[start1] < nums[start2]){nums_temp[j] = nums[start1];j++;start1++;}else{nums_temp[j] = nums[start2];j++;start2++;}}//把左边数列其它的元素追加到已排序数组while (start1 <= end1){nums_temp[j] = nums[start1];j++;start1++;}while (start2 <= end2){nums_temp[j] = nums[start2];j++;start2++;}}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 ,10,1,11 };vector<int>nums_temp(nums);_mergeSort(nums, nums_temp, 0, nums.size() - 1);nums.assign(nums_temp.begin(), nums_temp.end());print(nums);system("pause");return 0;
}

迭代版

#include<iostream>
using namespace std;
#include<vector>/*
归并排序
*/void mergeSort(vector<int>& nums,vector<int>& nums_temp,int len)
{if (len < 2) return;//表示区间元素小于两个，递归终止int seg;//区间分段的计数器，1,2,4,8...int start;//区间起始的计时器//排序的趟数的循环for (seg = 1; seg < len; seg = seg * 2){//每趟排序选取区间的循环for (start = 0; start < len; start = start + seg * 2){//把每个区间分成两部分，low1是起始位置，mind1是中间位置,high1是结束位置int low = start;int mid = min(start + seg, len);//考虑分段不均的情况，mid1不能超出lenint high = min(start + seg * 2, len);int j = low;//已排序数组的计数器int start1 = low, end1 = mid;int start2 = mid, end2 = high;//把待排序左右两边数列合并到已排序数组while (start1 < end1 && start2 < end2){nums_temp[j++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];}while (start1 < end1){nums_temp[j++] = nums[start1++];}while (start2 < end2){nums_temp[j++] = nums[start2++];}}swap(nums, nums_temp);}}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 ,10,1,11 };int len = nums.size();vector<int> nums_temp(len, 0);mergeSort(nums,nums_temp,len);print(nums);system("pause");return 0;
}

七、堆排序

  堆排序是利用堆这种数据结构设计的排序算法，堆具备以下特点：

• 1）完全二叉树

• 2）大顶堆：二叉树根结点值都大于或等于其左右子树结点的值

• 3）小顶堆：根结点的值都小于或等于其左右子树结点的值。

二叉树的性质：

  在第一个元素的索引为 0 的情形中：

性质一：

  索引为 $i$ 的左孩子的索引是$(2\ast i+1)$;

性质二：

  索引为 $i$ 的左孩子的索引是$(2\ast i+2)$;

性质三：

  索引为 $i$ 的父结点的索引是$floor((i-1)/2)$;

基本思路：

• $Step1$：建立大根堆,将n个元素组成的无序序列构建一个大顶堆。

  从最后一个叶子节点开始，从左到右，从下到上调整，将完全二叉树调整为大顶堆。

  1.找到第一个非叶子结点4，由于4的左结点7比4大，所以交换4和7，交换后为大顶堆结构。

  2.找到第二个非叶子结点6，由于6的右结点8比6大，所以交换6和8，交换后符合大顶堆结构。

• $Step2$：交换堆元素，交换堆尾元素和堆首元素，使堆尾元素为最大元素；

• $Step3$：重建大根堆，将前$n-1$个元素组成的无序序列调整为大顶堆。

• $Step4$：重复执行步骤二和步骤三，直到整个序列有序

堆排序（升序排序）

代码1：

#include<iostream>
using namespace std;
#include<vector>/*
堆排序
*//** (最大)堆的向下调整算法** 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。*     其中，N为数组下标索引值，如数组中第1个数对应的N为0。** 参数说明：*     nums -- 待排序的数组*     index -- 第一个非叶子点的下标*	   *///构造大顶堆	
void maxheap_down(vector<int>&nums,int len,int index)
{int left = 2 * index + 1;//左(left)孩子的位置int right = 2 * index + 2;//右(right)孩子的位置int maxIdx = index;//默认当前结点为最大if (left<len && nums[left]>nums[maxIdx]) maxIdx = left;if (right<len && nums[right]>nums[maxIdx]) maxIdx = right;if (maxIdx != index){swap(nums[maxIdx], nums[index]);maxheap_down(nums,len, maxIdx);}
}void heapSort(vector<int>& nums,int size)
{//构建大顶堆for (int i = size/2 - 1; i >= 0; i--){maxheap_down(nums, size,i);}//调制大顶堆for (int i = size - 1; i >= 1; i--){swap(nums[0], nums[i]);maxheap_down(nums, i, 0);}
}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 ,10,1,11 };int size = nums.size();heapSort(nums, size);print(nums);system("pause");return 0;
}

八、计数排序

  计数排序就是对一个待排序的数组进行排序，将结果一个一个放在一个申请的空间内。

排序方法：

  计数排序每次都将查询整个待排序数组，自第一位数到最后一位，每次找出整个待排序数组内大于（小于）当前待排数的个数 $count$。然后将当前待排数放入到新数组的第$count+1$位。

基本思想：

代码：

#include<iostream>
using namespace std;
#include<vector>/*
计数排序
*/int _max(vector<int>& nums, int len)
{int max = nums[0];//确定最大值for (int i = 1; i < len; ++i){if (nums[i] > max){max = nums[i];}}return max;
}void countSort(vector<int>& nums, int len)
{if (len < 2) return;int max = _max(nums, len);//确认统计数组长度并初始化vector<int>nums_temp(max + 1, 0);for (int i = 0; i < len; i++){++nums_temp[nums[i]];}// 排序数组，某个数出现了几次，便在nums里累计输出几次int index = 0;for (int i = 0; i <= max; ++i){for (int j = 0; j < nums_temp[i]; ++j){nums[index] = i;index++;}}
}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 ,10,1,11 };int len = nums.size();countSort(nums, len);print(nums);system("pause");return 0;
}

九、桶排序

  桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间$（\Theta （n））$。但桶排序并不是比较排序，他不受到$O(nlogn)$ 下限的影响。

代码：

#include <iostream>
using namespace std;
#include<vector>
const int offset = 50; 
const int maxSize = 40; void BucketSort(vector<int>&nums, int n) 
{int i, j;vector<int> buckets(offset);for (i = 0; i < offset; i++) // 清零buckets[i] = 0;// 1.计数,将数组arr中的元素放到桶中for (i = 0; i < n; i++)buckets[nums[i]]++; // 将arr[i]的值对应buckets数组的下标，每有一个就加1// 2.排序for (i = 0, j = 0; i < offset; i++) {while (buckets[i] > 0) { // 说明存有元素,相同的整数，要重复输出nums[j] = i;buckets[i]--;j++;}}
}// 输出数组
void Print(vector<int>& nums, int n) {int i;for (i = 0; i < n; i++)cout << nums[i] << " ";cout << endl;
}int main(int argc, const char* argv[]) {int n, i;vector<int> nums = { 5, 7, 3, 2, 8, 9 };cout << "请输入要排序的数的个数：";cin >> n;srand((int)time(NULL)); // 设置时间为随机点for (i = 0; i < n; i++) // 产生n个随机数nums[i] = rand() % 100;cout << "排序前：";Print(nums, n);BucketSort(nums, n); // 调用桶排序cout << "排序后：";Print(nums, n);return 0;
}

十、基数排序

  基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基本思想：

  基数排序的思想是将整数按位数切割成不同的数字，然后按每个位数分别比较从而得到有序的序列。

代码：

#include<iostream>
using namespace std;
#include<vector>int _max(vector<int>& nums, int len)
{int max = nums[0];//确定最大值for (int i = 1; i < len; ++i){if (nums[i] > max){max = nums[i];}}return max;
}
//e-排数的指数，e=1，按个位排，e=10，按10位排void _radixSort(vector<int>& nums, int len, int e)
{vector<int> temp(len);//存放从桶中收集后数据的临时数组vector<int> buckets(10, 0);//初始化10个桶//遍历nums,将数据出现的次数存储在buckets中。for (int i = 0; i < len; i++){buckets[(nums[i] / e) % 10]++;}//调整buckets个元素的值for (int i = 1; i < 10; i++){buckets[i] = buckets[i] + buckets[i - 1];}for (int i = len - 1; i >= 0; i--){int e1 = (nums[i] / e) % 10;temp[buckets[e1] - 1] = nums[i];buckets[e1]--;}nums.assign(temp.begin(), temp.end());
}void radixSort(vector<int>& nums, int len)
{int max = _max(nums, len);//int e1;//排序指数for (int e1 = 1; max / e1 > 0; e1 = e1 * 10){_radixSort(nums, len, e1);}
}void print(vector<int>& nums)
{/*for (auto i : nums)*/for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++){cout << *it << " ";}cout << endl;
}
int main()
{vector<int> nums = { 5, 7, 3, 2, 8, 9 };int len = nums.size();radixSort(nums,len);print(nums);system("pause");return 0;
}

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！本文尚有瑕疵，我会逐渐补全。