[C++知识库]快速排序——C语言实现

基数

选取数组中的元素为“基数”

哨兵

设置两个哨兵，一个指向数组最左端（i），一个指向最右端（j）

步骤

1、 先使最右端的哨兵j向左一步一步的移动，直到遇到数组中的元素小于基数停下来

2、 移动最左端的哨兵i向右一步一步的移动，直到遇到数组中的元素大于基数停下来

3、 判断两个哨兵是否指向了同一个元素或者i>j，如果没有交换两个哨兵的元素，继续移动哨兵。若两个哨兵指向了同一个元素，交换基数与i指向的元素

4、 此时哨兵i指向的元素左边为小于基数的元素，右边为大于基数的 元素

5、 对基数左边的数据和右边的数据进行上述步骤，也即进行递归

举例

假如此时有一堆数据：4，9，3，6，2，5，1

• 选取基数：temp = 4
• 设置哨兵i、j，i指向4，j指向1
• 移动j，当遇到1，停下来;移动i，当遇到9，停下来。
• i != j,交换i与j指向的数据，此时数据：4,1,3,6,2,5,9，i指向1，j指向9
• 继续移动哨兵，当j遇到2，停下来，当i遇到6，停下来。
• i = j，交换i与j指向的数据，此时数据:4，1，3，2，6，5，9，i指向2，j指向6
• 继续移动哨兵，此时，i > j，交换基数与i指向的元素
• 此时数据为：2，1，3，4，6，5，9
• 已经满足基数大于左边、小于右边
• 对基数左边的数据和右边的数据分别进行上述步骤

代码

#include "stdio.h"

#define SIZE 8

void QuickSort(int arr[],int left,int right)
{
	int i,j,t,temp;

	if(left>right)
		return;

	temp = arr[left];
	i = left;
	j = right;

	while(i != j)
	{
		while(arr[j] >= temp && i < j)
			j--;
		while(arr[i] <= temp && i < j)
			i++;
		if(i < j)
		{
			t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	arr[left] = arr[i];
	arr[i] = temp;

	QuickSort(arr,left,i-1);  //基数左边数制
	QuickSort(arr,i+1,right); //基数右边数据

	return ;
}

int main(void)
{
    int arr[SIZE] = {6,20,7,32,1,8,12,9};

	printf("排序前:\n");
	for(int i=0;i<SIZE;i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
	QuickSort(arr,0, SIZE-1);
	printf("排序前后:\n");
	for(int i=0;i<SIZE;i++)
	{
		printf("%d ",arr[i]);
	}

}