内容纲要
深入快速排序
sort
排序很多Acmer都不陌生,甚至经常使用,那么它是怎样实现的呢❔
可视化快速排序算法
原理
在序列中任意选择一个数(通常为第一个数),然后把序列分成比这个数大的和比这个数小的两个子序列。不断重复以上步骤完成排序
为了方便,以下统称 比 基准值小的序列元素 为 小元素
,比基准值大的序列元素为 大元素
举例
方法一
选定a[0]为基准,理想情况是后面都是大元素
,不交换
可见,交换策略为:后面出现小元素
具体实现:
- 确定待排序序列的基准pivot = a[0]
- 遍历来划分剩余序列,通过比较和交换,使得左半边都为小元素,右半边为大元素
- 最后交换基准和最后一位小元素,即可完成对序列的一次快排操作
- 即
- 开始->
基准-剩余序列
- ->
基准-小元素-大元素
- ->
小元素
-基准-大元素
`
- 开始->
对原数组a[5] = {4,5,7,3,6}
进行第一轮快速排序
beg = 0;
end = 4;
取枢轴元素 pivot = a[beg] = a[0]
设定索引 index = beg + 1
接下来遍历[beg+1,end]即[1,4]内的元素
按照策略,每当出现 a[i] < pivot
的情况时
交换 index 和 a[i] 的值,确保小的值都会被换到前面
并且index++,继续寻找是否有下一个可交换的小元素
如果没有找到,那么不做处理
直到[beg+1,end]区间遍历结束,小元素和大元素都已经划分完毕,此时交换枢轴和最后一位小元素
完成一轮快速排序
pivot = a[0] = 4
index = 1
4 5 7 3 6
遍历[1,4]区间
//找到3小于4,交换a[i] 和 index
4 3 7 5 6
index = 2 //index++
4 3 7 5 6 //遍历结束没有再找到
//此时确定最后一位小元素的下标为index - 1 = 1
index = 1 //pivot与其交换
//交换完成后即完成一轮快速排序
3 4 7 5 6
方法二
选定a[0]为枢轴pivot,设定索引 left
和 right
分别指定left,right除去pivot后剩余序列的起始位置
主要思想和方法一相同,不过由于有两个游标,写法上有些微区别
最终局面:
需要索引 left 的左边全都是`小元素`
需要索引 right 的右边全都是`大元素`
交换策略: 索引 left 指向大元素,索引 right 指向小元素,两者同时
发生时执行交换,如果只有一方达成交换条件,那么继续循环直到另一方也达成交换条件
4 5 7 3 6
pivot = a[0] = 4
left = 1,right = 4
4 5 7 3 6
遍历[1,4]区间
left = 1 -> 5 > 4 ,left出现大元素,满足交换条件
right = 3 -> 3 < 4 ,right出现小元素,满足交换条件
执行交换,得到
4 3 7 5 6
此时left++ 后 left = 2, right-- 后 right = 2
while(left < right) 满足,继续循环
>如果在left == right 时退出循环,会不确定left和right的值指向的值是否大于pivot,从而>导致交换后产生不必要的错误(当然也可以交换 (right - 1)的值,和上个方法一个思路)
继续循环: right-- 后right = 1,left++ 后left = 3
接着交换pivot 和 right的值swap(0,1)
得到一轮快排后的序列
3 4 7 5 6
代码实现
C++代码实现
#include <iostream>
#include <vector>
using namespace std;
int quick_method_1(vector<int> &v,int beg,int end){
int pivot = v[beg];
int index = beg + 1;
for(int i = index;i <= end;++i){
if(v[i] <= pivot){
swap(v[i],v[index++]);
}
}
swap(v[beg],v[index-1]);
return index - 1;
}
int quick_method_2(vector<int> &v,int beg,int end){
int pivot = v[beg];
int left = beg + 1;
int right = end;
while(left <= right){
if(v[left] < pivot) left++;
else if(v[right] > pivot) right--;
else if(v[left] >= pivot && v[right] <= pivot){
swap(v[left++],v[right--]);
}
}
swap(v[beg],v[right]);
return right;
}
void quick_sort(vector<int> &v,int beg,int end){
if(beg < end){
int pivot = quick_method_1(v,beg,end);
quick_sort(v,beg,pivot-1);
quick_sort(v,pivot+1,end);
}
};
int main()
{
vector<int> v;
v.push_back(5);
v.push_back(2);
v.push_back(9);
v.push_back(4);
quick_sort(v,0,3);
for(int i = 0;i < 4;i++){
cout << "v[" << i << "] = " << v[i] << endl;
}
return 0;
}
Python代码实现
def quick_method_1(seq,beg,end):
pivot = seq[beg] # 枢轴
index = beg + 1
for i in range(beg+1,end+1): # 剩余序列的起始位置
if(seq[i] <= pivot):
seq[i],seq[index] = seq[index],seq[i]
index += 1 # Python中没有++和--
seq[beg],seq[index-1] = seq[index-1],seq[beg]
return index - 1
def quick_method_2(seq,beg,end):
pivot = seq[beg]
left = beg + 1 # 左索引
right = end # 右索引
while(left <= right): # 注意等于
if(seq[left] < pivot):
left += 1
elif(seq[right] > pivot):
right -= 1
elif(seq[left] >= pivot and seq[right] <= pivot):
seq[left],seq[right] = seq[right],seq[left]
left += 1
right -= 1
seq[beg],seq[right] = seq[right],seq[beg]
return right
def quick_sort(seq,beg,end):
if(beg < end):
# 方法一
# pivot = quick_method_1(seq,beg,end)
# 方法二
pivot = quick_method_2(seq,beg,end)
quick_sort(seq,beg,pivot-1) # 快排枢轴左边序列
quick_sort(seq,pivot+1,end) # 快排枢轴右边序列
if __name__ == "__main__":
seq = [4,44,58,63,11,34,75,5,30,6]
quick_sort(seq,0,9)
print(seq)