1.快速排序(Quick sort)
💡 时间复杂度：$N*log N$
(a)快速排序算法实现方式:
快速排序的核心思想是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。
(b)算法描述:
==快速排序是使用分治的方法将一个串分为两个子串，然后递归的方法继续划分，具体算法描述如下：==
- 定义两个指针L和R分别指向序列的两端。
- 从序列中挑选一个指针元素P，称为 “基准”（pivot）
- 一般选 P = ( L + R ) / 2
- 分区操作：重新排序序列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
==[ 比基准值小的数] 基准值P [ 比基准值大的数]== - 接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时（递归排序左右两边“[ ]”中的子序列）同样也会使用快速排序。
(c)快速排序代码模板：
//快速排序模板 void quick_sort(int q[], int l, int r) { if(l >= r) return;//如果l >= r则数列只有一个数或数列为空 int i = l - 1, j = r + 1, x = q[(l + r) >> 1];//定义双指针，i指向左端，j指向右端，x为数列的基准值 while(i < j) { //将小于x的数放在x的左边，大于x的数放在x的右边 do i++ ;while(q[i] < x); do j-- ;while(q[j] > x); if(i < j) swap(q[i], q[j]); } quick_sort(q, l, j);//递归左边 quick_sort(q, j + 1, r);//递归右边 }
2.归并排序(Merge sort)
💡 时间复杂度：$N* log N$
(a)快速排序算法实现方式:
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的
(b)算法描述:
- 定义三个指针 L， R， mid， 分别指向序列的左右两端和中间。
- 首先找到序列的中间值mid =（ L + R） / 2，将序列分为两个子序列。
- 对左序列（ L — mid）和右序列 （ mid + 1— R ）递归将序列划分成若干个子序列。
- 然后从下往上逐层合并，首先对第一层序列的数字进行排序合并，然后再依次排序合并各层。
(c)归并排序代码模板：
void merge_sort(int q[], int l, int r) { if (l >= r) return; //将一整个数列拆分成若干个数 int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); //合并 int k = 0, i = l, j = mid + 1;//*** while (i <= mid && j <= r)//比较两个数，将较小的数存入tmp[]数组中 if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; //将比较厚剩余的数加到数组的后面 while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; //将tmp[]数组中的值搬回q[]数组中 for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
