ChrisLinn
V2EX  ›  算法

快排

  •  
  •   ChrisLinn · Jan 21, 2018 · 3235 views
    This topic created in 3040 days ago, the information mentioned may be changed or developed.

    想请教一下,快排这么写可以么,比经典写法少用一个 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 replies    2018-02-23 13:25:24 +08:00
    testratter
        1
    testratter  
       Feb 23, 2018 via Android
    可以,只是代码上少一个 swap,实际运行的时候,迭代到最后一个元素,i=r 的时候,arr[i] <= pValue 永远为真,那个 swap 肯定会执行。
    不过我觉得虽然省了一行,但代码明晰度下降了。
    不过 i = l + 1 这个赋值在第一个元素小于 arr[r]的情况下会出错。
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   955 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 21:42 · PVG 05:42 · LAX 14:42 · JFK 17:42
    ♥ Do have faith in what you're doing.