部分图片来源：牛客网
本文如果涉嫌侵权，请告知笔者第一时间做处理。
排序问题可以说是最经典的算法问题了。从排序问题上可以看到人们对效率孜孜不倦的渴求，也算是算法进化史的一个小小的缩影。
冒泡排序、选择排序与插入排序
早期的算法时间复杂度为O(N^2)，它们用笨拙和单纯的方式，跨出了算法历史上小小的一步。
冒泡排序
通过依次比较两两相邻的元素，并把两者中较大值交换[注1]至右侧，这样遍历过一次数组后，就会把最大值移动到队尾。对数组剩下的部分继续做此操作，直至排序完成。
CODE
int* bubbleSort(int* A, int n) {
//长度为n的数组需要遍历n-1次
for(int i=0;i<n-1;++i){
//遍历开始时右侧已排好i个元素，故待处理区间为[0,n-i)
//因为需要j+1<n-i所以j的取值是[0,n-i-1)
for(int j=0;j<n-i-1;++j){
if(A[j]>A[j+1]){
swap(A[j],A[j+1]);
}
}
}
return A;
}
要点
- 两层循环
- 外层每次循环选出当前范围内的最大值移至队尾
- 内层依次遍历当前范围，两两比较相邻元素
- 外层计数范围：
[0,n-1) - 内层计数范围：
[0,n-i-1)
选择排序
通过选出当前范围内的最小值并交换到队首，对剩下的部分不断重复该操作直至排序结束。
CODE
int* selectionSort(int* A, int n) {
//长度为n的数组需要遍历n-1次
for(int i=0;i<n-1;++i){
//每次找出最小值的下标
int min=i;
//A[i]暂定为最小值，故j遍历范围是[i+1,n)
for(int j=i+1;j<n;++j){
if(A[j]<A[min])
min=j;
}
//交换
swap(A[min],A[i]);
}
return A;
}
要点
- 两层循环
- 外层每次循环把当前范围内的最小值移至队尾
- 内层依次遍历当前范围，选出最小值
- 外层计数范围：
[0,n-1) - 内层计数范围：
[i+1,n)
插入排序
待处理元素左侧是一个已经排好序的数组（初始长度为1），从右向左遍历该有序数组，找到合适的位置插入待处理元素，直至所有元素处理完毕。
CODE
int* insertionSort(int* A, int n) {
//初始时认为A[0]是有序数列，待处理元素范围是[1,n)
for(int i=1;i<n;i++){
int get=A[i];
//待处理元素的插入位置从i-1到0逆序搜索
int j=i-1;
//搜索条件：j未越界且位置j上的元素大于待处理元素
while(j>=0&&A[j]>get){
//相当于元素右移一位
A[j+1]=A[j];
j--;
}
//循环结束时若j越界：需插入到A[0]处；
//否则A[j]<=get需要插入到A[j+1]处
A[j+1]=get;
}
return A;
}
要点
- 两层循环
- 外层循环遍历待处理的元素
- 内层循环遍历左侧有序序列，找到合适的位置插入待处理元素
- 插入位置的选择：大于待处理元素的部分右移一位，直至越界或遇见不大于待处理元素的部分。
- 特别需要提出的是，对于一个近乎有序的序列，插入排序的效率很高
附注
[1] 交换代码如下
void swap(int& a,int& b){
//加上不等判断来提高性能
if(a!=b){
int t=a;
a=b;
b=t;
}
}
