快速排序小结

核心

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

关键点

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

具现

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

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

更详细的步骤:

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

思考

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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); //右子序列
}

快速排序小结
http://lafish.fun/quick-sort/
作者
lafish
发布于
2022年4月29日
许可协议