【排序算法收录】这次别忘了

• 排序算法分类
  
  • 时间复杂度O(n^2)
    
    • 冒泡排序
      
  • //第一种写法： O(n^2)
  • void bubbleSort_1(vector& nums) {
  • int n = nums.size();
  • for (int i = 0; i < n - 1; ++i)
  • for (int j = 0; j < n - i - 1; ++j)
  • if (nums[j] > nums[j + 1])
  • swap(nums[j], nums[j + 1]);
  • }
  • 
    
  • //第二种写法：O(n^2)，最好的情况下O(n)
  • void bubbleSort_2(vector& nums) {
  • int n = nums.size();
  • bool swapped = true;
  • for (int i = 0; i < n - 1; ++i) {
  • if (swapped == false)
  • break;
  • swapped = false;
  • for (int j = 0; j < n - i - 1; ++j)
  • if (nums[j] > nums[j + 1]) {
  • swap(nums[j], nums[j + 1]);
  • swapped = true;
  • }
  • }
  • }
  • 
    
  • //第三种写法：O(n^2)，最好的情况下O(n)
  • void bubbleSort_3(vector& nums) {
  • bool swapped = true;
  • int lastIndexOfUnsortedElem = nums.size() - 1;
  • while (swapped) {
  • swapped = false;
  • for (int i = 0; i < lastIndexOfUnsortedElem; ++i)
  • if (nums[i] > nums[i + 1]) {
  • swap(nums[i], nums[i + 1]);
  • swapped = true;
  • }
  • }
  • }
    • 选择排序
      
  • //选择排序:O(n^2)，空间复杂度O(1)
  • //将第i个最小值放在第i轮循环的最前面
  • //不稳定
  • void selectionSort(vector& nums) {
  • int n = nums.size();
  • int minIndex;
  • for (int i = 0; i < n - 1; ++i) {
  • minIndex = i;
  • for (int j = i + 1; j < n; ++j)
  • if (nums[minIndex] > nums[j])
  • minIndex = j;
  • swap(nums[i], nums[minIndex]);
  • }
  • }
  • 
    
  • //二元选择排序：同时记录最小值和最大值
  • void selectionSort_double(vector& nums) {
  • int n = nums.size();
  • int minIndex, maxIndex;
  • //i只需要遍历一半
  • for (int i = 0; i < n / 2; ++i) {
  • minIndex = i;
  • maxIndex = i;
  • for (int j = i + 1; j < n - i; ++j) {
  • //最小值下标
  • if (nums[minIndex] > nums[j])
  • minIndex = j;
  • //最大值下标
  • if (nums[maxIndex] < nums[j])
  • maxIndex = j;
  • }
  • //最大最小下标相等，则必定等于i，全数组大小相同
  • if (minIndex == maxIndex) break;
  • //最小的元素交换到首位
  • swap(nums[minIndex], nums[i]);
  • //若最大元素的下标为i，由于nums[i]和nums[minIndex]已交换，则更新maxIndex的值
  • if (i == maxIndex) maxIndex = minIndex;
  • int LastIndex = n - 1 - i;
  • swap(nums[maxIndex], nums[LastIndex]);
  • }
  • }
    • 插入排序
      
  • //插入排序，稳定
  • //时间复杂度：O(n^2)；空间复杂度O(1)
  • void insertionSort(vector& nums) {
  • int n = nums.size();
  • for (int i = 1; i < n; ++i) {
  • int curNum = nums[i];
  • int j = i - 1;
  • while (j >= 0 && nums[j] > curNum) {
  • nums[j + 1] = nums[j];
  • —j;
  • }
  • nums[j + 1] = curNum;
  • }
  • }
  • 时间复杂度O(nlogn)
    
    • 快速排序（非常重要）
      
• //快速排序，不稳定
• //时间复杂度：平均O(nlogn)，最坏O(n^2)
• //空间复杂度：平均O(logn)，最坏O(n)
  • void quickSort(vector& nums, int start, int end) {
  • if (start >= end)
  • return;
  • int pivot = nums[start];
  • int l = start, r = end;
  • while (l < r) {
  • while (l < r && nums[r] >= pivot)
  • —r;
  • while (l < r && nums[l] <= pivot)
  • ++l;
  • if (l < r)
  • swap(nums[l], nums[r]);
  • }
  • swap(nums[start], nums[l]);
  • quickSort(nums, start, l - 1);
  • quickSort(nums, l + 1, end);
  • }
    • 归并排序
      
  • //归并排序，稳定
  • //时间复杂度:O(nlogn)，空间复杂度：O(n)
  • void mergeSort(vector& nums) {
  • int n = nums.size();
  • if (n == 0) return;
  • vector res(n);
  • mergeSort(nums, 0, n - 1, res);
  • }
  • //对nums[start…end]的区间排序
  • void mergeSort(vector& nums, int start, int end, vector& res) {
  • if (start == end)
  • return;
  • int mid = (start + end) / 2;
  • mergeSort(nums, start, mid, res);
  • mergeSort(nums, mid + 1, end, res);
  • }
  • //合并res的[start…mid]和[mid + 1…end]
  • void merge(vector& nums, int start, int end, vector& res) {
  • int end1 = (start + end) / 2;
  • int start2 = end1 + 1;
  • int idx1 = start, idx2 = start2;
  • while (idx1 <= end1 && idx2 <= end) {
  • if (nums[idx1] <= nums[idx2])
  • res[idx1 + idx2 - start2] = nums[idx1++];
  • else
  • res[idx1 + idx2 - start2] = nums[idx2++];
  • }
  • while (idx1 <= end1)
  • res[idx1 + idx2 - start2] = nums[idx1++];
  • while (idx2 <= end)
  • res[idx1 + idx2 - start2] = nums[idx2++];
  • //将res[start..end]拷贝回nums数组中
  • while (start <= end)
  • nums[start] = res[start++];
  • }
    • 堆排序
      
    • 希尔排序