@cleardusk 2016-09-28T17:21:14.000000Z 字数 2191 阅读 1073

# 逆序数寻找

雁栖湖 算法设计与分析

## 快速排序思想

### Code

#include <iostream>#include "gjz_timer.h"size_t rc = 0; // use size_t to avoid overflowconst 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();}

#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

• 私有
• 公开
• 删除