@cleardusk
2016-09-29T01:21:14.000000Z
字数 2191
阅读 1251
雁栖湖
算法设计与分析
#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