【Leetcode刷题记录】各种排序算法

前言：这篇文章总结一下学习的几种排序算法，假设要对一个 vector<int> 数组进行降序排序，数组中一共有 n 个数。

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<int>& nums, int i, int n) {
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<int>& nums, int i, int j) {
30     int temp = nums[i];
31     nums[i] = nums[j];
32     nums[j] = temp;
33 }

6、归并排序

思想：归并排序用到了分治的思想。将待排序的数组分为两个子数组各自排序，子数组排好后合并到一起即可。注意划分字数组的时候的返回条件，当左端点大于等于右端点时，直接返回！

 1 // nums2是一个中间变量，nums划分为两个有序子数组后，并入到nums2里面，然后再赋值给nums
 2 std::vector<int> nums2 = nums;
 3 sort(nums,nums2,0,nums.size()-1);
 4 
 5 // 归并排序算法
 6 void sort(std::vector<int>& nums1, std::vector<int>& nums2, int l, int r) {
 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<int>& nums, int l, int r) {
 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<int>& nums, int l, int r) {
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<int>& nums, int i, int j) {
31     int temp = nums[i];
32     nums[i] = nums[j];
33     nums[j] = temp;
34 }