堆排序之原地堆排序

之前介紹了堆排序，現在我們來聊聊原地堆排序

【代碼】

//原地堆排序
template<typename T>
void heapSort3(T arr[], int n)
{
    //将數組建構成一個堆
    for(int i = (n - 1) / 2; i >= 0; i--)
    {
        __shiftDown(arr, n, i);
    }
    for(int i = n - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        __shiftDown(arr, i, 0);
    }
}
template<typename T>
void __shiftDown(T arr[], int n, int k)
{
    while( 2 * k + 1< n)
    {
        int j = 2 * k + 1;
        while((j + 1) < n && arr[j] < arr[j+1])
        {
            j = j + 1;
        }
        if(arr[j] <= arr[k])
        {
            break;
        }
        swap(arr[k], arr[j]);
        k = j;
    }
}
           

【測試結果】Heap Sort3為原地堆排序，可以看出，原地堆排序性能比之前兩種堆排序效率都要高，但是還是次于快速排序