#include <iostream>
#include <vector>

// 冒泡排序
void bubble_sort(std::vector<int>& array){
    int array_ = 0;
    bool exchange = false;
    for(int i=0;i<array.size()-1;++i){
        exchange = false;
        for(int j=0;j<array.size()-1-i;++j){
            if(array[j] > array[j+1]){
                array_ = array[j+1];
                array[j+1] = array[j];
                array[j] = array_;
                exchange = true;
            }
        }
        if(!exchange)    break;     // 如果没有进行交换, 提前结束
    }
}

// 选择排序
void select_sort(std::vector<int>& array){
    int array_ = 0;
    for(int i=0;i<array.size()-1;++i){
        for(int j=i;j<array.size();++j){
            if(array[j] < array[i]){
                array_ = array[j];
                array[j] = array[i];
                array[i] = array_;
            }
        }
    }
}

// 插入排序
void insert_sort(std::vector<int>& array){
    int array_ = 0;
    for(int i=1;i<array.size();++i){    //从下标为1的元素开始进行
        int array_ = array[i];      //记录待插入元素
        int j;                  //从已排序序列的最右边开始查找, 找到比待插入元素最小的元素位置
        for(j=i;j>=1 && array_<array[j-1];j--){
            array[j] = array[j-1];
        }
        array[j] = array_;  //插入
    }
}

// 希尔排序
void hill_sort(std::vector<int>& array){
    int array_ = 0;
    for(int step = array.size()/2;step>0;step/=2){
        for(int i=0;i<step;i++){
            std::cout << "step: " << step << "";
            //使用直接插入排序进行
            for(int j=i+step;j<array.size();j+=step){
                array_ = array[j];
                int m;
                for(m=j;m>=step && array_ < array[m-step];m-=step)
                    array[m] = array[m-step];
                array[m] = array_;
            }
            for(auto i : array)
                std::cout << i << ' ';
            std::cout << std::endl;
        }
    }
}

void merge(std::vector<int>& array, int left, int mid, int right){
    // 采用分治思想
    std::vector<int> array_(array.size());
    int i=left, j=mid+1,k=0;
    while(i<=mid && j<=right){
        if(array[i] <= array[j]){   // 从小到大存放在array_中
            array_[k++] = array[i++];
        }else{
            array_[k++] = array[j++];
        }
    }
    // 剩余元素存放
    while (i<=mid)
    {
        array_[k++] = array[i++];
    }
    while(j<=right){
        array_[k++] = array[j++];
    }
    // 数据转移
    k = 0;
    for(int i=left;i<=right;i++){
        array[i] = array_[k++];
    }
}

// 归并排序
void merge_sort(std::vector<int>& array, int left, int right){
    if(left < right){
        int mid = left + (right-left)/2;
        merge_sort(array, left, mid);
        merge_sort(array, mid+1, right);
        merge(array, left, mid, right);
    }
}


// 快速排序
void quick_sort(std::vector<int>& array, int left, int right){
    if(left >= right)    return;
    int lp = left;
    int rp = right;
    int pivot = array[lp];
    while(lp < rp){
        // 寻找比基准小的值, 并交换
        while(lp < rp && array[rp] >= pivot){
            rp--;
        }
        if(lp < rp) array[lp] = array[rp];
        // 寻找比基准大的值, 并交换
        while(lp < rp && array[lp] <= pivot){
            lp++;
        }
        if(lp < rp) array[rp] = array[lp];
        // 重合, 赋值
        if(lp == rp)    array[lp] = pivot;
    }
    quick_sort(array, left, lp-1);  // 基准左侧
    quick_sort(array, lp+1, right); // 基准右侧
}

void heapify(std::vector<int>& array, int n, int i){
    if(i>=n)    return;

    int largest = i;
    int lson = i*2+1;
    int rson = i*2+2;

    int array_ = 0;
    if(lson < n && array[largest] < array[lson]){
        largest = lson;
    }
    if(rson < n && array[largest] < array[rson]){
        largest = rson;
    }
    if(largest!=i){
        array_ = array[i];
        array[i] = array[largest];
        array[largest] = array_;
        heapify(array, n, largest);
    }
}

// 堆排序
void heap_sort(std::vector<int>& array){
    int lastNode = array.size()-1;
    int parent = (lastNode-1)/2;
    for(int i=parent;i>=0;i--){
        heapify(array, array.size(), i);
    }
    for(int i=array.size()-1;i>=0;--i){
        heapify(array, i, 0);
    }
}

int main(){
    std::vector<int> array{3,4,2,5,6,1,7,9,8,0,0,1,30,20,0,-5};
    // int array[10] = {3,4,2,5,6,1,7,9,8,0};
    std::cout << "original: " << std::endl;
    for(auto i : array)
        std::cout << i << ' ';
    std::cout << std::endl;
    // merge_sort(array, 0, array.size()-1);
    quick_sort(array, 0, array.size()-1);
    std::cout << "\nafter:" << std::endl;
    for(auto i : array)
        std::cout << i << ' ';
}