10
2020
03

快速排序

  1. 今天来复习下几个常用的排序方式,首先想到的就是快速排序,思路用的是分治思想。

  2. 选取一个标准值,利用两个指针i,j分别只想最左边,最右边,i从左边找到1个比这个标准值大的数,j从右边找到1个比这个值小的数,两者交换,直到i>j

    就找到了这个标准值的位置。


/*
快速排序,分治思想
给定的N个数从小到达进行排序
3 2 4 5 1
思路:选定第一个元素作为轴,i从左往右找比他大的一个数a[i],j从后往前找比他小的数a[j]
两者交换,知道i>j 

对轴左边继续执行上述操作,右边继续执行上述操作,分而治之 
*/
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int n;
void mysort(int a[],int l,int r){
	//i记录轴左边位置,j记录轴右边位置 
	int i=l,j=r;
	int pvot=a[(l+r)>>1]; 
	while(i<=j){
		//从左边找比他大的一个数 
		while(a[i]<pvot){
			i++ ;
		}
		//从右边找比他小的一个数 
		while(a[j]>pvot){
			j--;
		}
		if(i<=j){
			swap(a[i],a[j]);//交换 
			i++;
			j--;
		}
	}
	//左右两边分别排序
	if(l<j) mysort(a,l,j);
	if(i<r) mysort(a,i,r);	
}


int main(){

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	int l=0,r=n-1;
	mysort(a,l,r); 
	for(int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	
	return 0;
}


« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。