第七章 Sorting ¶

// bubble sort
std::vector<int> bubble_sort(const std::vector<int> &arr){
    std::vector<int> sorted_array = arr;
    int n = sorted_array.size();
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n;j++)
            if(sorted_array[i] > sorted_array[j])
                std::swap(sorted_array[i],sorted_array[j]);
    return sorted_array;
}

// selection sort
std::vector<int> selection_sort(const std::vector<int> &arr){
    std::vector<int>sorted_array = arr;
    int n = sorted_array.size();
    for(int i = 0; i < n;i++){
        int min = sorted_array[i];
        int s = i;
        for(int j = i; j < n; j ++){
            if(sorted_array[j] < min)
                s = j;
        }
        std::swap(sorted_array[i],sorted_array[s]);
    }
    return sorted_array;
}

// insertion sort
std::vector<int> insertion_sort(const std::vector<int> &arr){
    std::vector<int> sorted_array = arr;
    int n = sorted_array.size();
    for(int i = 1; i < n ;i++){
        int j = i-1; 
        int key = sorted_array[i];
        while(j > 0 && key < sorted_array[j]){
            sorted_array[j+1] = sorted_array[j];
            j--;
        }
        sorted_array[j+1] = key;
        //注意这里的写法，省略了一些步骤，不管j是否移动过，这样都可以保证最后插入正确
    }
    return sorted_array;
}

//shell_sort
std::vector<int> shell_sort(const std::vector<int> &arr){
    std::vector<int> sorted_array = arr;
    int n = sorted_array.size();
    for(int gap = n>>1; gap > 0; gap >>=1){
        for(int i = gap; i < n;i++){
            int key = sorted_array[i];
            int j = i-gap;//注意这里起始的位置
            while(j > 0 && sorted_array[j] > key){
                sorted_array[j+gap] = sorted_array[j];
                j-= gap;
            }
            sorted_array[j+gap] = key;
        }
    }
    return sorted_array;
}

// quick sort

int partition(std::vector<int> &arr,int left,int right){
    int pivot = arr[left];
    int i = left+1,j = right;
    while(i <= j){
        while(i<=j && arr[i] < pivot) i++;
        while(i<=j && arr[j] > pivot) j--;
        if(i <= j) std::swap(arr[i++],arr[j--]);
    }
    std::swap(arr[left],arr[j]);
    return j;
}

void quick_sort(std::vector<int> &arr,int left,int right){
    if(left < right){
        int pivot_position = partition(arr,left,right);
        quick_sort(arr,left,pivot_position-1);
        quick_sort(arr,pivot_position+1,right);
    }
}

// merge sort

void merge(std::vector<int> &arr,int left, int mid , int right ){
    std::vector<int> temp(right-left+1);//这里一定要初始化长度
    int i = left, j = mid + 1, k = 0;
    while(i <= mid && j <= right){
        temp[k++] = arr[i]<arr[j]? arr[i++]:arr[j++];
    }
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= right) temp[k++] = arr[j++];

    for(int i = 0; i < k;i++){
        arr[left+i] = temp[i];
    }
}

void merge_sort(std::vector<int> &arr,int left,int right){
    if(left < right){
        int mid = (left + right)/2;
        merge_sort(arr,left,mid);
        merge_sort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }    
}

// heap sort

void heapify(std::vector<int> &arr, int n, int i ){
    //在长度为n的二叉堆中调整第i个元素
    int max = i;
    int left = 2*i +1, right = 2*i + 2;

    if(left < n && arr[left] > arr[max]) max = left;//这里一定要写left<n的判断，不然不会是你想要排序的序列
    if(right <n && arr[right] > arr[max]) max = right;
    if(max != i){
        std::swap(arr[max],arr[i]);
        heapify(arr,n,max);
    }
}

void heap_sort(std::vector<int> &arr){
    int n = arr.size();
    //构建最大堆,从倒数第二层开始调整
    for(int i = n/2-1; i >=0;i--){
        heapify(arr,n,i);
    }

    //查询堆顶元素并调整到数组末尾
    for(int i = n-1 ; i >0 ;i--){
        std::swap(arr[0],arr[i]);
        heapify(arr,i,0);
    }
}

void counting_sort(vector<int> &arr,int exp){
    const int n = arr.size();
    const int base = 10;//基数排序10进制

    vector<int> counting_array(base);
    for(int i = 0; i < n;i++){//注意这里是循环原数组
        counting_array[(arr[i]/exp)%base]++;
    }

    //计算前缀和
    vector<int> prefix_sum_array(base);
    prefix_sum_array[0] = counting_array[0];
    for(int i = 1;i < base;i++){
        prefix_sum_array[i] = prefix_sum_array[i-1] + counting_array[i];
    }

    //排序
    vector<int> sorted_array(n);
    for(int i = 0; i < n;i++){
        int index = prefix_sum_array[(arr[i]/exp)%base] - 1;
        sorted_array[index] = arr[i];
        prefix_sum_array[(arr[i]/exp)%base]--;
    }
    for(int i = 0; i < n ;i++){
        arr[i] = sorted_array[i];
    }
}