算法导论：c++快速排序-蒲公英云

算法导论：c++快速排序

快速排序也采用分治的思想，以最后一个元素为基准把其分成大于它和小于它的两部分，关键在于确定分割点。

算法思想

这里写图片描述

一趟快排

这里写图片描述

算法实现

安装书上的算法思想，主要要注意

i,j的初始化,i=p-1,j=p
终止条件j=r
每次循环j都要+1移动

/*快排分割,p首端，r尾端,i控制小于,j控制大于*/
int quick_partition(int array[], int p, int r)
{
    int x = array[r];
    int i = p - 1; //注意i和p的初始值
    for (int j=p; j<r;j++)
    {
        if (array[j] < x) //小于则发生交换
        {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    //交换分割点和最尾元素
    int temp = array[i+1];
    array[i + 1] = array[r];
    array[r] = temp;
    return i + 1; //返回分割点
}
/*快速排序*/
void quicksort(int array[], int p, int r) 
{
    if (p < r) {
        int q = quick_partition(array, p, r);
        quicksort(array, p, q-1);
        quicksort(array, q+1, r);
    }
}

主函数测试

int main()
{
    const int len = 8;
    int array[len] = { 2,8,7,1,3,5,6,4};
    quicksort(array, 0, 7);
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << " ";
    }
}