综合算法等

算法等"/>

综合算法等

Algorithm WebSite-知乎

排序 - Sort

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

时间复杂度

冒泡排序法

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间

/*** 冒泡排序法* asc 用来判断排序顺序* 时间复杂度: O(n^2)* 空间复杂度: S(1)*/
void BubbleSort(vector<int>& vec, int asc = 1) {int size = vec.size(), temp;    //temp用做中间变量进行交换数值//外循环控制循环次数，对 n 个数来说，一共要循环 n - 1 次， 因为每次都会确定一个当前最大(小)的数for (int i = size - 1; i > 0; i--) {//从第1个数开始相邻数比较，将较大(小)的数移动到后面for (int j = 0; j < i; j++) {if (asc ? vec[j] > vec[j + 1] : vec[j] < vec[j + 1]) {swap(vec[j], vec[j + 1]);}}}
}

选择排序

/*** 选择排序法* asc 是否是顺序排序* 时间复杂度 O(n^2)* 空间复杂度 O(1)* 不断的从头到尾进行查找，每次查找中，将比结尾大的放到结尾，比开头小的放到开头*/ 
void SelectSort(vector<int>& vec, int asc = 1) {int left = -1, right = vec.size();while (++left <= --right) {for (int i = left; i < right; i++) {if (asc ? vec[i] > vec[right] : vec[i] < vec[right]) swap(vec[i], vec[right]);  //找到当前最大的数并将其置换到最后if (asc ? vec[i] < vec[left] : vec[i] > vec[left]) swap(vec[i], vec[left]);     //找到当前最小的数并将其置换到当前位置的最前}}
}

鸡尾酒排序

鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。

/*** 鸡尾酒排序法* asc 是否是顺序排序* 时间复杂度 O(n^2)* 空间复杂度 O(1)* 不断进行查找，先前往后找到最大的数将它放到最后面，然后再从后往前将最小的数放到最前面*/
void CocktailSort(vector<int>& vec, int asc = 1) {int size = vec.size(), left = 0, right = size - 1, times = 0, max, min;while (times < size / 2) {      //每次为一个来回，即从left到right，再从right - 1 到 left + 1times++;                    //统计次数max = right, min = left;    //记录最大/小值for (int i = left; i <= right; i++) {   //第一趟，从left到right找最大值if (asc ? vec[i] > vec[max] : vec[i] < vec[max]) max = i;}swap(vec[max], vec[right--]);   //交换最大值和最右面for (int i = right; i >= left; i--) {   //第二趟，从right - 1 到 left + 1 找最小值if (asc ? vec[i] < vec[min] : vec[i] > vec[min]) min = i;}swap(vec[min], vec[left++]);    //交换最小值和最右面}
}
/*** 鸡尾酒排序法2* asc 是否是顺序排序* 时间复杂度 O(n^2)* 空间复杂度 O(1)* 不断进行查找，从前往后不断交换不是顺序的数，将最大的数放到最后，再从后往前不断交换，将较小的数放到最前*/
void CocktailSort2(vector<int>& vec, int asc = 1) {int size = vec.size(), left = 0, right = size - 1, times = 0, flag = 1;while (times < size / 2) {      //每次为一个来回，即从left到right，再从right - 1 到 left + 1times++;                    //统计次数for (int i = left; i < right; i++) {   //第一趟，从left到right找最大值if (asc ? vec[i] > vec[i + 1] : vec[i] < vec[i + 1]) {swap(vec[i], vec[i + 1]);flag = 0;}}right--;for (int i = right; i > left; i--) {   //第二趟，从right - 1 到 left + 1 找最小值if (asc ? vec[i] < vec[i - 1] : vec[i] > vec[i - 1]) {swap(vec[i], vec[i - 1]);flag = 0;}}left++;}
}
/*** 鸡尾酒排序法2 PLUS* asc 是否是顺序排序* 特点：冒泡排序进阶，适用于大部分都是有序的情况* 时间复杂度 O(n^2)* 空间复杂度 O(1)* 不断进行查找，先前往后将最大的数放到后面，然后再从后往前将较小的数放到最前面* 如果当前查找没有进行交换，则说明当前查找的范围[left, right]内是有序的，所以不用继续排序下去*/
void CocktailSortPlus(vector<int>& vec, int asc = 1) {int size = vec.size(), left = 0, right = size - 1, times = 0, flag = 1;while (times < size / 2) {      //每次为一个来回，即从left到right，再从right - 1 到 left + 1times++;                    //统计次数flag = 1;for (int i = left; i < right; i++) {   //第一趟，从left到right找最大值if (asc ? vec[i] > vec[i + 1] : vec[i] < vec[i + 1]){swap(vec[i], vec[i + 1]);flag = 0;}}right--;if (flag) break;flag = 1;for (int i = right; i > left; i--) {   //第二趟，从right - 1 到 left + 1 找最小值if (asc ? vec[i] < vec[i - 1] : vec[i] > vec[i - 1]) {swap(vec[i], vec[i - 1]);flag = 0;}}if (flag) break;left++;}
}

插入排序法

所谓插入排序法，就是检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。插入排序法主要的回圈有两个变数：i和j，每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。

void InsertSort(vector<int>& vec) {int size = vec.size();//外层循环控制当前查找交换的位置，内层循环进行控制判断和交换//lastChangeIndex记录当前内循环最终进行交换的位置，如果当前循环并没有进行交换，则使用lastChangeIndex增一进行增加外层循环for (int i = 0, lastChangeIndex = 0; i < size - 1; i = ++lastChangeIndex) {for (int j = size - 1; j > i; j--) {if (vec[j] < vec[j - 1]) {swap(vec[j], vec[j