[关闭]
@cleardusk 2016-09-28T17:21:14.000000Z 字数 2191 阅读 1140

逆序数寻找

雁栖湖 算法设计与分析


快速排序思想

Code

  1. #include <iostream>
  2. #include "gjz_timer.h"
  3. size_t rc = 0; // use size_t to avoid overflow
  4. const int N = 1000000;
  5. int tmp_ll[N], tmp_lr[N], tmp_rl[N], tmp_rr[N];
  6. int partition(int arr[], int l, int r) {
  7. int mid = l + (r - l) / 2;
  8. int pivot = arr[mid];
  9. // int *tmp_ll = NULL, *tmp_lr = NULL, *tmp_rl = NULL, *tmp_rr = NULL;
  10. size_t ll = 0, lr = 0, rl = 0, rr = 0;
  11. // left
  12. int i = 0;
  13. if (l < mid) {
  14. // int n = mid - l;
  15. // tmp_ll = new int[n];
  16. // tmp_lr = new int[n];
  17. for (i = mid - 1; i >= l; --i) {
  18. if (arr[i] < pivot)
  19. tmp_ll[ll++] = arr[i];
  20. else {
  21. tmp_lr[lr++] = arr[i];
  22. rc = rc + ll + 1; // the 1 is for the pivot
  23. }
  24. }
  25. }
  26. // right
  27. if (r > mid) {
  28. // int n = r - mid;
  29. // tmp_rl = new int[n];
  30. // tmp_rr = new int[n];
  31. for (i = mid + 1; i <= r; ++i) {
  32. if (arr[i] > pivot)
  33. tmp_rr[rr++] = arr[i];
  34. else {
  35. tmp_rl[rl++] = arr[i];
  36. rc = rc + rr + 1; //the 1 is for the pivot
  37. }
  38. }
  39. }
  40. rc = rc + lr * rl; // left * right
  41. // return the pivot
  42. int k = l;
  43. for (i = ll - 1; i >= 0; --i) arr[k++] = tmp_ll[i];
  44. for (i = 0; i < rl; ++i) arr[k++] = tmp_rl[i];
  45. int part = k; // get the part number
  46. arr[k++] = pivot;
  47. for (i = lr - 1; i >= 0; --i) arr[k++] = tmp_lr[i];
  48. for (i = 0; i < rr; ++i) arr[k++] = tmp_rr[i];
  49. // free memory
  50. // delete[] tmp_ll, tmp_lr, tmp_rl, tmp_rr;
  51. return part;
  52. }
  53. void quick_sort(int arr[], int l, int r) {
  54. if (l >= r) return;
  55. int part = partition(arr, l, r);
  56. quick_sort(arr, l, part - 1);
  57. quick_sort(arr, part + 1, r);
  58. }
  59. void _print(int arr[], int n) {
  60. for (int i = 0; i < n; ++i)
  61. std::cout << arr[i] << " ";
  62. std::cout << std::endl;
  63. }
  64. void test_easy() {
  65. // int arr[] = {1, 3, 2, 4, 5, 7, 6, 8};
  66. // int arr[] = {8, 5, 6};
  67. int arr[] = {6, 7, 4, 2, 1, 3, 5, 12, 8, 10};
  68. int sz = sizeof(arr) / sizeof(arr[0]);
  69. quick_sort(arr, 0, sz - 1);
  70. std::cout << rc << std::endl;
  71. _print(arr, sz);
  72. }
  73. void test_middle() {
  74. int A[1000000], i = 0, n = 0;
  75. while (~std::scanf("%d", &A[i++])) ++n;
  76. GjzTimer gjz_timer;
  77. quick_sort(A, 0, n - 1);
  78. gjz_timer.print_elaps("Cost");
  79. std::cout << rc << std::endl;
  80. }
  81. int main() {
  82. test_easy();
  83. //test_middle();
  84. }

若不需要 gjz_timer.h,注释掉即可。下面是 gjz_timer.h 代码.

  1. #ifndef _GJZ_TIMER_H
  2. #define _GJZ_TIMER_H
  3. /*
  4. * A small but useful timer
  5. * [4/18/2016 by gjz]
  6. */
  7. #include <ctime>
  8. class GjzTimer {
  9. public:
  10. GjzTimer() : _beg(clock()) {}
  11. ~GjzTimer() {}
  12. void reset() {
  13. _beg = clock();
  14. }
  15. const double elapsed() {
  16. _second = clock();
  17. return (_second - _beg) / double(CLOCKS_PER_SEC) * 1000;
  18. }
  19. void print_elaps(const std::string &info) {
  20. std::printf("%s: %.2f ms\n", info.c_str(), elapsed());
  21. }
  22. void print_elaps_reset(const std::string &info) {
  23. std::printf("%s: %.2f ms\n", info.c_str(), elapsed());
  24. reset();
  25. }
  26. private:
  27. clock_t _beg;
  28. clock_t _second;
  29. };
  30. #endif

编译

  1. g++ -std=c++0x -O3 main.cpp -o inv_number
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注