排序算法
快排
参考博客：链接
1、问题分析
快排的中心思想：分而治纸。通过选取基准值将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准值小，另一部分的所有数据都比基准值大，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此使所有数据变成有序序列。
2、算法设计
1、分解
先从数列中取出一个元素作为基准元素。一基准元素为标准，将问题分解为两个子序列，使小于或者等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
2、治理
对两个子序列进行快速排序（递归快速排序）。
3、合并
将排好的两个子序列合并在一起，得到原问题的解。
其中基准元素的选取可以有以下形式：
①：取第一个元素。(通常选取第一个元素)；
②：取最后一个元素；
③：取中间位置的元素；
④：取第一个、最后一个、中间位置元素三者之中位数；
⑤：取第一个和最后一个之间位置的随机数 k (low<=k<=hight)。
3、算法细节
排序的步骤如下：
假设当前的待排序的序列为 R[low,hight] ， 其中 low<=hight。同时选取首元素为基准元素。
步骤一：选取首元素的第一个元素作为基准元素 pivot=R[low] ，i=low ，j=hight。
步骤二：从右向左扫描，找到小于等于 pivot 的数，如果找到，R[i] 和 R[j] 交换 ，i++。
步骤三：从左向右扫描，找到大于 pivot 的数，如果找到，R[i] 和 R[j] 交换，j--。
步骤四：重复 步骤二~步骤三，直到 j 与 i 的指针重合 返回位置 mid=i ，该位置的数正好是 pivot 元素。
至此完成一次排序，此时以 mid 为界线，将数据分割为两个子序列，左侧子序列都比 pivot 数小，右侧子序列都比 pivot 数大，然后再分别对这两个子序列进行快速排序，递归合并后即可得到整个序列的排序
下面以序列（30，24，5，58，18，36，12，42，39）为例，进行图解。
（1）初始化。i=low ，j=hight，pivot=R[low]=30。如下图所示：
（2）向左走，从数组的右边位置向左找，一直找到小于等于 pivot 的数，找到R[j]=12，R[i]与R[j]交换，i++。如下图所示：
（3）向右走，从数组的左边位置向右找，一直找到比 pivot 大的数，找到 R[i]=58 ,R[i] 与 R[j] 交换 ，j--。
（4）向左走，从数组的右边位置向左找，一直找到小于等于 pivot 的数，找到R[j]=18，R[i]与R[j]交换，i++。如下图所示：
（5）向右走，从数组的左边位置向右找，一直找到比 pivot 大的数，这是 i=j，第一轮排序结束，返回 i 的位置，mid=i 。至此完成一次排序，具体代码如下所示：
int part(int* r, int low, int hight) //划分函数
{
int i = low, j = hight, pivot = r[low]; //基准元素
while (i < j)
{
while (i<j && r[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
{
j--;
}
if (i < j)
{
swap(r[i++], r[j]); //r[i]和r[j]交换后 i 向右移动一位
}
while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
{
i++;
}
if (i < j)
{
swap(r[i], r[j--]); //r[i]和r[j]交换后 i 向左移动一位
}
}
return i; //返回最终划分完成后基准元素所在的位置，为之后的分解做准备
}
（6）然后在分别对这两个序列（12，24，5，18）和（36，58，42，39）进行快速排序（递归）。其代码如下所示：
void Quicksort(int* r, int low, int hight)
{
int mid;
if (low < hight)
{
mid = part(r, low, hight); // 返回基准元素位置
Quicksort(r, low, mid - 1); // 左区间递归快速排序
Quicksort(r, mid+1, hight); // 右区间递归快速排序
}
}
4、算法复杂度
时间复杂度：o(nlogn)。分为logn层，每层需要遍历n个元素。共需o(nlogn)。
空间复杂度：o(logn)。递归栈的深度为o(logn)。
归并排序
参考博客：链接
归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
1、基本思想
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果。
2、实现逻辑
2.1 迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤③直到某一指针到达序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
2.2 递归法
① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素；
② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕。
3、具体实现
以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：
代码实现：
迭代法：
void merge_sort(T arr[], int len) {
T* a = arr;
T* b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T* temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}
递归法：
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) {
T *reg = new T[len]；
merge_sort_recursive(arr, reg, 0, len - 1);
}
4、算法复杂度
时间复杂度：o(nlogn)。分为logn层，每层需要遍历n个元素。共需o(nlogn)。
空间复杂度：o(n)。需要额外的空间存储元素。
冒泡排序
参考博客：链接
1.、基本思想
冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
2. 实现逻辑
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
通过两层循环控制：
- 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
- 第二个循环（内循环），负责两两比较交换。
3、具体实现
void bubble_sort(int arr[], int len)
{
int i, j;
for (i = 0; i < len; i++)
for (j = 1; j < len - i; j++)
if (arr[j - 1] > arr[j])
swap(arr[j - 1], arr[j]);
}
4、算法复杂度
时间复杂度：o(n2)。需要双重循环。
空间复杂度：o(1)。不需要额外的空间存储元素。
5、优化
优化方法一：
在某次遍历中如果没有数据交换，说明整个数组已经有序，不需要要在排列了。如果用基础的冒泡排序方法，仍然还要比较O(N^2)次，但其实并无交换操作。
改进思路：
通过设置标志位来记录此次遍历有无数据交换，进而可以判断是否要继续循环，设置一个flag标记，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。
改进代码：
void bubble_sort(int arr[], int len)
{
for (int i = 0; i < len-1; i++){ //比较n-1次
bool exchange = true; //冒泡的改进，若在一趟中没有发生逆序，则该序列已有序
for (int j = len-1; j >i; j--){ //每次从后边冒出一个最小值
if (arr[j] < arr[j - 1]){ //发生逆序，则交换
swap(arr[j], arr[j - 1]);
exchange = false;
}
}
if (exchange){
return;
}
}
}
优化方法二：
改进思路：
记录某次遍历时最后发生数据交换的位置pos，这个位置之后的数据显然已经有序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
改进代码：
void bubble_sort(int arr[], int len)
{
int j, k;
int flag;
flag = len;
while (flag > 0)
{
k = flag;
flag = 0;
for (j = 1; j < k; j++)
if (arr[j - 1] > arr[j])
{
swap(arr[j - 1], arr[j]);
flag = j;
}
}
}
一些常见的算法知识
查看5道真题和解析
快手公司福利 352人发布
