排序
各个排序复杂度：
插入排序：算法思想
算法思想：每次将⼀个待排序的记录按其关键字⼤⼩插⼊到前⾯已排好序的⼦序列中， 直到全部记录插⼊完成。
步骤：引用来自菜鸟教程：https://www.runoob.com/data-structures/insertion-sort.html
-
第一轮：从第二位置的 6 开始比较，比前面 7 小，交换位置。
-
第二轮：第三位置的 9 比前一位置的 7 大，无需交换位置。
-
第三轮：第四位置的 3 比前一位置的 9 小交换位置，依次往前比较。
-
第四轮：第五位置的 1 比前一位置的 9 小，交换位置，再依次往前比较。
代码：
#include<iostream>
using namespace std;
#include<vector>
//插入排序
//插入排序是从第二个元素进行排序的，每次排序时。当前元素都会和前面的元素进行对比。
void insertSort(vector<int>& v) {
int temp;//临时存放当前元素
int j;
for (int i = 1; i < v.size(); i++) {
temp = v[i];//存放当前元素
//将当前元素和之前的元素进行对比
//即检查前面所有已经排好序的元素是否大于当前元素值
for (j = i - 1; j >= 0; j--) {
if (v[j] > temp)
v[j + 1] = v[j];//将大于temp的元素后移
else
break;
}
//可将上面的循环体改写为
//for (j = i - 1; j >= 0 && a[j - 1] > temp; j--) v[j + 1] = v[j];
v[j + 1] = temp;//将temp放入对应位置。注意：这里是j+1，因为再前面的循环条件中，j = j-1，不满足条件才会跳出循环
}
}
int main() {
vector<int> v = { 2,5,9,5,12,43,76,1,0,89};
insertSort(v);
for (vector<int> ::iterator it = v.begin(); it != v.end(); it++) {
cout << (*it) << " ";
}
cout << endl;
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
希尔排序
算法思想：希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
见菜鸟教程：https://www.runoob.com/data-structures/shell-sort.html
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
算法思想：它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
图示过程：
- 初始增量第一趟 d = length/2 = 4
- 第二趟，增量缩小为d = d/2 = 2
- 第三趟，增量缩小为 1,得到最终排序结果.
代码
#include<iostream>
using namespace std;
#include<vector>
void shellsort(vector<int>& v) {
int n = v.size();
for (int gap = n >> 1; gap > 0; gap >>= 1) {
for (int i = gap; i < n; i++) {
int temp = v[i];
int j = i - gap;
while (j >= 0 && v[j] > temp) {
v[j + gap] = v[j];
j -= gap;
}
v[j + gap] = temp;
}
}
}
int main() {
vector<int> v = { 90,8,0,23,1,5,8,6,34,0,1,1,4 };
shellsort(v);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
冒泡排序算法思想：
基于“交换”的排序：根据序列中两个元素关键字的⽐较结果来对换这两个记录在序列中的位置。其目的是找到最大（最小）值，倒数第二大值，倒数第三大值....
算法为：
算法简介: 1.比较相邻的元素，前一个比后一个大（或者前一个比后一个小）调换位置
2.每一对相邻的元素进行重复的工作，从开始对一直到结尾对，这步完成后，结尾为做大或最小的数.
3.针对除了最后一个元素重复进行上面的步骤
4.重复1-3步骤直到完成排序
代码
void bubbleSort(vector<int>& v) {
for (int i = 0; i < v.size() - 1; i++) {
//每次从第1个元素开支找，一次找到最大值，倒数第二大值...
for (int j = 0; j < v.size()-1-i; j++) {
if (v[j] > v[j+1]) {//如果前面的大于后面的，将较大的值向后移动，直到选出最大的那个值
int temp = v[j];
v[j] = v[j + 1];
v[j + 1] = temp;
}
}
}
}
快速排序
随机化快速排序基本思想：算法思想：
1.通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
2.然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码
//用第一个元素将待排序的子数组序列划分为左右连个部分
//并返回第一个元素最终放置的位置。左边部分元素比该元素小，
//右边的元素比该元素大。
int partition(vector<int>& v, int low, int high) {
//选取子数组的第一个元素作为基准元素
int pivot = v[low];
//用low和right所搜基准的最终文职
while (low < high)
{
while (low < high && v[high] >= pivot)
high--;//找到右边小于基准元素的值，并将其放置再low的左边
v[low] = v[high];//并将其放置在下标为low处
while (low < high && v[low] <= pivot)
low++;//找到左边大于基准元素的值
v[high] = v[low];
}
//当low == high时，其左边的值都比pivot小，右边的值都比pivot大
v[low] = pivot;
return low;//必须返回该值，告诉该元素放置的位置
}
//快速排序
void quickSort(vector<int>& v,int low,int high) {
if (low < high) {
//先对整个数组进行划分。有点类似对二叉树进行遍历。
int position = partition(v, low, high);
//再进行递归处理，分别对左边和右边的部分进行排序
quickSort(v, low, position-1);
quickSort(v, position + 1, high);
}
}
简单选择排序
选择排序：每一趙在待排序元素中选取关键字最小（或最大）的元素加入有序子序列.
简单选择排序是基于选择排序的,每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列.有点类似冒泡排序.
算法:1.从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
- 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
代码
void selectSort(vector<int>& v) {
for (int i = 0; i < v.size(); i++) {
int min = i;//记录最小元素的位置
for (int j = i + 1; j < v.size(); j++) {//在v[i+1...v,size()]中选择最小元素的下标
if (v[j] < v[min])
min = j;//更新最小元素的位置
}
if (min != i) {//每一次都找出一个最小值，放在数组开头
int temp = v[min];
v[min] = v[i];
v[i] = temp;
}
}
}
堆排序
https://cuijiahua.com/blog/2018/01/algorithm_6.html
归并排序
算法思想：归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。
代码
#include<iostream>
using namespace std;
#include<vector>
void merge(vector<int>& A, int low, int mid, int high, vector<int>& B) {
int a;//a表示数组A的下标
int i;//辅助数组左侧下标
int j;//辅助数组mid右侧下标
//先将某段的有序序列复制到辅助数组B中
for (a = low; a <= high; a++) {
B[a] = A[a];
}
//从low和mid+1处的数值开始比较，较小的元素放置在数组A的位置a上
for (i = low, j = mid + 1, a = i; i <= mid && j <= high; a++) {
//i和j分别是辅助数组B的两部分数组下标，a是数组A的下标
if (B[i] <= B[j])
A[a] = B[i++];//A[a] = B[i],i++;
else
A[a] = B[j++];//A[a] = B[j],j++
}
//当i<=mid 但是j>high时，将第一部分B[i...mid]的数组直接放置在数组A中
while (i<=mid)
{
A[a++] = B[i++];//A[a] = B[i],a++,i++
}
//当i>mid 但是j<=high时，将第二部分B[mid+1...high]的数组直接放置在数组A中
while (j<=high)
{
A[a++] = B[j++];
};
}
void mergeSort(vector<int>& A, int low, int high,vector<int>& B) {
if (low < high) {
int mid = (low + high)>>1;//右移动，相当于除以2
mergeSort(A, low, mid,B);//对左半部分进行归并排序
mergeSort(A, mid+1, high,B);//对右半部分进行归并排序
merge(A, low, mid, high,B);//归并
}
}
void MegerSort(vector<int>& A) {
//归并排序一定要建立一个辅助数组temp，该数组和原数组同大小.
vector<int> B(A.size());
mergeSort(A, 0, A.size() - 1, B);
}
int main() {
vector<int> A = { 49,38,65,97,76,13,27 };
MegerSort(A);
for (int i = 0; i < A.size(); i++) {
cout << A[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
查看17道真题和解析