C语言经典排序算法之快速排序（详解）

亦凉 2023-01-03 14:19 119阅读 0赞

### 文章目录 ###

*   *  一、何为算法
     *  二、排序算法
     *  三、快速排序算法

## 一、何为算法 ##

1、算法（Algorithm），是程序设计的灵魂，它是利用系统的方法描述解决问题策略的机制。

2、正确算法应满足的性质：

*  输入：有零个或多个输入
 *  输出：至少有一个输出
 *  确定性：组成算法的每条指令清晰，无歧义。
 *  有限性：一个算法在执行有限步骤后必须结束，即计算步骤是有限的。

3、描述算法可以有多种方式，如自然语言、流程图、伪代码、程序设计语言，算法设计就是针对具体的问题，设计出良好的能使计算机解决问题的算法。  
同一个问题可以采用不同的算法实现，不同的算法时间、空间上也往往不同，一个算法的好坏可以用时间复杂度和空间复杂度来衡量。

## 二、排序算法 ##

通过特定的算法因式将一组或多组数据按照既定模式进行重新排序，这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

## 三、快速排序算法 ##

**1、快速排序简单解释**  
快速算法其实也可以通过递归调用来实现，排序的过程其实就是不断对元素序列进行划分，  
直到每一个部分不能划分时即完成快速排序。

**2、算法思想**  
速排序算法是对冒泡排序算法的改进，也属于交换类排序算法。它的基本算法思想如下:  
假设待排持序元素个数为n，分别存放在数组a\[1…n\]中，令第1个元素为参考轴无素)，`pot=a[1]`，初始时，`i=1,j=n`，然后按照以下方法操作：  
（1）从第个元素开始向前依次将每个元素与轴元素pot比较。如果当前元素大于等于pot，  
则比较前一个元素与pot，即比较a\[j-1\]与pot；否则，将当前元素移动到第i个位置并执行步骤（2）。

（2）从第1个元素开始向后依次将每个元素与轴元素pot比较。如果当前元素小于pot，  
则比较后个元素与pot，即比较a\[i+1\]与pot；否则，将当前元素移动到第j个位置并执行步骤（3）。

（3）重复执行步骤（1）和（2），直到出现i≥j,将轴元素pot移动到a\[i\]中。  
此时，整个元素序列被划分为两个部分，第i个位置前的元素都小于a\[i\]，第i个位置后的无素都大于等于a\[i\]。

至此，就完成了一次快速排序。按照以上方法，将每个部分都进行类似的划分操作，直到每个部分都只有一个元素为止，这样整个元素序列就构成了一个有序的序列。

**3、C语言实现快速排序**

#include <stdio.h>
    //声明函数 
    void DisArray(int a[], int n);
    void DisArray2(int a[], int n, int pot, int count);
    void Qsort(int a[], int n, int low, int high);
    void QuickSort(int a[], int n);
    int Partition(int a[], int low, int high);
    
    //主函数 
    void main()
    { 
    	int a[]= { 23,12,54,2,65,90,67,99,32,15};
    	int n= sizeof(a)/sizeof(a[0]);
    	printf("快速排序前：");
    	DisArray(a, n);
    	QuickSort(a, n);
    	printf("快速排序结果：");
    	DisArray(a, n);
    } 
    
    //操作函数
    //利用快速排序算法对数组a进行排序 
    void Qsort(int a[], int n, int low, int high)
    { 
    	int pot;
    	static count= 1;
    	if(low<high)  //如果元素序列的长度大于1 
    	{ 
    		pot= Partition(a, low, high);  //将待排序序列a[low...high]划分为两部分
    		DisArray2(a, n, pot, count);  //输出每次划分的结果
    		count++;
    		Qsort(a, n, low, pot-1);  //对左边的子表进行递归排序，pot是轴位置
    		Qsort(a, n, pot+1, high); 
    	}
    }
    
    //对数组a进行快速排序 
    void QuickSort(int a[], int n)
    { 
    	 Qsort(a, n, 0, n-1);
    }
    
    //对数组a[low...high]的元素进行一次排序，
    //使轴前的元素小于轴元素，轴后面的元素大于等于轴元素，并返回轴位置 
    int Partition(int a[], int low, int high)
    { 
    	int t, pot;
    	pot= a[low];  //收下将数组的第一个元素作为轴元素
    	t= a[low];
    	while(low<high)
    	{ 
    		while(low<high && a[high]>=pot)  //从数组的末端向前端扫描
    			high--;
    		if(low<high)
    		{ 
    			a[low]= a[high];
    			low++;
    		} 
    		while(low<high && a[low]<=pot)  //数组的起始端向后扫描
    			low++; 
    		if(low<high)  //将当前a指向的元素保存在high位置 
    		{ 
    			a[high]= a[low];
    			high--;
    		}
    		a[low]= t;  //将轴元素保存在low位置 
    	}
    	return low;  //返回轴位置
    }
    
    //输出每次划分的结果
    void DisArray2(int a[], int n, int pot, int count)
    { 
    	int i;
    	printf("第%d次划分的结果：[",count);
    	for(i=0; i<pot; i++)
    		printf("%4d",a[i]);
    	printf("]");
    	printf("%3d",a[pot]);
    	printf("[");
    	for(i=pot+1; i<n; i++)
    		printf("%4d",a[i]);
    	printf("]\n");
    }
    
    //输出数组中的元素
    void DisArray(int a[], int n)
    { 
    	int i;
    	for(i=0; i<n; i++)
    		printf("%-4d", a[i]);
    	printf("\n");
    }

![01][]

**4、快速排序的用途**  
快速排序是对冒泡排序的改进，它的实现比较复杂，它主要用在数量比较大的排序中，它的时间效率要远高于冒泡排序。

**5、快速排序复杂度**

*  时间复杂度：快速排序是一种不稳定的排序算法，在最好的情况下，每次排序都是将元素序列正好划分为两个等长的子序列，时间复杂度为O(n^2)。  
    在最坏的情况下待排序元素已经是有序的，则时间就主要花费在元素的比较次数上，时间复杂度为O(n^2)。  
    平均情况下，快速排序的时间复杂度为O(nlog2n) 2为底。
 *  空间复杂度为：O(log2n)，2为底，n为真值

参考文献：《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/35fb9a3966fb4ce4b75f9e451a5ee450.png