[C++知识库]快速排序(C语言)

排序分为很多种，例如希尔排序，冒泡排序，堆排序… …很多种，今天我要讲的是这里面时间复杂度最低的快速排序。
首先我们先了解一下快速排序的手工过程：

有了这个手工过程的了解，代码呼之欲出了，我们可以先编写一个交换函数：

void swapOnce(int *array, int start, int end) {
	int i = start;
	int j = end;
	int temp = array[i];

	if (i >= j) {
		return;
	}

	while (i < j) {
		while (i < j && array[j] > temp) {
			j--;
		}
		if (i < j) {
			array[i++] = array[j];
		}

		while (i < j && array[i] < temp) {
			i++;
		} 
		if (i < j) {
			array[j--] = array[i];
		}
	}

	array[i] = temp;

	swapOnce(array, start, i - 1);
	swapOnce(array, i + 1, end);
}

这个交换函数最后两行其实就是递归的思想，因为第一次整体交换完成后，那个temp其实就把整个数组分成了两个子数组，在两个子数组中要完成的工作跟这个大数组要完成的工作其实是一样的，所以只需要讲这个交换函数再次调用即可。
下面是数组的生成以及这个快速排序的完整代码：

#include <stdio.h>
#include <malloc.h>
#include <time.h>

int *creatArray(int minValue, int maxValue, int count);
void showArray(int *array, int count);
void swapOnce(int *array, int start, int end);
void quickSort(int *array, int count);

void quickSort(int *array, int count) {
	swapOnce(array, 0, count-1);
}

void swapOnce(int *array, int start, int end) {
	int i = start;
	int j = end;
	int temp = array[i];

	if (i >= j) {
		return;
	}

	while (i < j) {
		while (i < j && array[j] > temp) {
			j--;
		}
		if (i < j) {
			array[i++] = array[j];
		}

		while (i < j && array[i] < temp) {
			i++;
		} 
		if (i < j) {
			array[j--] = array[i];
		}
	}

	array[i] = temp;

	swapOnce(array, start, i - 1);
	swapOnce(array, i + 1, end);
}

void showArray(int *array, int count) {
	int index;

	for(index = 0; index < count; index++) {
		printf("[%d] ",array[index]);
	}

	printf("\n");
}

int *creatArray(int minValue, int maxValue, int count) {
	int index;
	int value;
	int *array;

	srand(time(0));
	array = (int *) calloc(sizeof(int), count);
	for (index = 0; index < count; index++) {
		value = rand() % (maxValue - minValue + 1) + minValue;
		array[index] = value;
	}

	return array;
}

int main() {
	int *array = NULL;
	int maxValue;
	int minValue;
	int count;
	
	printf("please input minValue/maxValue/count:"); 
	scanf("%d%d%d", &minValue, &maxValue, &count);
	array = creatArray(minValue, maxValue, count);
	
	printf("before sorting:\n");
	showArray(array, count);
	
	printf("after sorting:\n");
	quickSort(array, count);
	showArray(array, count);
	
	free(array);

	return 0;
}

下来我们来看一下这个函数的运行结果：

如果对这个代码中的数组生成函数，或者对这个代码有什么问题可以在下面留言，或者私信我。