面试中的排序算法（Part 1）
在面试中常见的常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、随机快排、堆排序和希尔排序这七种方式！虽然冒泡排序和选择排序基本上已经没有人使用了，但这种教科书式的思维还是值得学习的！我们接下来就来谈谈这集中排序算法的优劣！
冒泡排序
冒泡排序的思路十分的清楚，就是一个数列从左到右依次两两比对，如果左边的数大于右边的数则交换两者的位置。否则保持不变，这样的话，每一次走完一趟都可以确定一个元素的位置，并且需要n-1趟！因此外循环次数为N-1，内循环则从N-1依次递减！因为没走完一趟，确定位置的元素个数都会加一！
// 一：冒泡排序算法
void bubbleSort(vector<int> &list) {
if (list.size() < 2) {
return;
}
for (int end = list.size() - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (list[i] > list[i + 1]) {
swap(list[i], list[i + 1]);
}
}
}
}选择排序
选择排序的思路是从一个数列中选择一个值出来，然后计算剩余数的最小值，如果当前数大于剩余数的最小值，那么我们就交换这两个数的位置。注意每次我们选择一个数后，剩余数都会减一，相应的确定位置的元素数也会加一。并且判断最小值尽量不要使用库函数，特别面试的时候，这样会很low，由于进出函数的压栈出栈会影响算法的性能！
// 二：选择排序算法
void SelectSort(vector<int> &list) {
if (list.size() < 2) {
return;
}
for (int i = 0; i < list.size(); i++) {
int min = i;
for (int j = i + 1; j < list.size(); j++) {
min = list[j] < list[min] ? j : min; // 选择排序中的最小值不可以使用库函数
}
swap(list[min], list[i]);
}
}插入排序
插入排序的核心思路是，对整个数列进行遍历，将当前节点i有序的插入到一个有序列表[0, i-1]中去，为什么列表[0, i-1]是一个有序的列表呢？很简单，由于刚开始时那个列表只有一个数，必有序。如何有序插入一个节点呢？回忆一下冒泡排序，每走一趟是不是可以确定一个数的有序位置！因此，和冒泡排序类似，这个有序插入一个节点的方法也就是冒泡排序走一趟的方法！从而整个数列遍历后，他们都有序了！
// 三：插入排序算法
void InsertSort(vector<int> &list) {
if (list.size() < 2) {
return;
}
for (int i = 1; i < list.size(); i++) {
for (int j = i - 1; j >= 0 && list[j + 1] < list[j]; j--) {
swap(list[j], list[j + 1]);
}
}
}归并排序
归并排序流程图 首先我们来看合并的函数，也就是merge函数，这个函数只是做合并的算法，只能用于两个有序列表之间，我们就假设一个list分成两部分，L到mid，mid到R，这两部分均为有序数组，我们进行合并！首先准备一个辅助数组用于储存合并后的整个列表，接着这两个部分进行比较，谁小则将谁放入辅助数组，如果一个部分放完了，则将另一部分直接放入辅助数组，不再进行比较了！
怎么来使两个部分有序呢？这就用到了一个分而治之的思想，使用递归的方法对数组进行分解，直到将这两个部分分解成每个每个部分只包含一个节点，其必定有序！接着就一一合并就好啦！！递归可以很好的实现我们这个思路！
// for MergeSort
void merge(vector<int>& list, int L, int mid, int R) {
vector<int> help(R - L + 1);
int i = 0, p1 = L, p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
help[i++] = list[p1] < list[p2] ? list[p1++] : list[p2++];
}
while (p1 <= mid) {
help[i++] = list[p1++];
}
while (p2 <= R) {
help[i++] = list[p2++];
}
for (i = 0; i < help.size(); i++) {
list[L + i] = help[i];
}
}
// for MergeSort
void sortProcess(vector<int>& list, int L, int R) {
if (L == R) {
return;
}
int mid = L + (R-L) / 2; // 相比 （R+L）/ 2 可以防止数据溢出
sortProcess(list, L, mid);
sortProcess(list, mid + 1, R);
merge(list, L, mid, R);
}
// 四：归并排序算法（O(N*logN)） master公式计算递归复杂度，条件时同等规模
void MergeSort(vector<int> &list) {
if (list.size() < 2) {
return;
}
sortProcess(list, 0, list.size() - 1);
}复杂度分析
排序算法复杂度列表 由上表可得，前三种简单排序的时间复杂度平均为O(n^2)，而归并排序的时间复杂度为O(N*logN)，由于归并排序牵涉到了递归算法，对于递归算法其时间复杂度分析可以使用Master公式来说明！这个Master公式大家自行百度了解！
资源链接
完整测试文件（C++版）,文件名为：常见排序算法（重点），请关注我的个人公众号 （算法工程师之路），回复"左神算法基础CPP"即可获得，并实时更新！希望大家多多支持哦~