快速排序是什么？快速排序法原理以及代码实例讲解

Bonnie ·

更新时间:2024-11-13

· 844 次阅读

思想：调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素、右侧所有元素均大于该元素，对该元素的左侧和右侧进行相同的操作，直至当前调整区间的长度不超过1。原理：对一个序列A[1]、A[2]、…、A[n]，调整序列中元素的位置，使得A[1](原序列的A[1]，下同)的左侧所有元素都不超过A[1]、右侧所有元素都大于A[1]。例如对序列{5,3,9,6,4,1}来说，可以调整序列中元素的位置，形成序列{3,1,4,5,9,6}，这样就让A[1]=5左侧的所有元素都不超过它、右侧的所有元素都大于它。代码描述：

#include<cstdio>
const int n=10;
//对区间[left,right]进行划分
int Partition(int A[], int left, int right) {
int temp = A[left]; //将主元（A[left]）存放至临时变量temp
while(left<right) { //只要left和right不相遇
while(left<right&&A[right]>temp) right--; //比较主元和从右侧开始遍历的元素，元素大于主元则左移
A[left] = A[right]; //元素不大于主元，将此元素A[right]挪到A[left]
while(left<right&&A[left]<=temp) left++; //比较主元和从左侧开始遍历的元素，元素小于等于主元则右移
A[right] = A[left]; //元素大于主元，将此元素A[left] 挪到A[right]
}
A[left] = temp; //把temp放到left与right相遇的地方
return left; //返回相遇的下标
}
//快速排序，left与right初值为序列首位下标（例如1与n）
void quickSort(int A[],int left,int right) {
if(left<right) {
//将[left,right]按A[left]一分为二
int pos = Partition(A,left,right);
quickSort(A,left,pos-1); //对左子区间递归进行快速排序
quickSort(A,pos+1,right); //对右子区间递归进行快速排序
}
}
int main(){
int A[n]={1,2,4,5,6,43,7,9,3,5};
quickSort(A,0,9);
for(int i=0;i<n;i++){
printf("%d ",A[i]);
}
return 0;
}

分析：其关键在于主元的选取，我们将数组的第一个元素即A[left]定为主元，其实这样是不合理的，会导致时间复杂度出现及其不合理的差距甚至达到最坏的时间复杂度O(n²)。正确的方法是随机选取主元。时间复杂度：O(nlogn) 空间复杂度：O(nlogn) 拓展：根据[left,right]生成的随机数进行主元的选取：

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
using namespace std;
const int n=10;
//交换函数
void swap(int &a,int &b){
int temp=0;
temp = b;
b=a;
a=temp;
}
//对区间[left,right]进行划分
int Partition(int A[], int left, int right) {
//生成[left,right]内的随机数p
int p = (round(1.0*rand()/RAND_MAX*(right-left)+left));
swap(A[p],A[left]);
int temp = A[left]; //将主元（A[left]）存放至临时变量temp
while(left<right) { //只要left和right不相遇
while(left<right&&A[right]>temp) right--; //比较主元和从右侧开始遍历的元素，元素大于主元则左移
A[left] = A[right]; //元素不大于主元，将此元素A[right]挪到A[left]
while(left<right&&A[left]<=temp) left++; //比较主元和从左侧开始遍历的元素，元素小于等于主元则右移
A[right] = A[left]; //元素大于主元，将此元素A[left] 挪到A[right]
}
A[left] = temp; //把temp放到left与right相遇的地方
return left; //返回相遇的下标
}
//快速排序，left与right初值为序列首位下标（例如1与n）
void quickSort(int A[],int left,int right) {
if(left<right) {
//将[left,right]按A[left]一分为二
int pos = Partition(A,left,right);
quickSort(A,left,pos-1); //对左子区间递归进行快速排序
quickSort(A,pos+1,right); //对右子区间递归进行快速排序
}
}
int main(){
int A[n]={1,2,4,5,6,43,7,9,3,5};
quickSort(A,0,9);
for(int i=0;i<n;i++){
printf("%d ",A[i]);
}
return 0;
}

排序法快速排序排序

1024 个赞