排序算法c++实现

包括归并排序（2个版本，list和vector的），快速排序，堆排序，简单插入排序，选择排序，冒泡排序6种排序的c++代码，还没有整理。

#include 
#include 
#include 
using namespace std;

//list非递归版的归并排序，STL中list的merge函数实现方式
void merge(list<int>& list){
    list<int> carry;
    list<int> counter[64];
    int fill = 0;
    while(!list.empty()){
        carry.splice(list.begin(), list,list.begin());
        int i = 0; 
        while(i < fill && !counter[i].empty()){
            counter[i].merge(carry);
            carry.swap(counter[i++]);
        }
        carry.swap(counter[i]);
        if(i == fill) ++i;
    }
    for(int i = 1; i < fill; i++){
        counter[i - 1].merge(counter[i]);
    }
    list.swap(counter[fill]);
}



//归并排序
//3个函数均是闭区间
//时间复杂度：最好o(nlogn), 最坏o(logn)，平均o(logn)
//空间复杂度:o(n)
//稳定
void merge(vector<int> &vec, int left, int right, vector<int>& result){
    int left_length = (right - left + 1) / 2 + 1;
    int left_start = left;
    int right_start = left + left_length;
    int result_start = left;
    while(left_start < left + left_length && right_start < right + 1){
        if(vec[left_start] < vec[right_start]){
            result[result_start++] = vec[left_start++];
        }else{
            result[result_start++] = vec[right_start++];
        }
    }
    while(left_start < left + left_length){
        result[result_start++] = vec[left_start++];
    }
    while(right_start < right + 1){
        result[result_start++] = vec[right_start++];
    }
}

void merge_sort(vector<int> &vec, int left, int right, vector<int> &result){
    if(0 == right - left){
        return ;
    }else if(1 == right - left){
        if(vec[left] > vec[right]){
            swap(vec[left], vec[right]);
        }
    }else{
        int mid = left + (right - left + 1) / 2;
        merge_sort(vec, left, mid, result);
        merge_sort(vec, mid + 1, right, result);
        for(int i = left; i <= right; i++){
            vec[i] = result[i];
        }
    }
}

void merge_sort_1(vector<int> & vec){
    vector<int> result(vec.size());
    merge_sort(vec, 0, vec.size() - 1, result);
}


//堆排序
//时间：最好o(nlogn)，最坏o(logn)，平均o(logn)
//空间：o(1)
//不稳定
//向下调整函数
void adjustDown(vector<int> &vec,int size, int parent){
    int child = parent * 2 + 1;
    while(child < size){
        if(child + 1 < size && vec[child + 1] > vec[child]){
            child++;
        }
        if(vec[child] > vec[parent]){
            swap(vec[child], vec[parent]);
            parent = child;
            child = parent * 2 + 1;
        }else{
            break;
        }
    }
}

void heap_sort(vector<int> &vec){
    int size = vec.size();
    for(int i = (size - 2) / 2; i >= 0; i-- ){
        adjustDown(vec, size, i);
    }
    int end = size - 1;
    while(end){
        swap(vec[0],vec[end]);
        //这里必须用end，不能用size
        adjustDown(vec, end, 0);
        end--;
    }
}


//简单选择排序
//时间：最好o(n ^ 2),最坏o(n ^ 2)
//空间：原地
//稳定的
void select_sort(vector<int> &vec){
    int n = vec.size();
    for(int i = 0; i < n; i++){
        int minIndex = i;
        //选择最小
        for(int j = i + 1; j < n; j++){
            if(vec[minIndex] > vec[j]){
                minIndex = j;
            }
        }
        //交换
        if(minIndex != i){
            swap(vec[i], vec[minIndex]);
        }
    }
}


//时间：最好o(1), 最坏o(n ^ 2), 平均o(n ^ 2)
//空间：原地
//稳定的
void bubble_sort(vector<int> &vec){
    int n = vec.size();
    //这里排序 n - 1此就可以了
    for(int i = 0; i < n - 1; i ++){
        int flag = false;
        //进入此循环后，后i个元素都是有序的，因此只需要n - i 就可以了
        for(int j = 1; j < n - i; j++){
            if(vec[j - 1] < vec[j]){
                swap(vec[j - 1], vec[j]);
                flag = true;
            }
        }
        if(!flag){
            //如果一趟下来，falg灭有改变，说明已经有序了，退出
            return;
        }
    }
}
//时间复杂度：最好o(n)，最坏o(n ^ 2)，平均o(n ^ 2)
//空间：原地
//稳定的
void insert_sort(vector<int> &vec){
    int n = vec.size();
    for(int i = 1; i < n; i++){
        if(vec[i - 1] < vec[i]){
            continue;
        }
        for(int j = i - 1; j < n; j++){
            int Val = vec[j];
            int index = j;
            //循环查找位置
            while( j >= 0 && vec[j] > Val){
                vec[j + 1] = vec[j];
                j--;
            }
            vec[j + 1] = Val;
        }
    }
}

//左闭右闭区间
//时间：最好o(nlogn) ,最坏o(n ^ 2),平均o(nlogn)
//空间：栈空间n(logn)
//不稳定
void quick_sort(vector<int> &vec, int left, int right){
    if(left < right){
        int i = left, j = right;
        int midVal = vec[left + (right - left) / 2];//一种优化
        swap(vec[left], vec[left + (right - left) / 2]);//选择优化时必须swap
        while(i < j){
            //里面的2个循环不能交换
            while(i < j && vec[j] >= midVal) j--;
            vec[i] = vec[j];
            while(i < j && vec[i] <= midVal) i++;
            vec[j] = vec[i];
        }
        //将一个值放在了正确的位置
        vec[i] = midVal;
        //递归，注意左闭右闭
        quick_sort(vec, left, i - 1);
        quick_sort(vec, i + 1, right);
    }
}