h**6
发帖数: 4160 | 1 已知从小到大冒泡排序的代码如下：
for (int i = 0; i < n - 1; i ++) {
for (int j = 0; j < n - 1 - i; j ++) {
if (x[j] > x[j+1]) {
swap(x[j], x[j+1]);
}
}
}
已知数组x[]，长度为n，是0...n-1的某一排列，求将数组x进行冒泡排序需要的交换次
数。 |
l*********8
发帖数: 4642 | 2 需要O(n*logn)或者O(n)的算法？
【在 h**6 的大作中提到】
: 已知从小到大冒泡排序的代码如下：
: for (int i = 0; i < n - 1; i ++) {
: for (int j = 0; j < n - 1 - i; j ++) {
: if (x[j] > x[j+1]) {
: swap(x[j], x[j+1]);
: }
: }
: }
: 已知数组x[]，长度为n，是0...n-1的某一排列，求将数组x进行冒泡排序需要的交换次
: 数。
|
l*********8
发帖数: 4642 | 3 逐个扫描数组元素，依次插入下面这样的二叉树
struct BinaryTreeNode {
int subNodeCount;
int val;
BinaryTreeNode * left;
BinaryTreeNode * right;
};
在插入元素x[i]的同时，也容易求得二叉树中比x[i]小的元素的数目k[i], 也就是比x[
i]小，并且位于x[i]之前的元素个数.
swap总数就是： sum(x[i] - k[i]), i from 0 to n-1
每次插入二叉树， O(logn)
n个元素， 总共 O(n*logn)
【在 h**6 的大作中提到】
: 已知从小到大冒泡排序的代码如下：
: for (int i = 0; i < n - 1; i ++) {
: for (int j = 0; j < n - 1 - i; j ++) {
: if (x[j] > x[j+1]) {
: swap(x[j], x[j+1]);
: }
: }
: }
: 已知数组x[]，长度为n，是0...n-1的某一排列，求将数组x进行冒泡排序需要的交换次
: 数。
|
x***y
发帖数: 633 | 4 It's the same as counting inversions (O(nlogn) using merge sort.) |
l*********8
发帖数: 4642 | 5 good one:
http://www.geeksforgeeks.org/counting-inversions/
【在 x***y 的大作中提到】
: It's the same as counting inversions (O(nlogn) using merge sort.)
|
