數據結構之---C語言實現快速排序（多個版本）

數據結構之---C語言實現快速排序（多個版本）

快速排序基本上有如下版本

一、國內教材雙向掃描版
二、單向掃描版本
三、隨機化版本
四、三數取中分割法
五、非遞歸版

這裡給我前兩個版本（較為常用）

版本一：

雙向掃描版本：

如圖：

代碼如下：

//快速排序(版本一)
//帶樞軸
//楊鑫
#include 
#include 
#define MAXN 100
int a[MAXN + 1], n;
void QuickSort(int left, int right)
{
	int i, j, t, temp;
	if(left > right)
			return;
	temp = a[left];
	i = left;
	j = right;
	while(i != j)
	{
		while(a[j] >= temp && i < j)
		{
			j--;
		}
		while(a[i] <= temp && i < j)
		{
			i++;
		}
		if(i < j)
		{
			t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	a[left] = a[i];
	a[i] = temp;
	QuickSort(left, i - 1);
	QuickSort(i + 1, right);
}
int main()
{
	printf(=========快速排序版本一==========
);
	int i = 0, j, t, count = 0;
	int T;
	printf(請輸入要對數據排序的個數:
);
	scanf(%d, &T);
	while(T--)
	{
		scanf(%d, &a[i]);
	    i++;	
	}
	QuickSort(0, i - 1);
	printf(排序後的數據是:
);
	for(j = 0; j < i; j++)
	{
		printf(%d , a[j]);
	}
	return 0;
}

版本二：

單項掃描：

void quickSort2(int x[], int l, int r)
{
	if(l >= r)
		return;
	int m = l;
	for(int i = l + l; i <= r; i++ )
        {
		if(x[i] < x[l])
                {
			swap2(x[++m], x[i]);
		}
	}
	swap2(x[l], x[m]);
	quickSort2(x, l, m - 1);
	quickSort2(x, m + 1, r);

}
void swap2(int &a,int &b)
{
	if(a==b) return;//對同一地址的數據交換，會使其結果為0
	a=a^b;
	b=a^b;
	a=a^b;
}