前言

為什么要學(xué)習(xí)排序算法？
根據(jù)統(tǒng)計(jì)，早起大型機(jī)CPU資源的四分之一都花在了數(shù)據(jù)排序上面。排序算法作為最基礎(chǔ)的算法，各種操作系統(tǒng)、編程語(yǔ)言都提供了內(nèi)置的實(shí)現(xiàn)。既然排序?qū)崿F(xiàn)隨處可見，我們?yōu)槭裁催€要自己動(dòng)手實(shí)現(xiàn)呢？雖然經(jīng)典算法要?jiǎng)邮謱憣懠由钣∠蟮牡览矶级?，但直到最近才發(fā)現(xiàn)，每種排序算法里都“暗藏玄機(jī)”。排序算法看似簡(jiǎn)單，其實(shí)不同的算法中蘊(yùn)涵著經(jīng)典的算法策略。通過熟練掌握排序算法，就可以掌握基本的算法設(shè)計(jì)思想，包括暴力枚舉法、時(shí)間空間置換、子問題的分治以及隨機(jī)化。

目錄

一.排序的概念及其應(yīng)用
二.排序分類
1.插入排序
2.選擇排序
3.交換排序
4.歸并排序

一.排序的概念及其應(yīng)用

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍
在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

1.2排序運(yùn)用

1.3 常見的排序算法

