快速排序(C语言)

快速排序（英语：Quicksort），又称分区交换排序，简称「快排」，是一种被广泛运用的排序算法。

快速排序的工作原理是通过分治的方式来将一个数组排序。

快速排序分为三个过程：

1. 将数列划分为两部分（要求保证相对大小关系）；
2. 递归到两个子序列中分别进行快速排序；
3. 不用合并，因为此时数列已经完全有序。

对于完成一个快排函数，需要传入的参数分别是需要排序的数组a,最左边数据的下标以及最右边数据的下标

这里先介绍这一种方法：交换法，而实现交换的函数比较简单，这里不过多赘述。

void Swap(int* a,int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

这一方法的过程是：

先right从右向左开始遍历，right向左走，如果遇到比a[key]更加小的值就停下来；

再left从左向右开始遍历，left开始向右走，相反在遇到比a[key]更加大的值就停下来；

将数组中的两个值作交换；

right再重新开始继续向左走，不断重复这一过程直到二者相遇；

相遇后将相遇处数组的值与a[key]交换，同时将key的值改为相遇处的下标；

向下递归。

如图，举个简单的例子。

void QuickSort(int* a, int left, int right) {

	if (left >= right) {//放在最前
		return; 
 	}
	int begin = left, end = right;//left与right 会被改变，用两个变量保留它们的值用于接下来的递归

	int key = left;

	while (left < right) {

		while (left < right && a[right] >= a[key]) {
			right--;
		}
		 
		while (left < right && a[left] <= a[key]) {
			left++;
		}
		Swap(&a[left], &a[right]);

	}

	Swap(&a[left], &a[key]);
	key = left;

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

在测试一下结果：

没有问题。

(本人资历尚浅，如果文中有任何问题，劳请指出。)