为了便于测试，先写一个生成随机数组的方法。
1 pair<int*,int> GenerateRandomArray(int maxSize, int maxValue, int minValue)
2 {
3 //随机数组长度
4 const int len = rand()%maxSize+1;
5 int* arr = new int[len];
6
7 for (int i = 0; i < len; i++)
8 {
9 arr[i] = rand()%(maxValue-minValue+1)+minValue;
10 }
11 return make_pair(arr,len);
12 }
返回值（数组，数组长度）
//////////冒泡排序//////////
第一轮：从第0位开始，依次比较 i 和 i+1 位，把大的换到 i+1 位，一直比较到 i+1 = N
第二轮：从第0位开始，依次比较 i 和 i+1 位，把大的换到 i+1 位，一直比较到 i+1 = N-1
......
第N-1轮：从第0位开始，比较 0 和 1 位，大的换到第1位，比较结束。
1 void BubbleSort(int arr[], int N)
2 {
3 for (int i = N-1; i > 0; i--) //第一轮比较了N-1次，第二轮N-2次，...，一直到1次
4 {
5 for (int j = 0; j < i; j++) //注意最大值是j+1=i，所以要比较到j<i
6 {
7 if (arr[j] > arr[j + 1])
8 swap(arr[j], arr[j + 1]);
9 }
10 }
11 }
//////////选择排序//////////
第一轮：从第0位开始，一直到最后一位，找到最小的数，放在第0位
第二轮：从第1位开始，一直到最后一位，找到最小的数，放在第1位
......
第N-1轮：从第N-2位开始，比较第N-2和第N-1位，也就是最后两位，找到最小的放在N-2位，排序结束。
1 void SelectionSort(int arr[], int N)
2 {
3 for (int i = 0; i < N - 1 ; i++) //只剩最后一位时不用比较，所以一共比较了N-1次
4 {
5 int minIdx = i;
6 for (int j = i + 1; j < N; j++) //已经把第i位设为当前最小值，直接从i+1开始比到最后一位
7 {
8 if (arr[j] < arr[minIdx])
9 minIdx = j;
10 }
11 swap(arr[minIdx], arr[i]);
12 }
13 }
//////////插入排序//////////
第一轮：从第1位往前到第0位，逐次比较，把更小的换到左边，共比较1次。
第二轮：从第2位往前到第0位，逐次比较，把更小的换到左边，共比较2次。
......
第N-1轮：从第N-1位往前到第0位，逐次比较，把更小的换到左边，共比较N次。
===>外循环：i：1~N-1；
===>内循环：j：i~0；
最简单的可以类比扑克牌抽牌理牌，每抽起来一张牌都从右往左一一比较，然后插入到合适位置。
1 void InsertionSort(int arr[], int N)
2 {
3 for (int i = 1; i < N; i++)
4 {
5 for (int j = i - 1; j >= 0; j--)
6 {
7 if (arr[j] > arr[j + 1])
8 swap(arr[j], arr[j + 1]);
9 }
10 }
11 }
时间复杂度：冒泡、选择、插入的时间复杂度都为O(N2)
下面介绍两种时间复杂度为O(NlogN)的算法：归并排序、快速排序（最坏情况是O(N2)）
在此之前，先介绍递归
//////////递归//////////
Q. 在[L,R]范围内找最大值
1 int MaxValue(int arr[], int L, int R)
2 {
3 //[L,R] 只有1个数时，直接返回这个数
4 if (L == R)
5 return arr[L];
6 int mid = L + ((R - L) >> 1);
7 int leftMax = MaxValue(arr, L, mid);
8 int rightMax = MaxValue(arr, mid + 1, R);
9 return max(leftMax, rightMax);
10 }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
小技巧：如何选取中间节点？
mid = ( L + R ) / 2 ??? × 当数字特别大时，L+R可能会溢出
mid = L + ( R - L ) / 2 √ 避免溢出
还可以效率更高：mid = L + (R - L) >> 1
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Tips. 不建议用递归，容易栈溢出
∵ 每当程序执行一个函数调用，就会增加一层栈帧，当函数返回才会减一层栈帧。递归调用达到结束点才会退栈清栈。
∴ 可以用动态规划代替递归 或 修改栈的大小
//////////归并排序//////////
1 void Merge(int arr[], int low, int mid, int high)
2 {
3 int i = low, j = mid + 1;
4 vector<int> tmpArr;
5 while (i <= mid && j <= high)
6 {
7 if (arr[i] < arr[j])
8 tmpArr.push_back(arr[i++]);
9 else
10 tmpArr.push_back(arr[j++]);
11 }
12 while (i <= mid)
13 tmpArr.push_back(arr[i++]);
14 while (j <= high)
15 tmpArr.push_back(arr[j++]);
16 for (int n = 0; n <= high-low; n++)
17 arr[low+n] = tmpArr[n];
18 }
19
20 //归并排序
21 void MergeSort(int arr[],int L, int R)
22 {
23 if (L >= R) return;
24 int mid = L + ((R - L) >> 1);
25 MergeSort(arr,L, mid); //左边排好序
26 MergeSort(arr,mid + 1, R); //右边排好序
27 Merge(arr, L, mid, R); //整体有序
28 }
Q. 荷兰国旗问题：给定一个数组arr，和一个数num，把小于num的数放在数组左边，等于num的数放在中间，大于num的数放右边，要求空间复杂度O(1)，时间复杂度O(N)
思路：最左和最右两个指针i,j，指向当前位置的cur，从左往右依次遍历，如果比num大就跟j交换位置，j--；如果比num小就跟i交换位置，i++，cur++；如果等于num不用交换直接cur++。
1 void QuickSort1(int arr[], int len, int num)
2 {
3 int i = 0; //小于区域指针
4 int j = len-1; //大于区域指针
5 int cur = 0; //当前指针
6
7 while (cur < j)
8 {
9 if (arr[cur] < num)
10 {
11 swap(arr[cur], arr[i]);
12 i++;
13 cur++;
14 }
15 else if (arr[cur] == num)
16 cur++;
17 else
18 {
19 swap(arr[cur], arr[j]);
20 j--;
21 }
22 }
23 }
//////////快速排序//////////
1 void QuickSort(int arr[], int L, int R)
2 {
3 int i = L;
4 int j = R;
5 int temp = arr[i]; //基准值
6 if (i >= j) return;
7 while (i < j)
8 {
9 while (i < j && arr[j] >= temp) j--; //从右往左找到比基准值小的值
10 if (i < j)
11 arr[i++] = arr[j]; //将找到的比基准值小的数换到左边
12 while (i < j && arr[i] <= temp) i++; //从左往右找到比基准值大的数
13 if (i < j)
14 arr[j--] = arr[i]; //将找到的比基准值大的数换到右边
15 arr[i] = temp; //最后把基准数放在i位置
16 }
17 QuickSort(arr, L, i - 1);
18 QuickSort(arr, i + 1, R);
19 }
标签：arr,cur,int,mid,C++,++,算法,num,数据结构 From： https://www.cnblogs.com/tomatokely/p/16935655.html