排序
这里有个带图的博客，有助于理解和复习，博客链接
冒泡排序（Bubble Sort）
思路：一共有n个数，那么需要比n-1趟，每一趟比上次都会少比一个数，因为每次都会把最大的数上浮上去（从小到大排）。
时间复杂度： 平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ，最好平均时间复杂度n2（指的是未优化的冒泡排序）。
空间复杂度： O(1) , 因为只需要一个temp变量
稳定性 ：是稳定的，因为如果两个值相等，它们之间不需要做交换
//未优化的冒泡排序
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
int temp = 0;
for(int i = 0; i < n-1; ++i){
for(int j = 0; j < n-1-i; ++j){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
}
return 0;
} 可以做一个简单的优化，每次用isSwap检验这一轮是否发生过交换，如果没有，说明剩下的序列是有序的，不需要再排。这样最好平均时间复杂度是O（n）。
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
int temp = 0;
int isSwap = 0;
for(int i = 0; i < n-1; ++i){
isSwap = 0;
for(int j = 0; j < n-1-i; ++j){
if(arr[j] > arr[j+1]){
isSwap = 1;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(isSwap==0){
break;
}
}
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
} 选择排序（Selection Sort）
思路： 将序列分为有序区和无序区，每次从无序区中选择一个出来最小的数，放在序列的首部，构成有序区的尾部，直到所有无序区排列完成。
时间复杂度： 平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ，最好平均时间复杂度n2
空间复杂度 O（1）
稳定性 ： 不稳定 ，对于序列6 9 6 3 10， 第一遍选择第1个元素6会和3交换，那么原序列中2个6的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void sort(int *arr ,int len);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
sort(arr,n);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void sort(int *arr ,int len){
int minIndex ;
int temp;
for(int i = 0 ;i< len - 1; ++i){
minIndex = i;
for(int j = i + 1; j < len; ++j){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
插入排序
思路: 好比打扑克牌的时候，桌子上一堆无序的牌，每次抠出来一张，就插在手上握着的有序的牌，手上的牌是左边的有序区，桌上的牌是右边的无序区。
时间复杂度：平均时间复杂度 n2 , 最坏平均时间复杂度 n2 ，最好平均时间复杂度n
空间复杂度：空间复杂度 O(1)
稳定性 ： 稳定 ，可以让后面的数不插在相等的数前面
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void sort(int *arr ,int len);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
sort(arr,n);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void sort(int *arr ,int len){
int preIndex ,current;
for(int i=1;i<len;++i){
current = arr[i];
preIndex = i-1;
while(preIndex>=0 && arr[preIndex] > current){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
}快速排序
思路： 对于每个要排列的区间，选择第一个数或者最后一个数作为基准，将该区间的数，分为两部分左边的小于基准，右边的大于基准，两个指针移动的过程中，关键在于最后i==j的位置就是基准插入的地方。
关于分析快速排序的时间的复杂度，和BST类似，想成一个二叉搜索树，最糟糕的情况就是一字长蛇阵，最好的情况就是类似于满二叉树，对于每一层都要做n次比较，而树的深度可以为n ，也可以为log2n,所以...
时间复杂度 ： 平均时间复杂度 nlog2n , 最坏平均时间复杂度 n2 ，最好平均时间复杂度nlog2n
空间复杂度 ： 最好是log2n 最坏是n
稳定性： 不稳定，不稳定发生在基准和其他元素交换的时刻
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int arr[maxn];
void quickSort(int *arr ,int s ,int t);
int main(){
int n;
while(cin>>n){
for(int i = 0; i < n; ++i){
cin>>arr[i];
}
quickSort(arr,0,n-1);
int flag = 1;
for(int i = 0 ; i < n ; ++i){
if(flag){
cout<<arr[i];
flag=0;
} else {
cout<<" "<<arr[i];
}
}
cout<<endl;
}
return 0;
}
void quickSort(int *arr ,int s ,int t){
int i = s;
int j = t;
int temp ;
if(s<t){
temp = arr[s];
while(i!=j){
while(j>i && arr[j] >= temp ) j--;
arr[i] = arr[j];
while(j>i && arr[i] <= temp ) i++;
arr[j] = arr[i];
}
arr[i] = temp ;
quickSort(arr,s,i-1);
quickSort(arr,i+1,t);
}
}
堆排序
时间复杂度 ： 最好最坏是nlog2n
空间复杂度 ： O（1）
稳定性： 不稳定
#include <iostream>
using namespace std;
const int maxn = 1e5+5;
int tree[maxn];
int parent(int i){
return i/2;
}
int left(int i){
return i*2;
}
int right(int i){
return i*2+1;
}
void swap(int tree[],int i,int j){
int temp = tree[i];
tree[i] = tree[j];
tree[j] = temp;
}
void max_heapify(int tree[] , int n , int i){
int l = left(i);
int r = right(i);
int largest = i;
if(l <= n && tree[l] > tree[i]){
largest = l;
}
if(r <= n && tree[r] > tree[largest]){
largest = r;
}
if(largest != i){
swap(tree,i,largest);
max_heapify(tree , n , largest);
}
}
void build_heap(int tree[] ,int n){
int last_node = n ;
for(int i = last_node / 2; i>=1 ;--i){
max_heapify(tree, n, i);
}
}
void heap_sort(int tree[] ,int n) {
build_heap(tree,n);
int i;
for(i = n; i >= 1; --i) {
swap(tree,i,1);
max_heapify(tree, i-1, 1);
}
}
int main(){
int n;
cin>>n;
for(int i=1 ; i <= n ; ++i){
cin>>tree[i];
}
heap_sort(tree,n);
int i;
for(i = 1;i <= n; ++i){
cout<<tree[i]<<endl;
}
return 0;
} 