[数据结构与算法]数据结构--快速排序

这里快速排序使用递归的形式实现

思想就是，取第一个元素与最后一个元素交换，设置一个Low指针指向数组的左边界，设置一个High指针指向数组的右边界-1（也就是倒数第二个元素）

Low向前遍历找比基准元素大的元素的索引，High指针向左边界找比基准元素小的元素

如果Low<High则交换两个索引对应的元素

否则，跳出循环（这时候说明某一个已经找不到比基准元素大或小的元素了，直接指向了基准元素）

跳出循环以后，调整基准元素位置，因为Low交换了前面的大元素，所以Low左边都是比基准元素小的，所以我们直接将Low对应的元素与基准元素交换位置，

最后更改边界，继续递归实现基准元素左边的排序和基准元素右边的排序

递归需要一个结束递归的条件，我们发现，如果基准元素在最右边，则它对右边的递归的边界就变成了（Low+1,Right）相当于Left=Right+1,Right=Right,左边界比右边界大了，这就是我们需要寻找的跳出递归第条件，同理在最左边的基准元素也会造成这样的结果，只不过变成了左边的元素列表最终排序都会出现上述的情况,或者只传入一个数的情况，也已经完成了排序，这时候就会使Left=Right

所以，我们在每个函数的前面加上一个判断条件，如果Left>=Right

话不多说，上代码

测试程序和定义的结构体

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 1000

struct LNode {
	int Data[MAXSIZE];  //Data为待排序序列数组 
	int Last;  //Last为最后一个元素的数组下标 
};
typedef struct LNode *List;

void quicksort(List L, int Left, int Right);

List Create()
{
	List L;
	L = (List)malloc(sizeof(struct LNode));
	int j = 0, ch;

	/*输入待排序序列，输入 ctrl+Z 结束*/
	while (scanf("%d", &ch) != EOF)
	{
		L->Data[j] = ch;
		j++;
	}
	L->Last = j - 1;
	return L;
}

int main()
{
	int i;
	List L = Create();

	quicksort(L, 0, L->Last);

	for (i = 0; i <= L->Last; i++)
		printf("%d ", L->Data[i]);

	return 0;
}

void quicksort(List L, int Left, int Right) {
	if (Left>= Right)
		return;
	int Low = Left;
	int High = Right - 1;
	int temp = 0;
	//先交换第一个与最后一个
	temp=L->Data[Left];
	L->Data[Left] = L->Data[Right];
	L->Data[Right] = temp;
	//交换排序
	for (;;) {
		//找大元素
		for (Low;Low<=Right; Low++) {
			if (L->Data[Low] >= L->Data[Right])
				break;
		}
		//找小元素
		for (High;High>=Left; High--) {
			if (L->Data[High] <= L->Data[Right])
				break;
		}
		//判断交换位置
		if (High > Low) {
			temp = L->Data[High];
			L->Data[High] = L->Data[Low];
			L->Data[Low] = temp;
		}
		else{
			break;//结束循环
		}
	
	}
	//将基准移动到正确位置
	temp = L->Data[Right];
	L->Data[Right] = L->Data[Low];
	L->Data[Low] = temp;
	//继续交换排序
	//递归解决左边
	quicksort(L, Left,Low - 1);
	//递归解决右边
	quicksort(L, Low + 1, Right);

}