请教大家一个关于快速排序的问题。

sublx

回复 9# crazyhadoop


    你到你机器上运行下，看看是不是大概的结果。

goldenfort

回复 1# sublx


    刚qsort 一个整型 数组， 除了练习下， 实际应用中有意义吗？
    在什么情况下，是对 整数组 排序， 没有其它任何相关信息？在具体的应用环境下应该是，以整型数 为关键字的信息。

sublx

回复 12# goldenfort

我就是吃饱了没事干，脑子一拍写的，但是写过之后，遇到这样的疑问，所以想咨询一下大家嘛？


   

hzy2hzy

int partition(int *array, int low, int high)
{
    int prov = array[low];
    while(low < high)
    {
        while(low < high && array[high] >= prov) high--;
        array[low] = array[high];//????
        while(low < high && array[low] <= prov) low++;
        array[high] = array[low];//????
    }
    array[low] = prov;
    return low;
}
问号的地方为什么不需要swap array[low] and  array[high]?

sublx

回复 14# hzy2hzy

为什么需要？不过我记得是有一个swap的写法的，不过我这样写不需要。
   

变异老鼠

回复 10# sublx

debian wheezy, x86-64, g++ 4.7.2, -O2

inpput size:1000000
input times:10
t1 = 0.11seconds
t2 = 0.16seconds
same
t1 = 0.11seconds
t2 = 0.16seconds
same
t1 = 0.11seconds
t2 = 0.15seconds
same
t1 = 0.12seconds
t2 = 0.16seconds
same
t1 = 0.12seconds
t2 = 0.15seconds
same
t1 = 0.11seconds
t2 = 0.16seconds
same
t1 = 0.11seconds
t2 = 0.15seconds
same
t1 = 0.11seconds
t2 = 0.15seconds
same
t1 = 0.11seconds
t2 = 0.15seconds
same

确实会慢，但没有你的结果那么离谱。

linux_c_py_php

一句话：瞎JB抖擞。

sublx

回复 16# 变异老鼠

怎么我这里会慢这么多？难道是我那个compare函数写得太挫了？我看下。（PS:你是用我贴的代码吗？）

1. int compare(const void *v1, const void *v2)
   
2. {
   
3.         int *p = (int *)v1;
   
4.         int *q = (int *)v2;
   
5. 
   
6.         if (*p < *q) return -1;
   
7.         else if (*p > *q) return 1;
   
8.         else return 0;
   
9. }

复制代码

变异老鼠

回复 18# sublx

换了你的 compare，没什么区别。

我来猜猜……用的是 VS 的 Debug 库？

sublx

回复 19# 变异老鼠


是的。