快速排序小结

核心

以序列中某个元素作为标准，使剩下比其小的元素放左边、比其大的元素放右边，然后递归标准元素的左右子序列。

关键点

• 如何选取标准
• 如何形成新序列

具现

不同的选取方法有不同的序列形成方法，这里只写简单的做法：

始终选取第一个元素作为标准，顺序遍历后面的值，当值小于标准值时，将该元素置前，遍历结束后交换标准元素与最后一个小值，递归标准元素的左右子序列。

更详细的步骤：

第一个元素作为标准，定义i指向第一个元素、j指向第二个元素，j向后遍历，当j元素小于标准值时，先i自增再交换i、j元素，当j遍历完成，交换第一个元素与i元素，i的左右子序列继续递归，直到剩下一或零个元素。

思考

• 为什么定义i指向第一个元素？
  • i本质指向的是左子序列的尾元素，默认左子序列是空的。
  • 当出现比标准小的元素时，先i自增意味着腾出了左子序列的空间，后交换意味着大小元素正确置位。
  • 第一个元素是标准元素不属于左子序列，即i的默认指向不会造成任何歧义。
• 当j遍历完成后为什么要交换？
  • 遍历完成意味着左右子序列已被找出，将标准元素与左子序列尾元素交换意味着标准元素正确置位。

代码

int arr[114514];
void qs(int l,int r){
    if (l>=r)return;
    int i=l,j=l+1,t;
    int pivot=arr[l];//标准
    for (;j <= r; ++j) {//j遍历
        if (arr[j]<pivot){
            i++;//i自增
            t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;//交换i与j元素
        }
    }
    t=arr[i];
    arr[i]=arr[l];
    arr[l]=t; //交换第一个与i元素
    if(i-l>1) //剩下两个及以上元素时递归
        qs(l,i-1); //左子序列
    if(r-i>1)
        qs(i+1,r); //右子序列
}