// 排序?qū)崿F(xiàn)的接口
// 插入排序
void InsertSort(int* a, int n);
// 希爾排序
void ShellSort(int* a, int n);
// 選擇排序
比特就業(yè)課
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序
void QuickSort(int* a, int left, int right);
// 歸并排序
void MergeSort(int* a, int n)
// 測(cè)試排序的性能對(duì)比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int)*N);
	int* a2 = (int*)malloc(sizeof(int)*N);
	int* a3 = (int*)malloc(sizeof(int)*N);
	int* a4 = (int*)malloc(sizeof(int)*N);
	int* a5 = (int*)malloc(sizeof(int)*N);
	int* a6 = (int*)malloc(sizeof(int)*N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N-1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

二.排序算法分類

1.插入排序

1.1基本思想：

直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想

1.2直接插入排序：

當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置
上的元素順序后移

直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
2. 時(shí)間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

代碼實(shí)現(xiàn)：

打印數(shù)組中的元素的函數(shù)

// 假設(shè)都用升序來講，降序就是反過來

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

// 插入排序
// 時(shí)間復(fù)雜度是多少？O(N^2)
// 什么情況下最壞？逆序  1+2+3+...+n-1
// 什么情況下最好？順序有序  O(N)
void InsertSort(int* a, int n)
{
	// [0, end]有序  end+1位置的值插入[0, end]，讓[0, end+1]有序
	for (int i = 0; i < n-1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void TestInsertSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	InsertSort(a, sizeof(a) / sizeof(int));
	printf("InsertSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

運(yùn)行結(jié)果：

1.3 希爾排序( 縮小增量排序 )

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取，重
復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序的特性總結(jié)：

1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，需要進(jìn)行推導(dǎo)，推導(dǎo)出來平均時(shí)間復(fù)雜度： O(N^1.3—N2）
4. 穩(wěn)定性：不穩(wěn)定

代碼實(shí)現(xiàn)：

// 直接插入排序的基礎(chǔ)上的優(yōu)化
// 1、先進(jìn)行預(yù)排序，讓數(shù)組接近有序
// 2、直接插入排序
// 時(shí)間復(fù)雜度：O(logN*N) 或者 O(log3N*N)
// 平均的時(shí)間復(fù)雜度是O(N^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;

	while (gap > 1)
	{
		//gap = gap / 2;  // logN
		gap = gap / 3 + 1; // log3N 以3為底數(shù)的對(duì)數(shù)
		// gap > 1時(shí)都是預(yù)排序  接近有序
		// gap == 1時(shí)就是直接插入排序 有序

		// gap很大時(shí)，下面預(yù)排序時(shí)間復(fù)雜度O(N)
		// gap很小時(shí)，數(shù)組已經(jīng)很接近有序了，這時(shí)差不多也是(N)

		// 把間隔為gap的多組數(shù)據(jù)同時(shí)排
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}	
}


//希爾排序測(cè)試
void TestShellSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	ShellSort(a, sizeof(a) / sizeof(int));
	printf("ShellSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	//TestInsertSort();
	TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

運(yùn)行結(jié)果：

2選擇排序

2.1基本思想：

每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

2.2 直接選擇排序:

在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素
若它不是這組元素中的最后一個(gè)(第一個(gè))元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個(gè)元素

直接選擇排序的特性總結(jié)：

1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
2. 時(shí)間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

代碼實(shí)現(xiàn)：

//交換函數(shù)
void Swap(int* p1, int* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

// 選擇排序
void SelectSort(int* a, int n)
{
	int start = 0;
	int end = n - 1;
	while (start < end)
	{
		int mini = start;
		int maxi = start;
		//找出數(shù)組中最大的數(shù)和最小的數(shù)
		for (int i = start; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//把最小的數(shù)和start位置的數(shù)進(jìn)行交換
		Swap(&a[start], &a[mini]);
		if (a[start] == a[maxi])
		{
			maxi = mini;
		}
		//把最大的數(shù)和end 位置的數(shù)交換
		Swap(&a[end], &a[maxi]);
		start++;
		end--;
	}
}

//直接選擇排序測(cè)試
void TestSelectSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	SelectSort(a, sizeof(a) / sizeof(int));
	printf("SelectSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

運(yùn)行結(jié)果：

2.3 堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

堆排序的特性總結(jié)：

1. 堆排序使用堆來選數(shù)，效率就高了很多。
2. 時(shí)間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

代碼實(shí)現(xiàn)：

// 堆排序

//建堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	//默認(rèn)左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child += 1;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//新堆中的最大數(shù)跟最后面那個(gè)數(shù)交換
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}
//堆排序測(cè)試
void TestHeapSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	HeapSort(a, sizeof(a) / sizeof(int));
	printf("HeapSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	TestHeapSort();
	//TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

代碼運(yùn)行結(jié)果：

3. 交換排序

基本思想：所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來對(duì)換這兩個(gè)記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移
動(dòng)。

3.1冒泡排序

冒泡排序的特性總結(jié)：

1. 冒泡排序是一種非常容易理解的排序
2. 時(shí)間復(fù)雜度：O(N^2)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定

代碼實(shí)現(xiàn)：

// 冒泡排序
// 時(shí)間復(fù)雜度：O（N*N）
// 最好情況:O(N)
// N-1
// N-2
// ...
// 跟直接插入排序相比？誰(shuí)更好 -》 直接插入更好
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

//冒泡排序測(cè)試
void TestBubbleSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	printf("BubbleSort: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	TestBubbleSort();
	//TestPartSort2();

	//TestOP()
	return 0;
}

3.2 快速排序

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：

整體實(shí)現(xiàn)思想：

快速排序的特性總結(jié)：

1. 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
2. 時(shí)間復(fù)雜度：O(N*logN)

3. 空間復(fù)雜度：O(logN)
4. 穩(wěn)定性：不穩(wěn)定

代碼實(shí)現(xiàn)：

// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int start = left;
	int end = right;
	int pivot = start;
	int key = a[start];
	while (start < end)
	{
		//右邊找比key小的數(shù)
		while (start < end && a[end] >= key)
		{
			end--;
		}
		//找到后放到坑里去
		a[pivot] = a[end];
		//原來位置變成坑
		pivot = end;
		//左邊找比key小的數(shù)
		while (start < end && a[start] <= key)
		{
			start++;
		}
		//找到后放到坑里去
		a[pivot] = a[start];
		//原來位置變成坑
		pivot = start;

	}//以上是快排的單趟排序

	pivot = start;
	a[pivot] = key;
	//左子區(qū)間和右子區(qū)間有序，該序列就有序了，采用分治遞歸解決
	PartSort2(a, left, pivot - 1);
	PartSort2(a, pivot + 1, right);
}

//快速排序挖坑法測(cè)試
void TestPartSort2()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	PartSort2(a, 0,sizeof(a)/sizeof(int)-1);
	printf("PartSort2: ");
	ArrayPrint(a, sizeof(a) / sizeof(int));
}

int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestBubbleSort();
	TestPartSort2();

	//TestOP()
	return 0;
}

代碼運(yùn)行結(jié)果：

4.歸并排序

基本思想：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。 歸并排序核心步驟：

歸并排序的特性總結(jié)：

1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
2. 時(shí)間復(fù)雜度：O(N*logN)
3. 空間復(fù)雜度：O(N)
4. 穩(wěn)定性：穩(wěn)定

代碼實(shí)現(xiàn)：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) >> 1;
	// 假設(shè) [left, mid] [mid+1, right]
	有序，那么我們就可以歸并了
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid+1, right, tmp);

	// 歸并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	
	// 拷貝回去
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void TestMergeSort()
{
	int a[] = { 2,4,1,6,8,3,9,0,-1,9 };
	MergeSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	//TestOP();

	//TestShellSort();
	//TestHeapSort();
	//TestSelectSort();
	//TestBubbleSort();
	//TestPartSort2();
	TestMergeSort();

	return 0;
}

代碼運(yùn)行結(jié)果：

我們?cè)賮頊y(cè)試一下各個(gè)排序之間的性能：

// 測(cè)試排序的性能對(duì)比
void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		//a1[i] = i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
	}

	int begin1 = clock();
	//InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	//QuickSort(a4, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	//BubbleSort(a7, N);
	//BubbleSort(a4, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("BubbleSort:%d\n", end7 - begin7);

	printf("QuickSort:%d\n", end5 - begin5);
	/*printf("MergeSort:%d\n", end6 - begin6);*/

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);

}

int main()
{
	TestOP();

	//TestShellSort();
	//TestHeapSort();
	//TestSelectSort();
	//TestBubbleSort();
	//TestQuickSort();
	//TestMergeSort();

	return 0;
}

各個(gè)排序算法測(cè)試對(duì)一百萬(wàn)個(gè)數(shù)排序所消耗的時(shí)間為：

5.排序算法復(fù)雜度及穩(wěn)定性分析

總結(jié)：
各個(gè)排序算法有各個(gè)排序算法的不同使用場(chǎng)景，但是整體來說快排更有優(yōu)勢(shì)，所以快排更為常用。文章來源地址http://www.zghlxwxcb.cn/news/detail-415099.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之手撕排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！