逆序数寻找

雁栖湖 算法设计与分析

快速排序思想

Code

#include <iostream>
#include "gjz_timer.h"
size_t rc = 0; // use size_t to avoid overflow
const int N = 1000000;
int tmp_ll[N], tmp_lr[N], tmp_rl[N], tmp_rr[N];
int partition(int arr[], int l, int r) {
    int mid = l + (r - l) / 2;
    int pivot = arr[mid];
//    int *tmp_ll = NULL, *tmp_lr = NULL, *tmp_rl = NULL, *tmp_rr = NULL;
    size_t ll = 0, lr = 0, rl = 0, rr = 0;
    // left
    int i = 0;
    if (l < mid) {
//        int n = mid - l;
//        tmp_ll = new int[n];
//        tmp_lr = new int[n];
        for (i = mid - 1; i >= l; --i) {
            if (arr[i] < pivot)
                tmp_ll[ll++] = arr[i];
            else {
                tmp_lr[lr++] = arr[i];
                rc = rc + ll + 1; // the 1 is for the pivot
            }
        }
    }
    // right
    if (r > mid) {
//        int n = r - mid;
//        tmp_rl = new int[n];
//        tmp_rr = new int[n];
        for (i = mid + 1; i <= r; ++i) {
            if (arr[i] > pivot)
                tmp_rr[rr++] = arr[i];
            else {
                tmp_rl[rl++] = arr[i];
                rc = rc + rr + 1; //the 1 is for the pivot
            }
        }
    }
    rc = rc + lr * rl; // left * right
    // return the pivot
    int k = l;
    for (i = ll - 1; i >= 0; --i) arr[k++] = tmp_ll[i];
    for (i = 0; i < rl; ++i) arr[k++] = tmp_rl[i];
    int part = k; // get the part number
    arr[k++] = pivot;
    for (i = lr - 1; i >= 0; --i) arr[k++] = tmp_lr[i];
    for (i = 0; i < rr; ++i) arr[k++] = tmp_rr[i];
    // free memory
//    delete[] tmp_ll, tmp_lr, tmp_rl, tmp_rr;
    return part;
}
void quick_sort(int arr[], int l, int r) {
    if (l >= r) return;
    int part = partition(arr, l, r);
    quick_sort(arr, l, part - 1);
    quick_sort(arr, part + 1, r);
}
void _print(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}
void test_easy() {
    // int arr[] = {1, 3, 2, 4, 5, 7, 6, 8};
    // int arr[] = {8, 5, 6};
    int arr[] = {6, 7, 4, 2, 1, 3, 5, 12, 8, 10};
    int sz = sizeof(arr) / sizeof(arr[0]);
    quick_sort(arr, 0, sz - 1);
    std::cout << rc << std::endl;
    _print(arr, sz);
}
void test_middle() {
    int A[1000000], i = 0, n = 0;
    while (~std::scanf("%d", &A[i++])) ++n;
    GjzTimer gjz_timer;
    quick_sort(A, 0, n - 1);
    gjz_timer.print_elaps("Cost");
    std::cout << rc << std::endl;
}
int main() {
    test_easy();
    //test_middle();
}

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

#ifndef _GJZ_TIMER_H
#define _GJZ_TIMER_H
/*
* A small but useful timer
* [4/18/2016 by gjz]
*/
#include <ctime>
class GjzTimer {
public:
    GjzTimer() : _beg(clock()) {}
    ~GjzTimer() {}
    void reset() {
        _beg = clock();
    }
    const double elapsed() {
        _second = clock();
        return (_second - _beg) / double(CLOCKS_PER_SEC) * 1000;
    }
    void print_elaps(const std::string &info) {
        std::printf("%s: %.2f ms\n", info.c_str(), elapsed());
    }
    void print_elaps_reset(const std::string &info) {
        std::printf("%s: %.2f ms\n", info.c_str(), elapsed());
        reset();
    }
private:
    clock_t _beg;
    clock_t _second;
};
#endif

编译

g++ -std=c++0x -O3 main.cpp -o inv_number