上一篇分析了归并排序过程，本篇将堆排序完结，同时分析快速排序过程。

通过build_max_heap，对给定的数据，建立一个最大堆结构，此时，堆排序任务已经完成了80%，建立好的最大堆，堆顶为最大元素，

输出堆顶，然后将最后叶子切换到堆顶，重新建立最大堆，再次输出堆顶，依次重复建立最大堆过程，直至输出输出所有元素，最后形成的序列即为

有序序列，降序序列。

程序里紧紧对过程模拟，输出堆顶后，赋值为-1，而不删除元素，模拟最终的输出：

int i = 0;    stringstream iss;    for (; i < _arr_len; i++) {        build_max_heap();        //cout << _heap_arr[0] << " ";        iss << _heap_arr[0] << " ";        // swap 0 and last element        _heap_arr[0] = -1;           }    cout << "final sequence is:";    cout << iss.str() << endl;    return 0;

3、快速排序

快排是目前所有排序算法中使用较多的排序，其基本的原理是：每次迭代都确定一个元素的最终位置，那么此时元素的左右区间，可以递归掉调用来确定每个区间的元素的最终位置，可见，每个区间内的调整都不需要进行

核心逻辑是，给定区间[p, r]如何确定其中一个元素的最终位置，算法导论中以a[r]为参考元素，确定其最终的位置，实现代码为

int QuickSort::get_arr_pivot(int p, int r){    int key = _arr[r];    // i 指向开始遍历前一个。    int i = p - 1;    for (;p < r; p++) {        if (_arr[p] >= key) {            continue;                        //如果当前元素比参考值要小，那么i自增，将i当前元素与p指向的值交换            //这样i此时指向小于参考值元素        } else if (_arr[p] < key) {            i++;            arr_swap(i, p);        }    }    //遍历结束，i指向比key小的值，i+1是第一个大于key的元素    //交换i+1与key    //那么此时key的最终位置固定下来了，左右边为小于、大于它的区间    //对子区间递归排序即可    arr_swap(i + 1, r);    return i + 1;}

最终排序递归调用即可：

int QuickSort::quick_sort(int p, int r) {    if (p < r) {        int q = get_arr_pivot(p, r);                print_arr();        quick_sort(p, q-1);        quick_sort(q+1, r);    }    return 0;}

 

可以发现，快排是就地排序，而归并排序则是针对有序数据进行merge，需要借助额外空间。而快排则是就地排序，不用额外空间，每次递归就确定一个元素的最终位置，因此最终不用merge操作。