对数据结构中非常重要的十大内部排序算法以及七大查找算法做一个总结
排序算法可按照如下进行分类：

内部排序：指的是只用到了电脑内存而不使用外存的排序方式。

images

比较排序

比较排序，顾名思义，即需要通过比较两个元素的大小关系来确定先后顺序。
而在比较排序中，又可以分为交换、插入、选择和归并四类。

交换：根据比较结果交换两个元素。
插入：将当前遍历到的元素插入到之前已经排好序的序列中。
选择：不断选出当前剩余序列中最大(或最小)的元素出来。

交换

1. 冒泡排序（Bubble Sort）

冒泡排序是三大基础排序中的一种，比较简单，不再赘述，直接上代码。

1
2
3
4
5
6
7
void BubbleSort(int* arr, int n) {
	for(int i=0; i<n; ++i)
		for(int j=0; j<n-i-1; ++j) {
		if(arr[j] > arr[j+1])
			swap(arr[j], arr[j+1]);
	}
}

2. 快速排序（Quick Sort）

快速排序是对冒泡排序的一种改进，使用了分治思想。

思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int Partition(int *arr, int left, int right) {
	int pivot = arr[left];
	while(left < right) {
		while(left < right && arr[right] >= pivot)
			--right;
		arr[left] = arr[right];//将小于pivot的放在左侧
		while(left < right && arr[left] <= pivot)
			++left;
		arr[right] = arr[left];//将大于pivot的放在右侧
	}
	arr[left] = pivot;
	return left;//返回pivot的最终位置
}

void QuickSort(int *arr, int left, int right) {
	if(left < right) {
		int pivot = Partition(arr, left, right);
		QuickSort(arr, left, pivot-1);
		QuickSort(arr, pivot+1, right);
	}
}

插入

3. 插入排序（Insert Sort）

插入排序也是三大基础排序的一种，直接上代码。

1
2
3
4
5
6
7
8
9
void InsertSort(int *arr, int n) {
	for(int i=1; i<n; ++i) {
		int temp = arr[i];//当前遍历到的准备插入的元素
		int j = i-1;
		for(; j>=0 && arr[j] > temp; --j)
			arr[j+1] = arr[j];//将所有大于要插入的往后移
		arr[j+1] = temp;
	}
}

注意，因为时间复杂度的关系，三大基础排序算法中，选择和冒泡排序很少使用，因为无论何时，他们的时间复杂度都为$ O(N^2) $。但是插入排序在数组本就有序的时候，时间复杂度可以接近$ O(N) $。

4. 希尔排序（Shell Sort）

希尔排序是插入排序的一种，又称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

简单理解就是，普通插入排序实际上可以看作希尔排序的gap为1时的情况。希尔排序就是首先选择一个gap，将序列分成很多子序列并进行插入排序。减小gap并重复插入排序，直到间距降为1完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Shell(int *arr, int begin, int gap, int n) {
	for(int i=begin; i<n; i+=gap) {
		int temp = arr[i];
		int j = i-gap;
		for(;arr[j] > temp && j>=begin; j-=gap)
			arr[j+gap] = arr[j];
		arr[j+gap] = temp;
	}
}

void ShellSort(int *arr, int n) {
	int gap = n/2;
	while(gap) {
		int begin = gap-1;
		while(begin >= 0)
			Shell(arr, begin--, gap, n);
		gap /= 2;
	}
}

选择

5. 选择排序（Select Sort）

选择排序是三大基础排序的最后一种，直接上代码。

1
2
3
4
5
6
7
8
9
10
11
12
void SelectSort(int *arr, int n) {
	for(int i=0; i<n-1; ++i) {
		int min = arr[i];
		int index = i;
		for(int j=i+1; j<n; ++j)
			if(arr[j] < min) {
				min = arr[j];
				index = j;
			}
		swap(arr[i], arr[index]);
	}
}

6. 堆排序（Heap Sort）

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

堆排序的基本思想：
1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

为了便于理解，我们假设有一个待排序数组[4,5,1,7,8,6,3,2]，然后使用大顶堆来实现排序。

首先，我们将数组序列填入到一个二叉树中，如图：

images

然后，我们需要找出这个二叉树的最后一个非叶子节点（从这个节点开始往前面遍历，使得每个节点都能满足大顶堆的要求，即节点的值大于等于左右子节点的值）。

对于一个按这样的方式填入的二叉树，可以称之为完全二叉树，而要找到这样的树的最后一个非叶子节点，无非有两种情况，很容易看出来这两种情况是等价的。

images

无论是否存在最后这个节点，这棵树的最后一个非叶子节点都是节点7。所以，直接讨论存在这个节点的情况。根据二叉树的性质，当二叉树仅存在有两个子节点的非叶子节点时，我们很容易得到最后一层的节点总数 = 上面的所有节点总数 + 1，从而可以得到最后一个非叶子节点的索引应该为节点总数/2-1 = 3，对应就是节点7(根节点索引为0)。

images

接着，节点7大于它左右子节点的值，所以我们继续往上遍历，节点1不满足条件，所以我们需要交换。交换后的树如图：

images

按照这样的规则一直最后得到如下大顶堆：

images

最后，我们使用大顶堆，找出了这个序列中最大的数(即堆顶元素)，那么我们只需要将这个堆顶元素和尾部元素交换位置，然后将序列的大小减一，再重新构造大顶堆，找出新的最大的元素，重复这样的操作。

