整数排序 II 题解集合

归并排序是一种高效的排序算法，其时间复杂度为 O(n log n)，能够在 O(n log n) 的时间内完成对 n 个元素的排序工作。本文将介绍归并排序的实现方法，并对其进行优化以避免超时问题。

归并排序

归并排序采用递归的方式将数组分成若干个子序列进行处理。下面是归并排序的实现代码：

#include 
   
    using namespace std;class Solution {public:  void merge(vector
    
      &A, int begin, int mid, int end, vector
     
       &temp) {    int i = begin, j = mid + 1, k = 0;    while (i <= mid && j <= end) {      if (A[i] < A[j]) {        temp[k++] = A[i++];      } else {        temp[k++] = A[j++];      }    }    while (i <= mid) {      temp[k++] = A[i++];    }    while (j <= end) {      temp[k++] = A[j++];    }    for (int i = 0; i < k; ++i) {      A[begin + i] = temp[i];    }  }  void mergeSort(vector
      
        &A, int begin, int end) {    static vector
       
         temp(A.size(), 0);    if (begin < end) {      int mid = (begin + end) / 2;      mergeSort(A, begin, mid);      mergeSort(A, mid + 1, end);      merge(A, begin, mid, end, temp);    }  }  void sortIntegers2(vector
        
          &A) { mergeSort(A, 0, A.size() - 1); }};

注意事项：

上述代码在递归实现中使用了额外的 temp 数组来存储中间结果。

归并排序的时间复杂度为 O(n log n)，但在实际应用中，如果输入数据量较大，递归实现可能会导致栈溢出。为此，建议采用迭代实现或者改用非递归归并排序。

归并排序迭代版本

为了避免递归实现导致的栈溢出问题，以下是归并排序的迭代版本代码：

#include 
   
    using namespace std;class Solution {public:  void merge(vector
    
      &A, int begin, int mid, int end, vector
     
       &temp) {    int i = begin, j = mid + 1, k = 0;    while (i <= mid && j <= end) {      if (A[i] < A[j]) {        temp[k++] = A[i++];      } else {        temp[k++] = A[j++];      }    }    while (i <= mid) {      temp[k++] = A[i++];    }    while (j <= end) {      temp[k++] = A[j++];    }    for (int i = 0; i < k; ++i) {      A[begin + i] = temp[i];    }  }  void mergeSortIterative(vector
      
        &A) {    int n = A.size();    int m = 1;    int k = 1;    int First = 0;    int Last = n;    // 检查是否需要归并    while (k < n) {      // 合并前半部分      while (First <= Last - 2 * k + 1) {        int midSub = First + k - 1;        LastSub = First + 2 * k - 1;        merge(A, First, midSub, LastSub, temp);        First += 2 * k;      }      // 处理剩下的元素      if (Last - First <= k) {        // 两个子区间合并        int mid = First + (Last - First) / 2;        merge(A, First, mid, Last, temp);      } else {        int mid = First + k - 1;        merge(A, First, mid, Last, temp);      }      k *= 2;    }  }  void sortIntegers2(vector
       
         &A) {    int n = A.size();    vector
        
          temp(n, 0); int k = 1; int First = 0; int Last = n; while (k < n) { // 合并前半部分 while (First <= Last - 2 * k + 1) { int mid = First + k - 1; Last = First + 2 * k-1; merge(A, First, mid, Last, temp); First += 2 * k; } // 处理剩下的元素 if (Last - First <= k) { int mid = First + (Last - First)/2; merge(A, First, mid, Last, temp); } else { int mid = First + k -1; merge(A, First, mid, Last, temp); } k *= 2; } // 处理单个元素 if (First == Last) { merge(A, First, Last-1, Last, temp); } }};

优化说明：

和传统的递归归并排序不同，该迭代实现采用非递归方式避免了栈溢出的问题。

通过将数组分成多个小块并逐步归并，最终达到整体排序的目的。

快速排序

快速排序是一种高效的排序算法，平均时间复杂度为 O(n log n)，最坏时间复杂度为 O(n²)。以下是快速排序的实现代码：

#include 
   
    #include 
    
     using namespace std;class Solution {public:  void sortIntegers2(vector
     
       &A) {    if (A.size() <= 1) return;    quick_sort(A, 0, A.size() -1);  }  int partition(vector
      
        &r, int begin, int end) {    int i = begin;    int j = end;    // 找到等于或小于的最右边元素    while (i < j && r[i] <= r[j]) {      i++;    }    if (i == j) return i;    // 找到大于等于当前键值的最左边元素    while (i < j && r[i] >= r[j]) {      j--;    }    if (i == j) return i;    // 交换元素位置    swap(r[i], r[j]);    return i;  }  void quick_sort(vector
       
         &r, int begin, int end) {    if (begin >= end) return;    int pos = swap_sort(r, begin, end);    quick_sort(r, begin, pos -1);    quick_sort(r, pos + 1, end);  }  int swap_sort(vector
        
          &r, int begin, int end) { int i = begin; int j = end; while (i < j) { while (i < j && r[i] <= r[j]) { j--; } if (i < j) { swap(r[i], r[j]); i++; } while (i < j && r[j] >= r[i]) { i++; } if (i < j) { swap(r[i], r[j]); j--; } } return i; }};

优化说明：

快速排序的核心在于找到一个基准元素（pivot），将数组划分为小于基准和大于基准的两部分，然后递归排序这两部分。

通过合理选择基准元素（如随机选择、中位数选择等），可以减少最坏情况下的时间复杂度，提高整体性能。

本文详细介绍了归并排序、快速排序等多种整数排序算法的实现及其优化方法。如果你对某种算法有更多疑问，欢迎在评论区留言，我会在后续内容中进行补充说明。

转载地址：http://lygqz.baihongyu.com/

你可能感兴趣的文章