排序算法

学了这么久的计算机，结果还是只会冒泡排序，是时候做个了解了。

Bubble sort 冒泡排序

We import the pacage 'bits/stdc' and all codes are in the std namespace

void bubble_sort(int* arr,int len,bool(*cmp) (int,int)){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-i-1;j++){
            if(!cmp(arr[j],arr[j+1])){
                swap(arr[j],arr[j+1]);
            }   
        }
    }
}

Quick sort 快速排序

Main idea: Devide and Conquer

We devide the array into three parts: the pivot, the nums that all smaller than the pivots and the nums that are larger than it.

int partition(int* arr, int low,int high){
    int pivot=arr[high];
    int part_index=low;
    for(int i=low;i<high;i++){
        if(arr[i]<=pivot){
            swap(arr[i],arr[part_index]);
            part_index++;
        }        
    }
    swap(arr[part_index],arr[high]);
    return part_index;
}

void quick_sort(int* arr, int low,int high){
    if(low<high){
        int part_index=partition(arr,low,high);
        quick_sort(arr,low,part_index-1);
        quick_sort(arr,part_index+1,high);
    }
}

下雨 or 下雪才去学校
$$
p \lor q \rightarrow r
$$