V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ChrisLinn
V2EX  ›  算法

快排

  •  
  •   ChrisLinn · 2018-01-21 23:17:06 +08:00 · 2591 次点击
    这是一个创建于 2497 天前的主题,其中的信息可能已经有所发展或是发生改变。

    想请教一下,快排这么写可以么,比经典写法少用一个 swap ?

    int partition(int arr[], int l, int r) {
        int pPos = l, pValue = arr[l];
        for (int i = l+1; i <= r; ++i)
            if (arr[i] <= pValue) std::swap(arr[i], arr[pPos++]);
        return pPos;
    }
    
    void quicksort(int arr[], int l, int r) {
        if (l < r) {
            int pivot = partition(arr, l, r);
            quicksort(arr, l, pivot-1);
            quicksort(arr, pivot+1, r);
        }
    }
    

    经典写法类似于

    int partition(int arr[], int l, int r) {
        int k = l, pivot = arr[r];
        for (int i = l; i < r; ++i)
            if (arr[i] <= pivot) std::swap(arr[i], arr[k++]);
        std::swap(arr[k], arr[r]);
        return k;
    }
    
    void quicksort(int arr[], int l, int r) {
        if (l < r) {
            int pivot = partition(arr, l, r);
            quicksort(arr, l, pivot-1);
            quicksort(arr, pivot+1, r);
        }
    }
    
    1 条回复    2018-02-23 13:25:24 +08:00
    testratter
        1
    testratter  
       2018-02-23 13:25:24 +08:00 via Android
    可以,只是代码上少一个 swap,实际运行的时候,迭代到最后一个元素,i=r 的时候,arr[i] <= pValue 永远为真,那个 swap 肯定会执行。
    不过我觉得虽然省了一行,但代码明晰度下降了。
    不过 i = l + 1 这个赋值在第一个元素小于 arr[r]的情况下会出错。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1031 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 23:00 · PVG 07:00 · LAX 15:00 · JFK 18:00
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.