• 选择排序

vector<int> selectionSort(vector<int> v){
    int temp ;
    int size = (int)v.size();
    if(size<2) return v;
    for(int i=0; i<=size-2;++i){
        for(int j=i+1; j<=size-1;++j){
            if(v[i]>v[j]){
                temp = v[j];
                v[j] = v[i];
                v[i] = temp;
            }
        }
    }
    return v;
}

对于任何输入，时间为O(n*n)；

• 冒泡排序

vector<int> bubbleSort(vector<int> v){
    int size = (int)v.size();
    if(size<2) return v;
    int temp;
    bool finish ;
    for(int i = size-1;i>0; --i){
        finish =  true;
        for(int j = 0; j<i; ++j){
            if(v[j]>v[j+1]){
                temp = v[j];
                v[j] = v[j+1];
                v[j+1] = temp;
                finish = false;
            }
        }
        if(finish)
            break;
    }
    return v;
}

最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，平均：O(n*n)， 最差：O(n*n)

• 插入排序

vector<int> insertionSort(vector<int> v){
    int size = (int)v.size();
    if(size<2) return v;
    int temp ;
    for(int i=1; i<size;++i){
        int j = i-1;
        temp = v[i];
        while(j>=0){
            if(temp<v[j]){
                v[j+1]=v[j];
                --j;
            }else{
                break;
            }
        }
        v[j+1]=temp;
        }
    return v;
}

最优(升序的数组)：O(n)， 最差（严格递减的数组）:O(n*n)，平均(比最差性能快一倍)：O(n*n)
（遇到基本有序的数组时能表现出优异的性能）

• 希尔排序

void shellSort(vector<int>& v)
{
    int size = (int)v.size();
    if(size<2) return;
    int incre = size/2;
    int temp;
    for(; incre>=1; incre/=2)
    {
        for(int i=incre; i<size;++i)
        {
            int j = i - incre;
            temp = v[i];
            while(j>=0&&temp<v[j])
            {
                v[j+incre] = v[j];
                j -= incre;
            }
            v[j+incre] = temp;
        }
    }
}

• 归并排序

void mergeSort(vector<int>& v, int begin, int end){
    int size = end-begin;
    if(size<2) return;
    int mid = (end-begin)/2+begin;
    mergeSort(v, begin, mid);
    mergeSort(v,  mid, end);
    merge(v, begin, mid, end);
}

void merge(vector<int>& v, int begin, int mid, int end){
    vector<int>va;
    va.assign(v.begin()+begin, v.begin()+mid);
    vector<int>vb;
    vb.assign(v.begin()+mid, v.begin()+end);
    int i=0, j=0;
    int size_a = (int)va.size();
    int size_b = (int)vb.size();
    while(i<size_a&&j<size_b){
        if(va[i]<vb[j]){
            v[begin+i+j]=va[i];
            ++i;
        }else{
            v[begin+i+j]=vb[j];
            ++j;
        }
    }
    while(i<size_a){
        v[begin+i+j]=va[i];
        ++i;
    }
    while(j<size_b){
        v[begin+i+j]=vb[j];
        ++j;
    }
}

最优与平均与最差都是：O(n*log n)
优点在于其稳定性，缺点是需要额外的空间

• 快速排序

void quickSort(vector<int> &v, int begin, int end){
    if(end-begin<2) return;
    int i = begin;
    int j = end-1;
    int key = v[begin];
    while(i<j){
        while(i<j&&v[j]>key){
            --j;
        }
        if(i<j){
            v[i]=v[j];
        }
        while(i<j&&v[i]<key){
            ++i;
        }
        if(i<j){
            v[j]=v[i];
        }
    }
    v[i]=key;
    quickSort(v, begin, i);
    quickSort(v, i+1, end);
}

最优：O(n*log n) ， 平均：O(n*log n) ，最差（严格递增的数组，这时插入排序能表现出优异性能）：O(n*n) => 引入随机性即使用随机的元素作为中轴能解决这个窘境（随机快速排序）

• 归并排序对子数组的划分非常快速，时间耗在合并上，
  而快速排序时间则耗在子数组的划分上。

• 堆排序

vector<int> heapSort(vector<int> &v){
    int size = (int)v.size();
    if(size<2)return v;
    heapBottomUp(v);
    int temp;
    vector<int> sortedVector;
    for(int i=0;i<size;++i){
        temp = getTheHeadTop(v);
        sortedVector.insert(sortedVector.begin(), temp);
    }
    return sortedVector;
}

//自底向上（即从无序到有序）构造最大堆
// 自底向上与自顶向下的区别：
//自顶向下：从无到有的构造 ； 自底向上：从无序到有序的构造
void heapBottomUp(vector<int> &v){
    //默认根节点的号码为1， 而向量vector的索引起始为0，注意错位
    int size = (int)v.size();
    if(size<2)return ;
    int i, k, j,  fatherValue;
    bool heap = false;
    for( i=size/2;i>=1; --i){
        k = i;
        fatherValue = v[k-1];
        heap = false;
        while(!heap && 2*k<=size){
            j = 2*k;
            if(j+1<=size){ //存在两个子女
                j = v[j-1]<v[j+1-1]? j+1:j;
            }
            if(fatherValue>v[j-1]){
                heap=true;
            }else{
                v[k-1]=v[j-1];
                k=j;
            }
        }
        v[k-1] = fatherValue;
    }
}

//获取最大堆顶上的数字
int getTheHeadTop(vector<int>& v){
    int size = (int)v.size();
    if(size<1) return 0;
    int result = v[0];
    if(size==1){
        v.pop_back();
        return result;
    }
    v[0]=v[size-1];
    v.pop_back();
    //堆复原处理
    int i = 1; //根节点号码
    int fatherValue = v[i-1];
    int k;
    while(2*i<=size){
        k=2*i;
        if(k+1<=size){
            k = v[k-1]<v[k+1-1]?k+1:k;
        }
        if(fatherValue>v[k-1]){
            break;
        }else{
            v[i-1]=v[k-1];
        }
        i=k;
    }
    v[i-1]=fatherValue;
    return result;
}

• 堆排序与归并排序的性能差不多，不管平均还是最差情况下都是：O(n*log n)
  但堆排序是可以在位的，即不需要额外的存储空间，相比归并排序更省空间。
  针对随机文件的计时实验指出，堆排序比快速排序运行得慢。但与归并排序相差无几。