数据结构-快速排序-C语言实现

引言：快速排序作为一种非常经典且高效的排序算法，无论是工作还是面试中广泛用到，作为一种分治思想，需要熟悉递归思想。下面来讲讲快速排序的实现和改进。

老规矩，先用图解来理解一下：（这里使用快速排序中的“挖坑法”）

笔误：下面这个图right是--的！ 

 

 

  以此往复

下面是代码：

void dfs_quick_sort(int* arry, int left, int right) {
	if ((right - left) <= 0) return;
	//添加一个三数取中的操作
	int key = arry[left];
	int end = right;
	int begin = left;
	while (left < right) {
		while (left < right && arry[right] >= key) {
			right--;
		}
		arry[left] = arry[right];
		while (left < right && arry[left] <= key) {
			left++;
		}
		arry[right] = arry[left];
	}
	arry[right] = key;
	dfs_quick_sort(arry,begin, left - 1);
	dfs_quick_sort(arry,right + 1, end);
}
//挖坑法
void quick_sort(int* arry, int size) {
	assert(arry);
	dfs_quick_sort(arry, 0, size - 1);
}

测试代码:

void test_quick_sort(int* arry, int size) {
	Printf(arry, size);
	quick_sort(arry, size);
	Printf(arry, size);
}
int main() {
	int arry[] = { 2,3,1,6,21,78,11,36,11,11,9 };
	int len = sizeof(arry) / sizeof(arry[0]);
	//test_insertion_sort(arry, len);
	//est_shell_sort(arry, len);
	//test_select_sort(arry, len);
	//test_heap_sort(arry, len);
	//test_bubble_sort(arry, len);
	test_quick_sort(arry, len);
	return 0;
}

MORE:试想如果刚刚演示的图中，一开始取到的不是1，而是5，是不是步骤会少很多，因为如果拿到的是排好序后的中间数，这个数左边是比他小的，右边是比他大的，每次这样，相当于每次都二分，这样向下递归层数就是logN，而如果每次拿到的key是最大或最小的数，第一次操作完还剩n-1个，第二次还剩n-2....。层数为n层，时间复杂度为N^2。

所以我们要尽量选到一个靠近排序好的中间的数，不要选到最大或最小的数为key。

下面将代码进行改进：（取最左边和最右边和中间三个值中的中间数）

int mid_quick_number(int* arry, int left, int right) {
	int mid = left + (right - left >> 1);//去中间数防止普通求中间数溢出问题
	if (arry[mid] > arry[left]) {
		if (arry[right] > arry[mid]) {
			mid = mid;
		}
		else if(arry[right]>arry[left]){
			mid = right;
		}
		else {
			mid = left;
		}
	}
	else {
		if (arry[right] < arry[mid]) {
			mid = mid;
		}
		else if (arry[right] > arry[left]) {
			mid = left;
		}
		else {
			mid = right;
		}
	}
	return mid;
}
void dfs_quick_sort(int* arry, int left, int right) {
	if ((right - left) <= 0) return;
	//添加一个三数取中的操作
	int mid = mid_quick_number(arry, left, right);
	swap(arry + mid, arry+left);
	int key = arry[left];
	int end = right;
	int begin = left;
	while (left < right) {
		while (left < right && arry[right] >= key) {
			right--;
		}
		arry[left] = arry[right];
		while (left < right && arry[left] <= key) {
			left++;
		}
		arry[right] = arry[left];
	}
	arry[right] = key;
	dfs_quick_sort(arry,begin, left - 1);
	dfs_quick_sort(arry,right + 1, end);
}
//挖坑法
void quick_sort(int* arry, int size) {
	assert(arry);
	dfs_quick_sort(arry, 0, size - 1);
}