[数据结构与算法]C语言写传统快速排序

算法小白写快速排序~

快速排序一般比其他O(nlogn)算法更快一点，但如果遇到最坏的情况则是O(n²)。下面来讲解一下快速排序原理。

1. 取出基准值(传统方式的话，确定为最左端值)。
2. 将基准值与最有右端值相比，依次移动 i 指针，当出现比基准值小的值时，将该位置元素与基准值的空白(当前 j 指针所指位置)交换。
3. 将基准值与左端值相比，依次移动 j 指针，当出现比基准值大的值时，将该位置元素与基准值空白(当前 i 指针所指位置)交换。
4. 循环2~3步。
5. 当 i、j 相遇时，退出循环，将基准值填入当前空白处。将原数组根据当前基准值的位置分成两部分，分别再进行上述1~4步。(递归调用)
6. 当左元素位置>=右元素位置时，递归结束。

直接上图


当遇到需要调整位置的时候：
蓝色箭头所指的值直接扔给红色箭头所指的位置（空白）；
红色箭头所指的值直接扔给蓝色箭头所指的位置（空白）。
最后再将基准值填入空白。

分治法

可见，快速排序主要是使用了分治思想，使用递归实现分治然后用比较法进行排序。

下面进行代码编写

//先写个交换swap函数吧(实际上也可以不用，但是我喜欢~)
void swap(int i,int j,int num[]){
	int *p=&num[i];
	int *q=&num[j];
	int t;
	t=*p;
	*p=*q;
	*q=t;
	return;
} 

随后，我们来写quicksort函数

void quicksort(int left,int right,int num[]){
	if(left>=right) return; 		//结束递归条件
	int pivot=num[left];	 		//确定基准值
	int k,i,j;
	i=right;j=left;
	while(1){
		while(num[i]>=pivot && j<i){
			i--;
		}
		swap(i,j,num);				//交换i j所指的值
		while(num[j]<=pivot && j<i){
			j++;
		}
		swap(i,j,num);				//交换i j所指的值
		if(i==j){
			k=i; 					//记录切分数组的位置，方便之后进行递归
			break;
		}
	} 
	num[k]=pivot;					//将基准值填入空白处
	/*实际上这句话不需要，
	因为我们在分析的时候使用了填空白的想法，从而更加清晰一点（防止基准值乱跑不好找）。
	实际上，这个空白里面一直存放的就是我们的基准值
	*/
	quicksort(k+1,right,num);		//递归，顺便移动一个指针（右）
	quicksort(left,k-1,num);		//递归，顺便移动一个指针（左）
} 

（建议边看图边看代码）

所以我们就写好了快速排序

但是实际上这种传统的快速排序并不好，当遇到较坏的情况的时候，就会很慢。所以emm…

之后再发文章对算法进行优化……

（本文图片来源：洛谷；题目：P1177）