// 选择
void selection_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i ++) {
        int min = i;
        for (int j = i + 1; j < len; j ++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            int t = arr[i];
            arr[i] = arr[min];
            arr[min] = t;
        }
    }
}

// 冒泡
void bubble_sort(int arr[], int len) {
    for (int i = 0; i < len - 1; i ++) {
        for (int j = 0; j < len - i - 1; j ++) {
            if (arr[j] > arr[j + 1]) {
                int max = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = max;
            }
        }
    }
}

// 插入
void insertion_sort(int arr[], int len) {
    for (int i = 1; i < len; i ++) {
        int insert = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > insert) {
            arr[j + 1] = arr[j];
            j --;
        }
        arr[j + 1] = insert;
    }
}

// 希尔
void shell_sort(int arr[], int len) {
    for (int gap = len >> 1; gap > 0;  gap >>= 1) {
        for (int i = gap; i < len; i ++) {
            int j;
            int insert = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > insert; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = insert;
        }
    }
}

// 快速
void quick_sort_recursive(int arr[], int left, int right) {
    if(left >= right) {
        return ;
    }
    
    int L = left, R = right, key = arr[left];
    
    while(L < R) {
        while(L < R && key <= arr[R]) {
            R --;
        }
        arr[L] = arr[R];

        while(L < R && key >= arr[L]) {
            L ++;
        }
        arr[R] = arr[L];
    }
    
    arr[L] = key;
    quick_sort_recursive(arr, left, L - 1);
    quick_sort_recursive(arr, L + 1, right);
}

void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}