images

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void maxHeapIfy(int *arr, int cur, int n) {
	int left = cur*2+1;//左子节点
	int right = cur*2+2;//右子节点
	int max = cur;
	if(left < n && arr[max] < arr[left]) max = left;
	if(right < n && arr[max] < arr[right]) max = right;
	if(max != cur) {
		swap(arr[cur], arr[max]);
		maxHeapIfy(arr, max, n);
	}
}

void BuildMaxHeap(int *arr, int n) {//构造大顶堆
	for(int i=n/2-1; i>=0; --i)
		maxHeapIfy(arr, i, n);
}

void HeapSort(int *arr, int n) {
	BuildMaxHeap(arr, n);//构造大顶堆
	for(int i=n-1; i>0; --i) {
		swap(arr[0], arr[i]);
		maxHeapIfy(arr, 0, i);//注意要减小序列的大小
	}
}

归并（Merge Sort）

7. 归并排序

归并排序和快速排序有着类似的思想，使用了分治思想。
分，即将大问题分成小问题再处理；治，即将分后处理解决掉的小问题合在一起解决大问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Merge(int *arr, int left, int middle, int right) {
	int length = right-left+1;
	int *temp = new int[length];
	int l = left, r = middle+1, i=0;
	while(l <= middle && r <= right)//当左右两个数组都还有数时
		temp[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
	while(l <= middle)
		temp[i++] = arr[l++];
	while(r <= right)
		temp[i++] = arr[r++];
	for(int j=0; j<length; ++j)//拷贝合并后的数组
		arr[j+left] = temp[j];
	delete [] temp;//删除临时数组
}

void MergeSort(int *arr, int left, int right) {
	if(left == right) return;//当子数组长度为1时
	int middle = (left+right)/2;
	MergeSort(arr, left, middle);
	MergeSort(arr, middle+1, right);
	Merge(arr, left, middle, right);
}

非比较排序

最后还有三种不需要通过比较的排序算法，这三种排序算法在使用的时候往往有一些特殊要求。

8. 计数排序（Counting Sort）

计数排序即统计待排序数列中每个数字出现的次数。填入数据结构的过程其实就是排序的过程。最后再按照统计结果覆盖原序列就行了。

对于那些待排序列中的数值差距特别大或者无法预先知道待排学列中数值的范围时，这种排序算法是无法使用的。所以相比较来说，这种排序方式比较适合，数据重复较多，数值范围已知，数值变化较小的待排序列。

1
2
3
4
5
6
7
8
9
10
11
12
void CountingSort(int *arr, int n, int range) {
	vector<int> vec;
	vec.resize(range+1, 0);
	for(int i=0; i<n; ++i)
		++vec[arr[i]];
	int index = 0;
	for(int i=0; i<range+1; ++i) {
		while(vec[i]--){
			arr[index++] = i;
		}
	}
}

9. 桶排序（Bucket Sort）

桶排序是计数排序的改进，使用映射函数，将待排序集合中处于同一个值域的元素存入同一个桶中(弱化了计数排序对空间的浪费)，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

计数排序可以看作让每个值都单独成为一个桶(当然，因为每个桶都只有一个值，计数排序的桶里存储的是出现次数)；而每次快速排序可以看作是通过选定的pivot将整个序列分成两个桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void insert(list<int>& bucket, int val) {//将数插入桶中正确的位置
	auto i = bucket.begin();
	while(i != bucket.end() && (*i) <= val) ++i;
	bucket.insert(i, val);
}

void BucketSort(int *arr, int n) {
	int min = arr[0], max = arr[0];//找出待排序序列的数值范围
	for(int i=0; i<n; ++i){
		if(arr[i] < min) min = arr[i];
		if(arr[i] > max) max = arr[i];
	}
	int capacity = 10;//桶的容量
	int bucketNum = (max-min)/capacity+1;//桶的个数
	vector<list<int>> buckets(bucketNum);
	for(int i=0; i<n; ++i) {
		int val = arr[i];
		insert(buckets[(temp-min)/capacity], val);
	}
	int index = 0;
	for(int i=0; i<bucketNum; ++i) {//将桶中的数倒回原数组
		if(buckets[i].size()) {//桶中有数
			for(auto& val:buckets[i])
				arr[index++] = val;
		}
	}
}

10. 基数排序（Radix Sort）

基数排序,将所有序列中的数，统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始, 依次进行稳定排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序要求待排序列的数都是正整数。

基数排序原理很简单，对于一个正整数来说，决定其他大小的优先级总是从高位向低位递减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void CountingSort(int *arr, int n, int exp) {
	vector<int> pos;
	int *temp = new int[n];
	pos.resize(10, 0);//基数排序的桶有0-9共10个
	for(int i=0; i<n; ++i)
		++pos[(arr[i]/exp)%10];
	for(int i=1; i<10; ++i)//找到元素应该存放的位置
		pos[i] += pos[i-1];
	for(int i=n-1; i>=0; --i)
		temp[--pos[(arr[i]/exp)%10]] = arr[i];
	for(int i=0; i<n; ++i)
		arr[i] = temp[i];
	delete [] temp;
}

void RadixSort(int *arr, int n) {
	int max = arr[0];
	for(int i=1; i<n; ++i){
		if(max < arr[i]) max = arr[i];
	}
	for(int exp=1; max/exp>0 ; exp*=10)
		CountingSort(arr, n, exp);
}

算法性能分析

images