排序算法—快速排序

x33g5p2x  于2021-09-19 转载在 其他  
字(0.9k)|赞(0)|评价(0)|浏览(156)

算法稳定性:不稳定

复杂度分析:

  • 最好空间复杂度:O(logn)
  • 最坏空间复杂度:O(n)
  • *最好时间复杂度:O(n/logn)
  • *平均时间复杂度:O(n/logn)
  • 最坏时间复杂度(全部有序):O(n^2)

实现代码:

#include<iostream>
using namespace std;
//快速排序

//用待排序序列的第一个元素将待排序序列划分为左右两个部分
int part(int *nums,int low,int high){
	
	int tmp=nums[low]; //第一个元素作为枢轴 
	
	while(low<high){
		
		while(low<high&&nums[high]>=tmp) high--; //小于等于枢轴的在low的左端 
		nums[low]=nums[high];
		while(low<high&&nums[low]<=tmp) low++; //大于等于枢轴的在high的右端 
		nums[high]=nums[low];
	}
	
	nums[low]=tmp; //枢轴元素存放到最终位置 
	return low; //返回存放枢轴的位置,即下一步要划分的位置 
} 

//快速排序 
void QuickSort(int *nums,int low,int high){
	
	if(low<high){
		int mid=part(nums,low,high); //划分整个数组 
		QuickSort(nums,low,mid-1); //划分左子数组
		QuickSort(nums,mid+1,high); //划分右子数组 
	} 
	
}

int main(){
	
	int n;
	cin>>n;
	int nums[n];
	
	for(int i=0;i<n;i++)
		cin>>nums[i];
		
	QuickSort(nums,0,n-1); //快速排序
	
	cout<<"排序后的序列为:";
	for(int i=0;i<n;i++)
		cout<<nums[i]<<" "; 
	
	return 0;
}

运行结果:

在这里插入图片描述

相关文章