排序算法 - Passion of life

插入排序（Insertion Sort）

具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后

重复步骤2~5

平均时间复杂度为

C代码如下：

/**
*Insertion sort algorithm
*Time complexity O(N^2)
*@param int a[], the array beening sorted
*@param unsigned int n, number of array
*/
void insertion_sort(int a[], unsigned int n);

void insertion_sort(int a[], unsigned int n) {
	unsigned i = 1, j;
	for (; i < n; i++) {
		int temp = a[i];
		for (j = i; j > 0 && a[j-1] > temp; j--) {
			a[j] = a[j-1];
		}
		a[j] = temp;
	}
}

希尔排序（Shell Sort）

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。原始的算法实现在最坏的情况下需要进行\(O(n^2)\)的比较和交换。V. Pratt的书对算法进行了少量修改，可以使得性能提升至\(O(nlog^2n)\)。这比最好的比较算法的\(O(nlogn)\)要差一些。

假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长串行都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
c语言实现如下：

void shell_sort(int a[], unsigned int n) {
	int gap = 0;
	while (gap <= (signed)n)
		gap = gap * 3 + 1; //{1, 4, 7, 10, 13, 16...}

	while (gap > 0) {
		for (int i = gap; i < (signed)n; i++) {
			int j = i - gap;
			int temp = a[i];
			while (j >= 0 && a[j] > temp) {
				a[j+gap] = a[j];
				j -= gap;
			}
			a[j+gap] = temp;
		}
		gap = (gap - 1) / 3;
	}
}

堆排序（Heapsort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

父节点i的左子节点在位置 (2i+1);
父节点i的右子节点在位置 (2i+2);
子节点i的父节点在位置 floor((i-1)/2);

在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

代码来自wikipedia:

#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

int parent(int);
int left(int);
int right(int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int [], int);
void print(int [], int);
void HeapSort(int [], int);

/*父結點*/
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}

/*左子結點*/
int left(int i)
{
    return (2 * i + 1);
}

/*右子結點*/
int right(int i)
{
    return (2 * i + 2);
}

/*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if(l < heap_size && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r < heap_size && A[r] > A[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        Max_Heapify(A, largest, heap_size);
    }
}

/*建立最大堆積樹*/
void Build_Max_Heap(int A[]，int heap_size)
{
    for(int i = (heap_size-2)/2; i >= 0; i--)
    {
        Max_Heapify(A, i, heap_size);
    }
}

/*印出樹狀結構*/
void print(int A[]， int heap_size)
{
    for(int i = 0; i < heap_size;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}

/*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
    Build_Max_Heap(A, heap_size);
    int temp;
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        Max_Heapify(A, 0, i);
    }
    print(A, heap_size);
}

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
步骤为：

从数列中挑出一个元素，称为 “基准”（pivot）。
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

快速排序的平均时间复杂度为

实现代码如下：

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#ifndef MAX_SIZE
#define MAX_SIZE 1000
#endif

void quicksort(int a[], int low, int high);
void swap(int a[], int i, int j);

void quicksort(int a[], int low, int high) {
	if (low < high) {
		int i, j, pivot, key;
		pivot = (low + high) / 2;
		key = a[pivot];
		/*put the key in the first*/
		swap(a, low, pivot);
		i = low + 1;
		j = high;
		while (i <= j) {
			while (i <= high && a[i] <= key) i++;
			while (j >= low && a[j] > key) j--;
			if (i < j)
				swap(a, i, j);
		}

		swap(a, low, j);
		quicksort(a, low, j - 1);
		quicksort(a, j + 1, high);
	}
}

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

int main(int argc, char const *argv[])
{
	int a[MAX_SIZE] = {INT_MAX};
	unsigned int i = 0;
	FILE* fp1 = fopen("data1.txt", "wa");
	FILE* fp2 = fopen("data2.txt", "wa");

	for (; i < MAX_SIZE; i++) {
		a[i] = rand();
	}

	for (i = 0; i < MAX_SIZE; i++) {
		fprintf(fp1, "%d\t", a[i]);
	}

	quicksort(a, 0, MAX_SIZE - 1);

	for (i = 0; i < MAX_SIZE; i++) {
		fprintf(fp2, "%d\t", a[i]);
	}

	return 0;
}

这里随机产生1000个数字的数组，然后排序。
data1.txt:

