算法从来不是死记硬背，而是要知道它背后需要解决什么样的问题，为什么这样设计，

选择排序

其实就是挨个查找最小元素的索引，然后交换之。先看图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename  T>
void selectionSort(T arr[], int n) {
	for (int i = 0; i < n; i++)
	{
		//寻找在[i,n)之间的最小值的索引
		int minIndex = i; 
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] < arr[minIndex])
			{
				minIndex = j;
			}
		}
		swap(arr[i], arr[minIndex]);
	}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T >
	void insertSort(T arr[], int n) {
		for (int i = 1; i < n; i++)
		{
			T e = arr[i];
			int j;
			for (j = i; j > 0 && arr[j - 1] > e; j--)
			{
				arr[j] = arr[j - 1];
			}
			arr[j] = e;
		}
		return;
	}

归并排序

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//将arr[l...mid]和arr[mid+1...r]进行归并
	template<typename  T>
	void __merge(T arr[], int l, int mid, int r) {
		int size = r - l + 1;
		T aux[size];
		for (int i = l; i <= r; i++)
			aux[i - l] = arr[i];
		int i = l, j = mid + 1;
		for (int k = l; k <= r; k++)
		{
			if (i > mid)
			{
				aux[k] = aux[j - l];
				j++;
			}
			else if (j > r) {
				aux[k] = aux[i - l];
				i++;
			}
			else if (aux[i - l] < aux[j - l]) {
				aux[k] = aux[i - l];
				i++;
			}
			else {
				aux[k] = aux[j - l];
				j++;
			}
		}
		return;
	}

	//递归使用归并排序 对arr[l....r]的范围进行排序
	template<typename T >
	void __mergeSort(T arr[], int l, int r) {
		/*
		if (l >= r)
		{
			return;
		}
		*/
		//第二个优化  如果数据量小，使用插入排序
		if (r - l <= 15)
		{
			InsertSort::insertionSort(arr, l, r);
			return;
		}
		int mid = (l + r) / 2;
		__mergeSort(arr, l, mid);
		__mergeSort(arr, mid + 1, r);
		if (arr[mid] > arr[mid + 1])    //第一个优化，如果这个递归出来的数组本身就已经是有序的了，就不需要进行归并了
			__merge(arr, l, mid, r);
	}

	template<typename T >
	void mergeSort(T arr[], int n) {

		__mergeSort(arr, 0, n - 1);

	}

快速排序

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
28
29
30
31
32
//对arr[l...r]部分进行partition操作
	//返回p，使得arr[l...p-1] < arr[p]  arr[p+1...r] > arr[p]
	template<typename T>
	int partition(T arr[],int l,int r) {
		T v = arr[l];
		//arr[l+1...j]<v   arr[j+1...i) > v
		int j = l;
		for (int i = l+1; i <= r; i++)
		{
			if (arr[i] < v) {
				swap(arr[i], arr[j+1]);
				j++;
			}
		}
		swap(arr[l],arr[j]);
		return j;
	}

	//对arr[l...r]进行快速排序
	template<typename T>
	void __quickSort(T arr[],int l ,int r) {
		if (l >= r)
			return;
		int p = partition(arr,l,r);
		__quickSort(arr, l, p-1);
		__quickSort(arr, p + 1, r);
	}

	template<typename T>
	void quickSort(T arr[], int n) {
		__quickSort(arr,0,n-1);
	}