/*
    排序算法
*/

#include<bits/stdc++.h>
using namespace std;
void bubbleSort(vector<int> arr) {
    cout << "冒泡排序" << endl;
    int n = arr.size();
    // i也可表示为以及确定位置的元素个数
    // 所以j < n - i - 1
    for(int i = 0; i < n - 1; i ++) {
        for(int j = 0; j < n - i - 1; j ++) {
            if(arr[j] > arr[j + 1]) {
                swap(arr[j],arr[j + 1]);
            }
        }
    }
    for(int i = 0; i < n; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 思路：从当前元素向前进行比较，如果比当前元素大就向后移动
// 如果没有就退出，空缺位置补上
void insertSort(vector<int>  arr) {
    cout << "插入排序" << endl;
    int n = arr.size();
    for(int i = 1; i < n; i ++) {

        int key = arr[i];
        int j = i - 1;
        while(j >=0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j --;
        }
        arr[j + 1] = key;
    }
    for(int i = 0; i < n; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 思路：每次记录最值下标，然后进行交换
void selectionSort(vector<int> arr) {
    cout << "选择排序" << endl;
    int n = arr.size();
    for(int i = 0; i < n - 1; i ++) {
        int min_idx= i;
        for(int j = i + 1; j < n; j ++) {
            if(arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i],arr[min_idx]);
    }
    for(int i = 0; i < n; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}


// 快排思路：选择一个基准元素进行两部分排序
void quickSort(vector<int> & arr,int l,int r) {
    if(l >= r) return;
    int i = l - 1,j = r + 1,x = arr[l + r >> 1];
    while(i < j) {
        do i ++;
        while(arr[i] < x);
        do j --;
        while(arr[j] > x);
        if(i < j) swap(arr[i],arr[j]);
    }
    quickSort(arr,l,j);
    quickSort(arr,j + 1,r);
}

int temp[8];
// 归并排序：将数组进行不断二分，然后对每个部分进行排序
// 最后合并为最终数组
void mergeSort(int arr[],int l,int r) {

    if(l >= r)return;
    int mid = l + r  >> 1;
    mergeSort(arr,l ,mid),mergeSort(arr,mid + 1,r);
    int k = 0,i = l ,j = mid + 1;
    while(i<= mid && j <= r) {
        if(arr[i] < arr[j]) temp[k ++] = arr[i ++];
        else temp[k ++] = arr[j ++];
    }

    while(i <= mid) temp[k ++] = arr[i ++];
    while(j <= r) temp[k ++] = arr[j ++];

    for(int i = l,j = 0; i <= r; i ++,j ++) {
        arr[i] = temp[j];
    }
}
int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    int n = arr.size();
    bubbleSort(arr);
    insertSort(arr);
    selectionSort(arr);
    cout << "快排" << endl;
    quickSort(arr,0,n - 1);


    for(int i = 0; i < n; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    reverse(arr.begin(),arr.end());

    for(int i = 0; i < n; i ++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << "归并排序" << endl;
    int nums[] = {64, 34, 25, 12, 22, 11, 90};
    mergeSort(nums,0,n - 1);
    for(int i = 0; i < n; i ++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}