41	18467	6334	26500	19169	15724	11478	29358	26962	24464	5705	28145	23281	16827	9961	491	2995	11942	4827	5436	32391	14604	3902	153	292	12382	17421	18716	19718	19895	5447	21726	14771	11538	1869	19912	25667	26299	17035	9894	28703	23811	31322	30333	17673	4664	15141	7711	28253	6868	25547	27644	32662	32757	20037	12859	8723	9741	27529	778	12316	3035	22190	1842	288	30106	9040	8942	19264	22648	27446	23805	15890	6729	24370	15350	15006	31101	24393	3548	19629	12623	24084	19954	18756	11840	4966	7376	13931	26308	16944	32439	24626	11323	5537	21538	16118	2082	22929	16541	4833	31115	4639	29658	22704	9930	13977	2306	31673	22386	5021	28745	26924	19072	6270	5829	26777	15573	5097	16512	23986	13290	9161	18636	22355	24767	23655	15574	4031	12052	27350	1150	16941	21724	13966	3430	31107	30191	18007	11337	15457	12287	27753	10383	14945	8909	32209	9758	24221	18588	6422	24946	27506	13030	16413	29168	900	32591	18762	1655	17410	6359	27624	20537	21548	6483	27595	4041	3602	24350	10291	30836	9374	11020	4596	24021	27348	23199	19668	24484	8281	4734	53	1999	26418	27938	6900	3788	18127	467	3728	14893	24648	22483	17807	2421	14310	6617	22813	9514	14309	7616	18935	17451	20600	5249	16519	31556	22798	30303	6224	11008	5844	32609	14989	32702	3195	20485	3093	14343	30523	1587	29314	9503	7448	25200	13458	6618	20580	19796	14798	15281	19589	20798	28009	27157	20472	23622	18538	12292	6038	24179	18190	29657	7958	6191	19815	22888	19156	11511	16202	2634	24272	20055	20328	22646	26362	4886	18875	28433	29869	20142	23844	1416	21881	31998	10322	18651	10021	5699	3557	28476	27892	24389	5075	10712	2600	2510	21003	26869	17861	14688	13401	9789	15255	16423	5002	10585	24182	10285	27088	31426	28617	23757	9832	30932	4169	2154	25721	17189	19976	31329	2368	28692	21425	10555	3434	16549	7441	9512	30145	18060	21718	3753	16139	12423	16279	25996	16687	12529	22549	17437	19866	12949	193	23195	3297	20416	28286	16105	24488	16282	12455	25734	18114	11701	31316	20671	5786	12263	4313	24355	31185	20053	912	10808	1832	20945	4313	27756	28321	19558	23646	27982	481	4144	23196	20222	7129	2161	5535	20450	11173	10466	12044	21659	26292	26439	17253	20024	26154	29510	4745	20649	13186	8313	4474	28022	2168	14018	18787	9905	17958	7391	10202	3625	26477	4414	9314	25824	29334	25874	24372	20159	11833	28070	7487	28297	7518	8177	17773	32270	1763	2668	17192	13985	3102	8480	29213	7627	4802	4099	30527	2625	1543	1924	11023	29972	13061	14181	31003	27432	17505	27593	22725	13031	8492	142	17222	31286	13064	7900	19187	8360	22413	30974	14270	29170	235	30833	19711	25760	18896	4667	7285	12550	140	13694	2695	21624	28019	2125	26576	21694	22658	26302	17371	22466	4678	22593	23851	25484	1018	28464	21119	23152	2800	18087	31060	1926	9010	4757	32170	20315	9576	30227	12043	22758	7164	5109	7882	17086	29565	3487	29577	14474	2625	25627	5629	31928	25423	28520	6902	14962	123	24596	3737	13261	10195	32525	1264	8260	6202	8116	5030	20326	29011	30771	6411	25547	21153	21520	29790	14924	30188	21763	4940	20851	18662	13829	30900	17713	18958	17578	8365	13007	11477	1200	26058	6439	2303	12760	19357	2324	6477	5108	21113	14887	19801	22850	14460	22428	12993	27384	19405	6540	31111	28704	12835	32356	6072	29350	18823	14485	20556	23216	1626	9357	8526	13357	29337	23271	23869	29361	12896	13022	29617	10112	12717	18696	11585	24041	24423	24129	24229	4565	6559	8932	22296	29855	12053	16962	3584	29734	6654	16972	21457	14369	22532	2963	2607	2483	911	11635	10067	22848	4675	12938	2223	22142	23754	6511	22741	20175	21459	17825	3221	17870	1626	31934	15205	31783	23850	17398	22279	22701	12193	12734	1637	26534	5556	1993	10176	25705	6962	10548	15881	300	14413	16641	19855	24855	13142	11462	27611	30877	20424	32678	1752	18443	28296	12673	10040	9313	875	20072	12818	610	1017	14932	28112	30695	13169	23831	20040	26488	28685	19090	19497	2589	25990	15145	19353	19314	18651	26740	22044	11258	335	8759	11192	7605	25264	12181	28503	3829	23775	20608	29292	5997	17549	29556	25561	31627	6467	29541	26129	31240	27813	29174	20601	6077	20215	8683	8213	23992	25824	5601	23392	15759	2670	26428	28027	4084	10075	18786	15498	24970	6287	23847	32604	503	21221	22663	5706	2363	9010	22171	27489	18240	12164	25542	7619	20913	7591	6704	31818	9232	750	25205	4975	1539	303	11422	21098	11247	13584	13648	2971	17864	22913	11075	21545	28712	17546	18678	1769	15262	8519	13985	28289	15944	2865	18540	23245	25508	28318	27870	9601	28323	21132	24472	27152	25087	28570	29763	29901	17103	14423	3527	11600	26969	14015	5565	28	21543	25347	2088	2943	12637	22409	26463	5049	4681	1588	11342	608	32060	21221	1758	29954	20888	14146	690	7949	12843	21430	25620	748	27067	4536	20783	18035	32226	15185	7038	9853	25629	11224	15748	19923	3359	32257	24766	4944	14955	23318	32726	25411	21025	20355	31001	22549	9496	18584	9515	17964	23342	8075	17913	16142	31196	21948	25072	20426	14606	26173	24429	32404	6705	20626	29812	19375	30093	16565	16036	14736	29141	30814	5994	8256	6652	23936	30838	20482	1355	21015	1131	18230	17841	14625	2011	32637	4186	19690	1650	5662	21634	10893	10353	21416	13452	14008	7262	22233	5454	16303	16634	26303	14256	148	11124	12317	4213	27109	24028	29200	21080	21318	16858	24050	24155	31361	15264	11903	3676	29643	26909	14902	3561	28489	24948	1282	13653	30674	2220	5402	6923	3831	19369	3878	20259	19008	22619	23971	30003	21945	9781	26504	12392	32685	25313	6698	5589	12722	5938	19037	6410	31461	6234	12508	9961	3959	6493	1515	25269	24937	28869	58	14700	13971	26264	15117	16215	24555	7815	18330	3039	30212	29288	28082	1954	16085	20710	24484	24774	8380	29815	25951	6541	18115	1679	17110	25898	23073	788	23977	18132	29956	28689	26113	10008	12941	15790	1723	21363	28	25184	24778	7200	5071	1885	21974	1071	11333	22867	26153	14295	32168	20825	9676	15629	28650	2598	3309	4693	4686	30080	10116	12249

