前言：这篇文章总结一下学习的几种排序算法，假设要对一个 vector
1、冒泡排序
思想：冒泡排序的思想就是一共进行 n - 1 次循环，每次循环把范围内最小的数冒到最后面。
因此用内为双循环，外循环为冒泡的次数，内循环为每次冒泡的范围，通过比较和交换操作将最小值移到后面。
1 // 第一个循环表示一共要泡几次
2 // 第二个循环是冒泡
3 for (int i = 0; i < nums.size() - 1; ++i) {
4 for (int j = 0; j < nums.size() -i; ++j) {
5 if (nums[j] < nums[j + 1]) {
6 int temp = nums[j];
7 nums[j] = nums[j + 1];
8 nums[j + 1] = temp;
9 }
10 }
11 }
2、简单选择排序
思想：简单选择排序非常粗暴！原理就是一共进行 n - 1 次循环，每次循环在范围内找到最大的数，然后把它移到前面！
同样是内外双循环，外循环为选择排序的次数，内循环每次找到范围内最大值，然后交换到最前面。
1 // 外循环为选择的次数
2 // 内循环为具体的选择操作
3 for(int i = 0; i < nums.size() - 1; ++i) {
4 int max = i;
5 for (int j = i + 1; j < nums.size(); ++j) {
6 if (nums[j] > nums[i]) {
7 max = j;
8 }
9 }
10 if (max != i) {
11 int temp = nums[i];
12 nums[i] = nums[max];
13 nums[max] = temp;
14 }
15 }
3、直接插入排序
思想：直接插入排序的原理是当循环到下标 i 时，范围 [0,i-1] 已经保证有序，然后判断 nums[i] 是否大于 nums[i-1]，如果是，则往回找到第一个元素下标 j ，使得 nums[j] >= nums[i]，然后把 [j+1,i-1] 范围内元素后移一位，nums[j+1] = nums[i]。
1 // 直接插入排序（原型）
2 for (int i = 1; i < nums.size(); ++i) {
3 if (nums[i] > nums[i - 1]) {
4 int temp = nums[i];
5 int j;
6 for (j = i - 1; j >= 0 && nums[j] < temp; --j) {
7 nums[j + 1] = nums[j];
8 }
9 nums[j + 1] = temp;
10 }
11 }
4、希尔排序
思想：希尔排序是直接插入排序的改进。其原理是先设置一个阈值宽度，在这个范围内进行直接插入排序，使数组处于大致有序的状态（大的数基本在前面，中间的数基本在中间，小的数基本在后面）。
然后不断缩小阈值宽度直到它等于 1，此方法可以减少移动次数，因此效率上要优于直接插入排序。
1 // 希尔排序（改进）
2 int index = nums.size();
3 do {
4 index = index / 3 + 1;
5 for (int i = index; i < nums.size(); ++i) {
6 if (nums[i] > nums[i - index]) {
7 int temp = nums[i];
8 int j;
9 for (j = i - index; j >= 0 && nums[j] < temp; j -= index) {
10 nums[j + index] = nums[j];
11 }
12 nums[j + index] = temp;
13 }
14 }
15 } while (index > 1);
5、堆排序
思想：堆排序是简单选择排序的改进，其原理是首先把数组构造成一个小顶堆，然后每次将第一个元素与范围内最后一个元素交换，并重新构造小顶堆...
注意事项：构造小顶堆时，break 的条件不能有 = 。
1 // 将数组构造成小顶堆
2 for (int i = nums.size()/2 - 1; i >= 0; --i) {
3 heapadjust(nums,i,nums.size() - 1);
4 }
5
6 // 堆排序，每次把最小的数移到最后面，然后重新构造堆
7 for (int i = nums.size() - 1; i > 0; --i) {
8 swap(nums,0,i);
9 heapadjust(nums,0,i-1);
10 }
11
12 // 构造小顶堆算法
13 void heapadjust(std::vector
14 int temp = nums[i];
15 for (int j = i * 2 + 1; j <= n; j = j * 2 + 1) {
16 if (j <= n - 1 && nums[j] > nums[j + 1]) {
17 ++j;
18 }
19 // 这里不能大于等于
20 if (nums[j] > temp) {
21 break;
22 }
23 nums[i] = nums[j];
24 i = j;
25 }
26 nums[i] = temp;
27 }
28
29 void swap(std::vector
30 int temp = nums[i];
31 nums[i] = nums[j];
32 nums[j] = temp;
33 }
6、归并排序
思想：归并排序用到了分治的思想。将待排序的数组分为两个子数组各自排序，子数组排好后合并到一起即可。注意划分字数组的时候的返回条件，当左端点大于等于右端点时，直接返回！
1 // nums2是一个中间变量，nums划分为两个有序子数组后，并入到nums2里面，然后再赋值给nums
2 std::vector
3 sort(nums,nums2,0,nums.size()-1);
4
5 // 归并排序算法
6 void sort(std::vector
7 if (l >= r) {
8 return;
9 }
10 int m = l + (r - l) / 2;
11 sort(nums1, nums2, l, m);
12 sort(nums1, nums2, m + 1, r);
13 int k = l, ptr1 = l, ptr2 = m + 1;
14 while (ptr1 <= m && ptr2 <= r) {
15 nums2[k++] = nums1[ptr1] > nums2[ptr2] ? nums1[ptr1++] : nums2[ptr2++];
16 }
17 while (ptr1 <= m) {
18 nums2[k++] = nums1[ptr1++];
19 }
20 while (ptr2 <= r) {
21 nums2[k++] = nums1[ptr2++];
22 }
23 for (int i = l; i <= r; ++i) {
24 nums1[i] = nums2[i];
25 }
26 }
7、快速排序
思想：快速排序的思想是先选取一个中间数，然后通过交换操作将数组分为两个部分，大于等于中间数的数都在中间数的左边，小于等于中间数的数都在中间数的右边。然后对这两个区域分别进行快速排序。
具体的，每次就选取区域内的第一个元素作为中间数！
1 // 对数组作快速排序
2 quicksort(nums,0,nums.size()-1);
3
4 // 快速排序算法
5 void quicksort(std::vector
6 if (l >= r) {
7 return;
8 }
9 int m = getmid(nums,l,r);
10 quicksort(nums,l,m-1);
11 quicksort(nums,m+1,r);
12 }
13
14 // 将区域分为两部分，同时返回中间数下标
15 int getmid(std::vector
16 int index = nums[l];
17 while (l < r) {
18 while (l < r && nums[r] <= index) {
19 r--;
20 }
21 swap(nums,l,r);
22 while (l < r && nums[l] >= index) {
23 l++;
24 }
25 swap(nums,l,r);
26 }
27 return l;
28 }
29
30 void swap(std::vector
31 int temp = nums[i];
32 nums[i] = nums[j];
33 nums[j] = temp;
34 }