排序相关

全部评论 2

• 

  hjh-研究员版

  删除

  归并排序

  #include<bits/stdc++.h>
  using namespace std;
  using i64 = long long;
  i64 cnt = 0;
  
  void gb_sort(vector<int> &v, int l, int r, vector<int> &tmp) {
      if (l == r) return;
      int mid = (l + r) / 2;
      gb_sort(v, l, mid, tmp);
      gb_sort(v, mid + 1, r, tmp);
      int i = l, j = mid + 1, t = l;
      while (i <= mid && j <= r) {
          if (v[i] <= v[j]) {
              cnt += (j - mid - 1);
              tmp[t++] = v[i++];
          } else {
              tmp[t++] = v[j++];
          }
      }
      while (i <= mid) {
          cnt += (j - mid - 1);
          tmp[t++] = v[i++];
      }
      while (j <= r) { tmp[t++] = v[j++]; }
      for (i = l; i <= r; i++) {
          v[i] = tmp[i];
      }
  }
  
  int main() {
      int n;
      cin >> n;
      vector<int> v(n + 1);
      vector<int> tmp(n + 1);
      for (int i = 1; i <= n; i++)cin >> v[i];
      gb_sort(v, 1, n, tmp);
      for (int i = 1; i <= n; i++) {
          cout << v[i] << " ";
      }
      cout << endl;
  }
  
  

  11小时前 来自 浙江

  0
• 

  hjh-研究员版

  删除

  快速排序

  #include <bits/stdc++.h>
  using namespace std;
  // 分区函数（索引从 1 开始）
  int partition(std::vector<int> &arr, int low, int high) {
      int pivot = arr[high]; // 选择最后一个元素作为基准
      int i = low - 1; // i 是小于基准的元素的右边界
  
      for (int j = low; j < high; j++) {
          if (arr[j] < pivot) {
              i++;
              std::swap(arr[i], arr[j]); // 交换元素
          }
      }
      // 将基准放到正确位置
      std::swap(arr[i + 1], arr[high]);
      return i + 1; // 返回基准的索引
  }
  
  // 快速排序主函数（索引从 1 开始）
  void quickSort(std::vector<int> &arr, int low, int high) {
      if (low < high) {
          int pi = partition(arr, low, high); // 获取分区点
          quickSort(arr, low, pi - 1); // 递归排序左半部分
          quickSort(arr, pi + 1, high); // 递归排序右半部分
      }
  }
  
  // 示例用法（索引从 1 开始）
  int main() {
      int n;
      cin >> n;
      vector<int> arr(n + 1);
      for (int i = 1; i <= n; i++) cin >> arr[i];
  
      quickSort(arr, 1, n);
  
  
      for (int i = 1; i <= n; i++) {
          std::cout << arr[i] << " ";
      }
      std::cout << std::endl;
  
      return 0;
  }
  

  11小时前 来自 浙江

  0