data2.txt:

28	28	41	53	58	123	140	142	148	153	193	235	288	292	300	303	335	467	481	491	503	608	610	690	748	750	778	788	875	900	911	912	1017	1018	1071	1131	1150	1200	1264	1282	1355	1416	1515	1539	1543	1587	1588	1626	1626	1637	1650	1655	1679	1723	1752	1758	1763	1769	1832	1842	1869	1885	1924	1926	1954	1993	1999	2011	2082	2088	2125	2154	2161	2168	2220	2223	2303	2306	2324	2363	2368	2421	2483	2510	2589	2598	2600	2607	2625	2625	2634	2668	2670	2695	2800	2865	2943	2963	2971	2995	3035	3039	3093	3102	3195	3221	3297	3309	3359	3430	3434	3487	3527	3548	3557	3561	3584	3602	3625	3676	3728	3737	3753	3788	3829	3831	3878	3902	3959	4031	4041	4084	4099	4144	4169	4186	4213	4313	4313	4414	4474	4536	4565	4596	4639	4664	4667	4675	4678	4681	4686	4693	4734	4745	4757	4802	4827	4833	4886	4940	4944	4966	4975	5002	5021	5030	5049	5071	5075	5097	5108	5109	5249	5402	5436	5447	5454	5535	5537	5556	5565	5589	5601	5629	5662	5699	5705	5706	5786	5829	5844	5938	5994	5997	6038	6072	6077	6191	6202	6224	6234	6270	6287	6334	6359	6410	6411	6422	6439	6467	6477	6483	6493	6511	6540	6541	6559	6617	6618	6652	6654	6698	6704	6705	6729	6868	6900	6902	6923	6962	7038	7129	7164	7200	7262	7285	7376	7391	7441	7448	7487	7518	7591	7605	7616	7619	7627	7711	7815	7882	7900	7949	7958	8075	8116	8177	8213	8256	8260	8281	8313	8360	8365	8380	8480	8492	8519	8526	8683	8723	8759	8909	8932	8942	9010	9010	9040	9161	9232	9313	9314	9357	9374	9496	9503	9512	9514	9515	9576	9601	9676	9741	9758	9781	9789	9832	9853	9894	9905	9930	9961	9961	10008	10021	10040	10067	10075	10112	10116	10176	10195	10202	10285	10291	10322	10353	10383	10466	10548	10555	10585	10712	10808	10893	11008	11020	11023	11075	11124	11173	11192	11224	11247	11258	11323	11333	11337	11342	11422	11462	11477	11478	11511	11538	11585	11600	11635	11701	11833	11840	11903	11942	12043	12044	12052	12053	12164	12181	12193	12249	12263	12287	12292	12316	12317	12382	12392	12423	12455	12508	12529	12550	12623	12637	12673	12717	12722	12734	12760	12818	12835	12843	12859	12896	12938	12941	12949	12993	13007	13022	13030	13031	13061	13064	13142	13169	13186	13261	13290	13357	13401	13452	13458	13584	13648	13653	13694	13829	13931	13966	13971	13977	13985	13985	14008	14015	14018	14146	14181	14256	14270	14295	14309	14310	14343	14369	14413	14423	14460	14474	14485	14604	14606	14625	14688	14700	14736	14771	14798	14887	14893	14902	14924	14932	14945	14955	14962	14989	15006	15117	15141	15145	15185	15205	15255	15262	15264	15281	15350	15457	15498	15573	15574	15629	15724	15748	15759	15790	15881	15890	15944	16036	16085	16105	16118	16139	16142	16202	16215	16279	16282	16303	16413	16423	16512	16519	16541	16549	16565	16634	16641	16687	16827	16858	16941	16944	16962	16972	17035	17086	17103	17110	17189	17192	17222	17253	17371	17398	17410	17421	17437	17451	17505	17546	17549	17578	17673	17713	17773	17807	17825	17841	17861	17864	17870	17913	17958	17964	18007	18035	18060	18087	18114	18115	18127	18132	18190	18230	18240	18330	18443	18467	18538	18540	18584	18588	18636	18651	18651	18662	18678	18696	18716	18756	18762	18786	18787	18823	18875	18896	18935	18958	19008	19037	19072	19090	19156	19169	19187	19264	19314	19353	19357	19369	19375	19405	19497	19558	19589	19629	19668	19690	19711	19718	19796	19801	19815	19855	19866	19895	19912	19923	19954	19976	20024	20037	20040	20053	20055	20072	20142	20159	20175	20215	20222	20259	20315	20326	20328	20355	20416	20424	20426	20450	20472	20482	20485	20537	20556	20580	20600	20601	20608	20626	20649	20671	20710	20783	20798	20825	20851	20888	20913	20945	21003	21015	21025	21080	21098	21113	21119	21132	21153	21221	21221	21318	21363	21416	21425	21430	21457	21459	21520	21538	21543	21545	21548	21624	21634	21659	21694	21718	21724	21726	21763	21881	21945	21948	21974	22044	22142	22171	22190	22233	22279	22296	22355	22386	22409	22413	22428	22466	22483	22532	22549	22549	22593	22619	22646	22648	22658	22663	22701	22704	22725	22741	22758	22798	22813	22848	22850	22867	22888	22913	22929	23073	23152	23195	23196	23199	23216	23245	23271	23281	23318	23342	23392	23622	23646	23655	23754	23757	23775	23805	23811	23831	23844	23847	23850	23851	23869	23936	23971	23977	23986	23992	24021	24028	24041	24050	24084	24129	24155	24179	24182	24221	24229	24272	24350	24355	24370	24372	24389	24393	24423	24429	24464	24472	24484	24484	24488	24555	24596	24626	24648	24766	24767	24774	24778	24855	24937	24946	24948	24970	25072	25087	25184	25200	25205	25264	25269	25313	25347	25411	25423	25484	25508	25542	25547	25547	25561	25620	25627	25629	25667	25705	25721	25734	25760	25824	25824	25874	25898	25951	25990	25996	26058	26113	26129	26153	26154	26173	26264	26292	26299	26302	26303	26308	26362	26418	26428	26439	26463	26477	26488	26500	26504	26534	26576	26740	26777	26869	26909	26924	26962	26969	27067	27088	27109	27152	27157	27348	27350	27384	27432	27446	27489	27506	27529	27593	27595	27611	27624	27644	27753	27756	27813	27870	27892	27938	27982	28009	28019	28022	28027	28070	28082	28112	28145	28253	28286	28289	28296	28297	28318	28321	28323	28433	28464	28476	28489	28503	28520	28570	28617	28650	28685	28689	28692	28703	28704	28712	28745	28869	29011	29141	29168	29170	29174	29200	29213	29288	29292	29314	29334	29337	29350	29358	29361	29510	29541	29556	29565	29577	29617	29643	29657	29658	29734	29763	29790	29812	29815	29855	29869	29901	29954	29956	29972	30003	30080	30093	30106	30145	30188	30191	30212	30227	30303	30333	30523	30527	30674	30695	30771	30814	30833	30836	30838	30877	30900	30932	30974	31001	31003	31060	31101	31107	31111	31115	31185	31196	31240	31286	31316	31322	31329	31361	31426	31461	31556	31627	31673	31783	31818	31928	31934	31998	32060	32168	32170	32209	32226	32257	32270	32356	32391	32404	32439	32525	32591	32604	32609	32637	32662	32678	32685	32702	32726	32757