資料結構——排序——快速排序

快速排序的基本思想是通過一輪排序将待排資料分為獨立的兩部分，其中一部分資料的關鍵字均比另一部分的關鍵字小，則可對這兩部分記錄繼續進行排序，以達到整個序列有序的目的 。就像切蘋果一樣，先将蘋果分為兩瓣，然後再分别對兩瓣蘋果繼續進行切分，其中用到的就是遞歸的思想，話不多少，直接上代碼：

#include"stdafx.h"
#include"stdlib.h"
#include"math.h"
using namespace std;

void swap(int k[], int low, int high)  //交換函數
{
	int temp;
	temp = k[high];
	k[high] = k[low];
	k[low] = temp;
}

int Partition(int k[], int low, int high)    //進行資料的排序
{
	int point;
	point = k[low];
	while (low < high)
	{
		while (low < high&&k[high] >= point)
		{
			high--;
		}
		swap(k, low, high);
		while (low < high&&k[low] <= point)
		{
			low++;
		}
		swap(k, low, high);
	}
	return high;

}

void Qsort(int k[], int low, int high)  //進行遞歸
{
	int point;
	if (low < high)
	{
		point = Partition(k,low,high);
		Qsort(k, low, point - 1);
		Qsort(k, point + 1, high);
	}
}

void quicksort(int k[], int n)
{
	Qsort(k, 0, n-1);
}
int main()
{
	int a[] = { 1,5,3,7,9,6,4 };
	quicksort(a,7);
	for (int i = 0; i < 7; ++i)
	{
		printf("%d", a[i]);
	}
}
           

 以上就是快排的實作代碼，對上述代碼進行優化的方法主要包括以下四種：1、優化選取樞軸 2、優化不必要的交換 3、使用尾遞歸優化遞歸操作 4、優化數組較小時的排序方案 下文展示了采用四種方法進行優化後的快排代碼：

#include"stdafx.h"
#include"stdlib.h"
#include"math.h"
using namespace std;
#define MAX_LENGTH_INSERT_SORT 7

void swap(int k[], int low, int high)
{
	int temp;
	temp = k[high];
	k[high] = k[low];
	k[low] = temp;
}

void Isort(int k[], int n)  //小數組用直接插入排序
{
	int i, j, temp;
	for(i=1;i<n;i++)
	{
		if (k[i] < k[i - 1])
		{
			temp = k[i];
			for (j = i - 1; k[j] > temp; j--)
			{
				k[j + 1] = k[j];
			}
			k[j + 1] = temp;
		}
	}
}
void insertsort(int k[], int low,int high)
{
	Isort(k + low, high - low + 1);
}

int Partition(int k[], int low, int high)
{
	int m = low + (high - low) / 2;    //三數取中法
	if (k[high] > k[low])
		swap(k, low, high);
	if (k[high] < k[m])
		swap(k, m, high);
	if (k[m] > k[low])
		swap(k, m, low);
	int point;
	point = k[low];
	while (low < high)
	{
		while (low < high&&k[high] >= point)
		{
			high--;
		}
		k[low] = k[high];
		while (low < high&&k[low] <= point)
		{
			low++;
		}
		k[high] = k[low];
		k[low] = point;
	}
	return high;

}

void Qsort(int k[], int low, int high)
{
	int point;
	if ((high - low) > MAX_LENGTH_INSERT_SORT)
	{
		point = Partition(k, low, high);
		Qsort(k, low, point - 1);
		low = point + 1;               //尾遞歸
	}
	else
		insertsort(k,low,high);
}

void quicksort(int k[], int n)
{
	Qsort(k, 0, n-1);
}
int main()
{
	int a[] = { 1,5,3,7,9,6,4 };
	quicksort(a,7);
	for (int i = 0; i < 7; ++i)
	{
		printf("%d", a[i]);
	}
}
           

至今快排算法在優化後，依然是排序算法裡的王者，裡面優化算法的思想需要學以緻用，尾遞歸，三數取中法都是需要認真掌握的概念。