交換排序（快速排序 冒泡排序）

1.快速排序：先從數列中取出一個數作為基準數；分區過程，将比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊；再對左右區間重複第二步，直到各區間隻有一個數。

以一個數組作為示例，取區間第一個數為基準數。

1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始時，i = 0;  j = 9;   X = a[i] = 72

由于已經将a[0]中的數儲存到X中，可以了解成在數組a[0]上挖了個坑，可以将其它資料填充到這來。從j開始向前找一個比X小或等于X的數。當j=8，符合條件，将a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++;  這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎麼辦了？簡單，再找數字來填a[8]這個坑。這次從i開始向後找一個大于X的數，當i=3，符合條件，将a[3]挖出再填到上一個坑中a[8]=a[3]; j--;當i=5時，由于i==j退出。此時，i = j = 5，而a[5]剛好又是上次挖的坑，是以将X填入a[5]。

/*快速排序*/ 
#include <iostream>
using namespace std;

const int MAXN = 100;
int n;
void quick_sort(int s[], int left, int right)
{
	if(left<right)
	{
		int pole = s[left];
		int i = left;
		int j = right;
		while(i<j)
		{
			while(i<j&&s[j]>=pole)//while(i<j&&s[j]<=pole)
			{//從後向前尋找可以填前面第i個坑的 
				j--;
			}
			s[i] = s[j];//把第j 個填到了前面，第j個空缺 
			while(i<j&&s[i]<pole)//while(i<j&&s[i]>pole)
			{
				i++;
			}
			s[j] = s[i];
		}
		s[i] = pole;
		
//		for(int k = 0; k<n-1; k++)//輸出過程 
//		printf("%d ",s[k]);
//		printf("%d\n",s[n-1]);
		
		quick_sort(s, left, i-1);
		quick_sort(s, i+1, right);
	}//left == right;
}
 
int main() 
{
	int s[MAXN];
	scanf("%d",&n);
	for(int i = 0; i<n; i++)
	{
		scanf("%d",&s[i]);
	}
	quick_sort(s, 0, n-1);
	
	for(int k = 0; k<n-1; k++)
	printf("%d ",s[k]);
	printf("%d\n",s[n-1]);
	
	return 0;
} 
           

二．交換排序

冒泡排序：冒泡排序是最簡單的排序之一了，其大體思想就是通過與相鄰元素的比較和交換來把小的數交換到最前面。這個過程類似于水泡向上升一樣，是以而得名。舉個栗子，對5,3,8,6,4這個無序序列進行冒泡排序。首先從後向前冒泡，4和6比較，把4交換到前面，序列變成5,3,8,4,6。同理4和8交換，變成5,3,4,8,6,3和4無需交換。5和3交換，變成3,5,4,8,6,3.這樣一次冒泡就完了，把最小的數3排到最前面了。對剩下的序列依次冒泡就會得到一個有序序列。冒泡排序的時間複雜度為O(n^2)。

/*冒泡排序*/
#include <iostream>
using namespace std;
const int MAXN = 100;

void swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

void Print(int arr[], int n, int i)
{
	printf("%d: ",i);
	for(int j = 0; j<n-1; j++)
	{
		printf("%d ",arr[j]);
	}
	printf("%d\n",arr[n-1]);
}

void BubbleSort(int arr[], int n)
{
	for(int i = 0; i<n-1; i++)//進行n-1次,每一次都會定下一個最小的 
	{
		for(int j = n-1; j>i; j--)
		{
			if(arr[j]<arr[j-1])
			swap(arr, j-1, j);
		}
		Print(arr, n, i+1);
	}
}

int main()
{
	int arr[MAXN], n;
	scanf("%d",&n);
	for(int i = 0; i<n; i++)
	{
		scanf("%d",&arr[i]);
	}
	BubbleSort(arr, n);
}  
           

快速排序講解部分來自：http://blog.csdn.net/morewindows/article/details/6684558講的很清楚推薦！