冒泡排序
- 比较两两相邻的元素，假如目标是升序序列，那么如果第一个比第二个大，就交换他们两个。
- 当第一轮交换完毕后，最小的元素就已经归位。
- 重复以上步骤，比较未归位的元素。
代码如下（c++）
#include<iostream>
using namespace std;
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
if(arr[i] > arr[j]){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
} 最好和最坏的时间复杂度都是O（n^2），我们可以从冒泡排序算法中发现，每一次遍历都只归位一个元素。当我们遍历了一遍数组之后如果一次交换都没有进行，就说明所有数字都是正序的，那么我们后续也就不需要再遍历了。这里我们引入一个flag标志，如果某一次遍历结束都没有进行交换，可以直接退出。
优化后最好的时间复杂度是O（n），此时数组本身就是正序。最坏的时间复杂度是O（n^2）。此时数组本身逆序。
优化版冒泡排序代码：
#include<iostream>
using namespace std;
int main(){
bool flag = false;
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
if(arr[i] > arr[j]){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
flag = true;
}
if(flag == false){
break;
}
}
flag = false;
}
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
} 我们还可以发现在冒泡排序的过程中，对于相同的元素是不会进行交换处理的，所以冒泡排序是稳定的排序算法，且空间复杂度为O（1），不需要消耗额外的空间。
选择排序
- 从未排序的序列中找出最大（小）的元素，与首个元素交换
- 从剩下的序列中找出最大（小）的元素，与未排序序列首个元素交换
- 重复第二个步骤，直到整个序列有序
#include<iostream>
using namespace std;
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
int mmin = arr[i];
int pos = i;
for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
if(arr[j] < mmin){
pos = j;
mmin = arr[j];
}
}
int tmp = arr[i];
arr[i] = mmin;
arr[pos] = tmp;
}
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
}与冒泡排序类似，但是冒泡排序每次遍历是比较相邻的元素，而选择排序每次遍历是在寻找未排序序列中最大（小）的元素。所以无法像冒泡排序那样进行优化，将最好的情况的时间复杂度优化到O（n）。选择排序的最好，最坏的时间复杂度都是O（n^2）。而且也不是稳定的算法。例如2 1 2 3 6，如果是降序排序，两个2的相对位置会发生变化。
插入排序
- 将整个序列分为有序和无序两部分
- 从无序中选择一个元素，然后遍历有序序列中找到适应的位置
- 将有序序列向后移一位，为选择的元素让位
- 插入待排序元素
- 重复以上2、3、4步骤
#include<iostream>
using namespace std;
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
for(int i = 1; i < sizeof(arr)/sizeof(int); i++){
int tmp = arr[i];
int j = i-1;
for(; j >= 0; j--){
if(arr[j] > tmp){
arr[j+1] = arr[j];
}
else{
break;
}
}
arr[j+1] = tmp;
}
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
}相信读者也能发现，每次插入都涉及到已排序序列的整体移动。最坏的情况是整个序列逆序。移动次数为1,2,3,4...n-1。等差数列求和为N^2 / 2。时间复杂度为O（n^2）。最好的情况为整个序列正序，无序交换，时间复杂度为O（n）。相等元素间相对位置不会发生变化，为稳定排序算法。
希尔排序
希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
实质上就是将待排序数组进行分组，然后分组内进行一次插入排序。一轮结束之后，缩小分组个数，再次进行插入排序，直到整个数组为一组时结束。
具体实现代码如下：
#include<iostream>
using namespace std;
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
int gap;
int n = sizeof(arr)/sizeof(int);
for(gap = n >> 1; gap > 0; gap >>= 1){
for(int i = gap; i < n; i++){
int tmp = arr[i];
int j = i - gap;
for(; j >= 0; j-=gap){
if(arr[j] > tmp){
arr[j+gap] = arr[j];
}
else{
break;
}
}
arr[j+gap] = tmp;
}
}
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
}不难发现，在数组基本有序的情况下，直接插入排序较优。但是无序程度越高，希尔排序中所需要移动的次数比起直接插入排序就越少。同时，希尔排序的最坏的情况取决于我们取得增量gap。在排序的过程中gap逐渐紧缩，到最后变成1时就退化为直接插入排序，此时的数组可以看为基本有序，而且也能保证每个元素最终都会被排序到。最坏的时间复杂度是O（nlog^2n）。平均时间复杂度为O（nlogn），且是一个不稳定的排序算法。
桶排序
将各个元素按照自己所属的区间放入相应的桶中，只需要将每个桶的元素排好序，依次输出各个桶内的元素，就得到了有序的元素序列。
我们通常使用一个数组的下标来作为桶号，将每个数值放入对应的桶号当中，最后再将桶中的内容按照桶号输出。
#include<iostream>
#include<memory.h>
using namespace std;
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
int n = sizeof(arr)/sizeof(int);
int bucket[100];
memset(bucket,0,sizeof(bucket));
for(int i = 0; i < n; i++){
bucket[arr[i]]++;
}
for(int i = 0; i < 100; i++){
while(bucket[i] != 0){
cout << i << " ";
bucket[i]--;
}
}
return 0;
}桶排序的时间复杂度只有O（n），但是空间复杂度会随着序列中的元素大小变化而变化。是一种典型的用空间换时间的排序算法。适用于序列各个元素间数值大小变化较小，数据量较为庞大的场景下使用。
快速排序
升序快排实际上就是先找到一个基准数，然后将所有小于基准数的放到他的左边，大于基准数的放到他的右边。每次排序都会将基准数进行归位。这种排序算法很像冒泡排序，但是与之不同的是在归位基准数时，是用两根指针在数组的左右两边同时寻找小于和大于它的数字，如果找到的话会将他们的位置进行交换，如果左右指针重合的话就说明找完了，再将基准数进行归位。然后再对基准数左右两边的子区间继续重复以上过程。通常情况下，我们取最左边的元素为基准数。
实现代码如下
递归快排：
#include<iostream>
using namespace std;
void qsort(int nums[], int left, int right){
if(left > right) return;
int num = nums[left];
int i = left;
int j = right;
while(i < j){
while(i < j && nums[j] >= num) j--;
while(i < j && nums[i] <= num) i++;
if(i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
int tmp = nums[i];
nums[i] = num;
nums[left] = tmp;
qsort(nums,left,i-1);
qsort(nums,i+1,right);
}
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
qsort(arr,0,sizeof(arr)/sizeof(int)-1);
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
}非递归快排
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
queue<int>q;
void qsort(int nums[],int left,int right){
q.push(left);
q.push(right);
while(!q.empty()){
int i = q.front();
left = i;
q.pop();
int j = q.front();
q.pop();
right = j;
int num = nums[left];
while(i < j){
while(i < j && nums[j] >= num) j--;
while(i < j && nums[i] <= num) i++;
if(i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
nums[left] = nums[i];
nums[i] = num;
if(left < i-1){
q.push(left);
q.push(i-1);
}
if(right > i+1){
q.push(i+1);
q.push(right);
}
}
}
int main(){
int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
qsort(arr,0,sizeof(arr)/sizeof(int)-1);
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
cout << arr[i] << " ";
}
return 0;
}在快排里是左右同时进行查找比较，所以在一般情况下比较的次数是明显少于冒泡排序的。但是在完全逆序的情况下，仍然需要逐个比较后交换，所以最坏的时间复杂度为O（n^2），平均时间复杂度为 O（nlogn）。
归并排序
归并排序采用了分治的思想。
分：将整个待排序序列分为递归分为左右两个部分。
治：将左右两个有序序列进行合并。
以下展示递归实现方法：
#include<iostream>
using std::cout;
int tmp[100] = {0};
void Mergeans(int nums[], int low, int mid, int high){
for(int i = low; i <= high; i++){
tmp[i] = nums[i];
}
int i = low;
int j = mid+1;
int k = low;
while(i <= mid && j <= high){
if(tmp[i] <= tmp[j]){
nums[k++] = tmp[i++];
}
else{
nums[k++] = tmp[j++];
}
}
while(i <= mid) nums[k++] = tmp[i++];
while(j <= high) nums[k++] = tmp[j++];
}
void Merge(int nums[],int left, int right){
if(left >= right) return;
int mid = (left + right)/2;
Merge(nums,left,mid);
Merge(nums,mid+1, right);
Mergeans(nums,left,mid,right);
}
int main(){
int nums[] = {9,8,11,0,5,21,32,6,44,47};
Merge(nums,0,sizeof(nums)/sizeof(int)-1);
for(int i = 0; i < sizeof(nums)/sizeof(int); i++){
cout << nums[i] << " ";
}
return 0;
}
整体思路比较简单，这里就不再赘述。
时间复杂度就是分+治。也就是
f(n) = 2*f(n/2) + n
=2*f(2*f(n/4) + n/2) + n
.....
=2^m*f(n/2^m) + mn
当m足够大时，有：
n/2^m = 1
即m = logn，将其代入得：
f(n) = 2^logn * f(1) + n * logn
因为f(1) = 0
所以 f(n) = nlogn
时间复杂度为O（nlogn）。且是一种稳定的排序算法。
堆排序
堆排序中，我们将一个线性的序列转换成一个完全二叉树的形式。仍然使用线性序列存储。对于完全二叉树，需要利用到以下性质（下标从0开始）：
- 最后一个非叶子节点的下标为2*n-1，n为节点个数。
- 对于第i个节点，他的左儿子为2*i+1，右儿子为2*i+2。
堆排序算法如下：
- 维护一个大（小）顶堆
- 然后将堆顶元素与未排序的最后一个元素交换
- 整个堆的规模-1，剩下的部分继续重复上述操作。直到堆中只剩一个元素，即完成排序。
如何维护一个大顶堆：
- 从最后一个非叶子节点开始往前遍历，比较当前节点与其子节点的大小，如果子节点中存在大于当前节点的节点，交换父子节点。
小顶堆同理，此处不再赘述。
整体代码如下：
#include<iostream>
using namespace std;
void createheap(int nums[],int len){
int k = len/2 - 1;
while(k >= 0){
int j = 2*k+1;
if(j+1 < len){
if(nums[j] < nums[j+1]){
j = j+1;
}
}
if(nums[j] > nums[k]){
int tmp = nums[j];
nums[j] = nums[k];
nums[k] = tmp;
}
k--;
}
}
int main(){
int nums[] = {9,8,11,0,5,21,32,6,44,47};
int len = sizeof(nums)/sizeof(int);
while(len!=0){
createheap(nums,len);
int tmp = nums[len-1];
nums[len-1] = nums[0];
nums[0] = tmp;
len--;
}
for(int i = 0; i < sizeof(nums)/sizeof(int); i++){
cout << nums[i] << " ";
}
}在完全二叉树的基础上进行排序，对于n个节点，需要排序logn+log(n-1)+log(n-2)+...+1。近似的看做O（nlog）。