C语言 快速排序

• 首先，定义两个指针left、right，分别指向当前数组的第一个元素和最后一个元素
• 将当前数组的第left个位置记为key
• 得到key的值之后，将right所指位置的元素与key值相比较，若小于key值，则将right所指位置的元素赋给left所指的元素，然后进行right–操作；否则，直接进行right–
• 再将left所指元素与key相比较，若大于key值，则将left所指位置的元素赋给right所指的元素，然后进行left++操作；否则，直接进行left++
• 知道left的值与right的值相等，将key的值赋给left所指的位置，并记下left的值。
• 此时，一趟排序完成，left左边均比left所指位置的值小，右边均比left所指位置的值大。相当于将一个数组分为两部分，之后再对这两部分进行快排。
• 运用递归思想，不断将一个数组按照一个特定值分为左边小于特定值和右边大于特定值。
  完整代码如下

#include
#include
#define Max 100


void QuickSort(int A[], int left, int right);      //快排
int Quickpass(int A[], int low, int high);     //一趟快排


int main()
{
	int n;
	printf("请输入要排序的元素的个数：");
	scanf("%d", &n);
	int i;
	int A[Max];
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &A[i]);     //输入数据，放入数组A中
	}
	QuickSort(A,1,n);   //快排
	for (i = 1; i <= n; i++)
	{
		printf("%dt", A[i]);    //打印排好序的数组
	}
	return 0;
}



void QuickSort(int A[], int left, int right)     //快排
{
	if (left < right)   
	{
		int pos = Quickpass(A, left, right);   //定位left和right相等时候的位置，此位置的左边比A[pos]小，右边比A[pos]大
		QuickSort(A, left, pos - 1);    //对pos左边，再进行一次快排
		QuickSort(A, pos + 1, right);   //对pos右边，再进行一次快排
	}
}



int Quickpass(int A[], int low, int high)    //一趟快排
{
	int key = A[low];
	while (low < high)
	{
		while (low < high && A[high] >= key)    //当high所指位置的值大于key时，high向前移动
			high--;
		A[low] = A[high];    //将high所指位置的值赋给low
		while (low < high && A[low] < key) 
			low++;
		A[high] = A[low];
	}
	A[low] = key;    //将key赋给low和high相等时候所指位置的值
	return low;      //并返回该位置
}