C语言数据结构与算法---快速排序

快速排序—改进的交换排序

基本思想：

• 任取一个元素（如：第一个）为中心
• 所有比它小的元素一律前放，比它大的一律后放，形成左右两个子表
• 对各子表重新选择中心元素并依此规则调整
• 直到每个子表的元素只剩一个

该方法太浪费空间，需要许多空间

改进如下：只需要一个额外的位置

依此将后续的值与所选界点进行比较
比界点大的不移动（low++或high–），比界点小的移动到前面

前面有空，从后面移动一个比界点大的；
后面有空，从前面移动一个比界点小的。


当low = high 时不用继续了，并将 0 号位置的中心点放到该位置上

此时被分成了两个子表，分别继续重复操作


代码实现
此代码又对上述进行优化，没有一个空位置，直接将两个值与基准数（界点）比较

//从大到小排序
void quicksort(int b[], int* pcount, int left, int right)
{
	int i, j, t, temp;
	if (left > right)
	{
		return;
	}
	temp = b[left]; //temp中存的就是基准数
	i = left;
	j = right;
	while (i != j)
	{   
		//顺序很重要，要先从右边开始找
		while (b[j] <= temp && i < j)
		{
			j--;
		}

		while (b[i] >= temp && i < j)//再找左边的
		{
			i++;
		}
		if (i < j)//交换两个数在数组中的位置
		{
			(*pcount)++;
			t = b[i];
			b[i] = b[j];
			b[j] = t;
		}
	}
	//最终将基准数归位
	b[left] = b[i];
	b[i] = temp;
	quicksort(b, pcount, left, i - 1);//继续处理左边的，这里是一个递归的过程
	quicksort(b, pcount, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
}

int main()
{
	int a[10] = { 12,14,78,45,45,47,-12,8,17,19 };
	int count = 0;
	int i;
	int n = 10;
	quicksort(a, &count, 0, n - 1);//快速排序调用
	//输出排序后的结果
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n一共交换了%d次\n", count);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53