一、交换排序

基本思想：两两比较待排序记录关键字，当两个关键字不满足次序要求时进行交换，直到整个序列满足要求为止。

冒泡排序

两两比较关键字，如逆序则交换顺序，较大关键字逐渐一端移动，直到序列有序。

void bubble_sort(int arr[], int n) {
    for(int i=0; i<n-1; i++) {
        bool flag = true;
        for(int j=0; j<n-i; j++) {
            if(arr[j]>arr[j+1]) {
                flag = false;
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
        if(flag)
            break;
    }
}

算法特点：
? 1、稳定排序
? 2、可用于链式存储结构
? 3、记录移动次数较多，算法平均性能比直接插入排序差，当初始记录无序时，n较大时，不宜采用

选择排序

基本思想：每一趟排序从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录中，直到全部排完为止。

//简单选择排序
void select_sort1(int arr[],int n){
    int k;
    for(int i = 0; i < n; i++){
        k = i;
        for(int j = i+1; j < n; j++){
            if(arr[k] > arr[j])
                k = j;
        }
        if(k != i){
            int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp;
        }
    }
}

算法特点：
? 1、算法本身是稳定排序，也可以变成是不稳定排序
? 2、可以用于链式存储结构
? 3、移动次数少，当每一个记录占用的空间较多时，此方法比直接插入排序快。

快速排序

由冒泡排序改进得到，冒泡排序只对相邻两个记录进行比较，因此每次只能消除一个逆序，而快速排序一次交换可消除多个逆序，从而提高排序性能。

int median3(int arr[], int L, int R) {
    int mid = L + (R - L)/2;
    if(arr[L] > arr[mid])
        swap(arr[L], arr[mid]);
    if(arr[L] > arr[R])
        swap(arr[L], arr[R]);
    if(arr[mid] > arr[R])
        swap(arr[mid], arr[R]);
    swap(arr[mid], arr[R - 1]);
    return arr[R - 1];
}

void quicksort(int arr[], int L, int R) {
    if(L > R)
        return;
    // int mid = L + (R-L)/2;
    int pivot = median3(arr, L, R);
    int i = L;
    int j = R-1;
    while(i<j) {
        while(arr[++i] < pivot) {}
        while(arr[--j] > pivot) {}
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[R-1]);
    quicksort(arr, L, i-1);
    quicksort(arr, i+1, R);
}

void quick_sort(int arr[], int n) {
    quicksort(arr, 0, n-1);
}