快速排序quicksort算法详细图解附代码实现(C++)

快速排序的思想我就不讲了，下面直接上流程图

下面是快速排序的函数声明，可以看到这里的代码思路是接受两个迭代器来完成的，lp迭代器指向的是数组的第一个元素，rp迭代器指向的是数组最后一个元素（注意是vector.end()-1，而非vector.end()）

void quicksort(vector::iterator lp, vector::iterator rp)

void quicksort(vector::iterator lp, vector::iterator rp)
{
    if(rp - lp > 0)	
    // 判断数组中是否少于一个元素
    {
        vector::iterator olp = lp, orp = rp;
        // original-lp和original-rp用于记录当前数组的第一个和最后一个元素位置
        
        int pivot = *lp;
		// 使用第一个元素作为pivot，这里直接用*olp来表示pivot的值也可以，这里是为了能更直观
		
        while(lp != rp)
        // 循环体里面就是根据刘成都来执行
        {
            while(*rp >= pivot && rp > lp)
                --rp;
            //rp要么指到一个比pivot小的元素，要么指到pivot本身

            while(*lp <= pivot && rp > lp)
                ++lp;
            // lp要么指到rp，要么指到一个比pivot大的元素

            if (rp != lp)
                swap(*rp, *lp); 
            // 若rp和lp没相遇，那么交换元素进行下一轮循环
        }
        
        swap(*olp, *rp);
        // 这里做的是跳出循环后，rp与pivot进行交换的步骤
       
        quicksort(olp, lp - 1);	
       	// 对pivot左边的子数组进行快排
       	
        quicksort(rp + 1, orp);
        // 对pivot右边的子数组进行快排
    }
}

假设待排序的序列是基本有序的，这时候快排的效率就会降低，因此使用随机选取pivot的方法可以在一定程度优化算法。

void quicksort(vector::iterator lp, vector::iterator rp)
{
    if(rp - lp > 0)	
    // 判断数组中是否少于一个元素
    {
        vector::iterator olp = lp, orp = rp;
        // original-lp和original-rp用于记录当前数组的第一个和最后一个元素位置
        
        auto pivot_it = (lp + rand() % (rp - lp + 1));
        int pivot = *pivot_it;
        swap(*olp, *pivot_it);
		// 这里用这三行代码就可以实现随机选取pivot，并且不需要动下面的代码
		
        while(lp != rp)
        // 循环体里面就是根据刘成都来执行
        {
            while(*rp >= pivot && rp > lp)
                --rp;
            //rp要么指到一个比pivot小的元素，要么指到pivot本身

            while(*lp <= pivot && rp > lp)
                ++lp;
            // lp要么指到rp，要么指到一个比pivot大的元素

            if (rp != lp)
                swap(*rp, *lp); 
            // 若rp和lp没相遇，那么交换元素进行下一轮循环
        }
        
        swap(*olp, *rp);
        // 这里做的是跳出循环后，rp与pivot进行交换的步骤
       
        quicksort(olp, lp - 1);	
       	// 对pivot左边的子数组进行快排
       	
        quicksort(rp + 1, orp);
        // 对pivot右边的子数组进行快排
    }
}