資料結構學習筆記 --- 排序（冒泡排序、快速排序）

1. 引言 

本文主要講解一些常見的排序算法。

2. 冒泡排序

冒泡排序是經過n-1趟子排序完成的，第i趟子排序從第1個數至第n-i個數，若第i個數比後一個數大（則升序，小則降序）則交換兩數。

#include "ds.h"

#define 	N 		8

// 将a中整數序列重新排列成自小至大有序的整數序列(起泡排序)
void bubble_sort(int a[],int n)
{
	int i, j, t;
	Status change;
	for (i = n - 1, change = TRUE; i > 0 && change; --i)
	{
		change = FALSE;
		for (j = 0; j < i; j++)
		{
			if (a[j] > a[j+1])
			{
				t      = a[j];
				a[j]   = a[j+1];
				a[j+1] = t;
				change = TRUE;
			}
		}
	}
}

void print(int r[],int n)
{
   	int i;
   	for(i = 0; i < n; i++)
     	printf("%d ", r[i]);
   	printf("\n");
}

int main()
{
   int d[N]={49,38,65,97,76,13,27,49};
   printf("排序前:\n");
   print(d,N);
   bubble_sort(d,N);
   printf("排序後:\n");
   print(d,N);
}
           

3. 快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。　

設要排序的數組是A[0]……A[N-1]，首先任意選取一個資料（通常選用第一個資料）作為關鍵資料，然後将所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時産生變動。

　　一趟快速排序的算法是： 　　1）設定兩個變量I、J，排序開始的時候：I=0，J=N-1； 　　2）以第一個數組元素作為關鍵資料，指派給 key ，即  key =A[0]； 　　3）從J開始向前搜尋，即由後開始向前搜尋（J=J-1即J--），找到第一個小于 key 的值A[j]，A[j]與A[i]交換； 　　4）從I開始向後搜尋，即由前開始向後搜尋（I=I+1即I++），找到第一個大于 key 的A[i]，A[i]與A[j]交換； 　　5）重複第3、4、5步，直到 I=J； (3,4步是在程式中沒找到時候j=j-1，i=i+1，直至找到為止。找到并交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後另循環結束。）

#include "ds.h"

#define 	MAX_SIZE 	20			// 一個用作示例的小順序表的最大長度
typedef		int			KeyType;	// 定義關鍵字類型為整型
typedef 	int 		InfoType; // 定義其它資料項的類型

#define 	EQ(a,b) 	((a)==(b))
#define 	LT(a,b) 	((a)<(b))
#define 	LQ(a,b) 	((a)<=(b))

struct RedType						// 記錄類型
{
	KeyType		key;				// 關鍵字項
	InfoType	otherinfo;			// 其它資料項，具體類型在主程中定義
};

struct SqList						// 順序表類型
{
	RedType		r[MAX_SIZE+1];		// r[0]閑置或用作哨兵單元
	int 		length;				// 順序表長度
};

// 交換順序表L中子表L.r[low..high]的記錄，使樞軸記錄到位，
// 并傳回其所在位置，此時在它之前(後)的記錄均不大(小)于它。算法10.6(a)
int Partition(SqList &L,int low,int high)
{
#if 1
  	KeyType pivotkey;
   	L.r[0] = L.r[low]; // 用子表的第一個記錄作樞軸記錄
   	pivotkey = L.r[low].key; // 樞軸記錄關鍵字
   	while(low < high)
   	{ // 從表的兩端交替地向中間掃描
     	while(low<high&&L.r[high].key>=pivotkey)
       		--high;
     	L.r[low]=L.r[high]; // 将比樞軸記錄小的記錄移到低端
     	
     	while(low<high&&L.r[low].key<=pivotkey)
       		++low;
     	L.r[high]=L.r[low]; // 将比樞軸記錄大的記錄移到高端
   }
   L.r[low] = L.r[0]; // 樞軸記錄到位
   return low; // 傳回樞軸位置
#else
	RedType	t;
	KeyType	pivotkey;
	pivotkey = L.r[low].key;		// 用子表的第一個記錄作樞軸記錄
	
	while (low < high)
	{
		// 從表的兩端交替地向中間掃描
		while (low < high && L.r[high].key >= pivotkey)
			--high;
		// 将比樞軸記錄小的記錄交換到低端
		t = L.r[low];
		L.r[low] = L.r[high];
		L.r[high] = t;
		
		while (low < high && L.r[low].key <= pivotkey)
			++low;
		
		// 将比樞軸記錄大的記錄交換到高端
		t = L.r[low];
		L.r[low] = L.r[high];
		L.r[high] = t;
	}
	return low;		// 傳回樞軸所在位置
#endif
}

// 快速排序的函數，包括算法10.7、10.8
void QSort(SqList &L, int low, int high)
{
	// 對順序表L中的子序列L.r[low..high]作快速排序。算法10.7
	int 	pivotloc;
	if (low < high)	// 長度大于1
	{
		pivotloc = Partition(L, low, high);	// 将L.r[low..high]一分為二
		QSort(L, low, pivotloc - 1);		// 對低子表遞歸排序，pivotloc是樞軸位置
		QSort(L, pivotloc + 1, high);		// 對高子表遞歸排序
	}
}

// 對順序表L作快速排序。
void QuickSort(SqList &L)
{
	QSort(L, 1, L.length);
}


void print(SqList L)
{
   	int i;
   	for(i = 1; i <= L.length; i++)
     	printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
   	printf("\n");
}

#define N 8
int main()
{
   RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   printf("排序前:\n");
   print(l);
   QuickSort(l);
   printf("排序後:\n");
   print(l);
}