最简单的快速排序

叁歲伎倆 2021-11-11 04:42 267阅读 0赞

## 一，快速排序是什么： ##

快速排序(Quicksort)是对冒泡排序的一种改进，将相邻交换改成跳跃式互换。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:**通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小**，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

## 二，快速排序原理： ##

现在有一个数组1,7,3,8,5,2,1,4,9,需要排序

**1.** 选择一个数字作为比较的基数，通常会选择**第一个,中间的一个或者最后一个**，我们选择第中间一个数5作为基数，并把它单独拿出来

**2.** 需要将剩下的数分别和基数5作比较，所以我们需要去遍历剩下的数

**3.** 我们选择两个变量 i 和 j来遍历，**i从1开始往右遍历**，当碰到一个数比基数5大就停下来。**j从9开始往左遍历**，当碰到一个数比基数5小就停下来。

**4.** **交换两个数字**使得小的数在基数5的左边，大的数在基数5 的右边

**5.** 交换完成之后 i 和 j来**继续遍历，直到i>=j停止**这里得到了一个以中间为基准，左边小于右边的数组。但是以基数为中心分隔的左边，和右边的两个数组还是无序的。

**6.** 所以接着分别递归调用左边和右边两个数组，重复上述步骤，最终可以得到一个有序的数组

## 三，代码： ##

#include<stdio.h> 
    
    int a[100],n;//给定全局变量。 
    //交换函数，实现两个数的互换 
    void swap(int a,int b){
    	int temp;
    	temp=a;
    	a=b;
    	b=temp;
    } 
    
    void quicksort(int left,int right){
    	int i,j,t,temp;
    	if(left>right)
    	  return;
    	temp = a[left];//设置temp为基数，将要排序的数组分为两块（这里以第一个数字为基数） 
    	i=left;
    	j=right;
    	while(i!=j){
    	
    	while(a[j]>=temp&&i<j)//j从右边向左边遍历，直到找到一个数a[j]<temp停下来 
    	{
    		j--;
    	}
    	  
    	while(a[i]<=temp&&i<j)//i从左边向右边遍历，直到找到一个数a[i]>temp停下来 
    	{
    		i++;	
    	}
          
        if(i<j){//将找到的两个数交换位置 
        	t=a[i];
    		a[i]=a[j];
    		a[j]=t;  
    		}	
    	}
    	a[left]=a[i];
    	a[i]=temp;//第一趟遍历的最后一步，将基数归位到中间的位置，也就是将temp和a[i]互换 
    	quicksort(left,i-1);//递归调用左分组，再次进行排序 
    	quicksort(i+1,right);//递归调用右分组，再次进行排序 
    	return;
    	} 
    
    
    int main(){
    	int i,j;
    	printf("请输入你要排序的数组元素个数n:");
    	scanf("%d",&n);
    	for(i=0;i<n;i++){
    		printf("请输入第%d个元素",i+1);
    		scanf("%d",&a[i]);
    	}
    	printf("你的数组为：\n");
    	for(i=0;i<n;i++){
    		printf("%3d",a[i]);
    	}
    	quicksort(0,n-1);//调用快速排序的算法 
    	printf("\n排序后的数组为：\n");
    		for(i=0;i<n;i++){
    		printf("%3d",a[i]);
    	}
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70]

## 四，时间复杂度 ##

*  **最优时间复杂度：O( nlogn )**  
    情况：每一次取到的基数都刚好平分整个数组
 *  **最差时间复杂度为：O( n^2 )**  
    情况：每一次取到的元素就是数组中最小/最大的
 *  **快速排序的平均时间复杂度也是：O(nlogn)**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70]: /images/20211109/b24c9d5020ea4af8bc7e15e74f19e899.png