void swap(int arr[], int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void BubbleSort(int arr[], int n){
    if(arr == NULL){
        return;
    }
    int sorted, i;
    for(sorted = n - 1; sorted > 0; sorted--){
        for(i = 0; i < sorted; i++){
            if(arr[i] > arr[i + 1]){
                swap(arr, i, i+1);
            }
        }
    }
}

void InsertSort(int arr[], int n){
    if(arr == NULL){
        return;
    }
    int i, j;
    for(i = 1; i< n; ++i){
        for(j = i - 1; j >= 0; j--){
            //前一个比后一个大，交换
            if(arr[j] > arr[j + 1]){
                swap(arr, j, j+1);
            }
        }
    }
}

void SelectionSort(int arr[], int n){
    if(arr == NULL){
        return;
    }
    int i, j;
    for(i = 0; i < n - 1; i++){
        int min = i;
        for(j = i + 1; j < n; j++){
            min = arr[j] < arr[min] ? j : min;
        }
        swap(arr, i, min);
    }
}

void ShellSort(int arr[], int n){
    if(arr == NULL){
        return;
    }
    int i, j;
    int gap = n/2;
    while(gap > 0){
        for(i = gap; i < n ; ++i){
            for(j = i; j >= gap; j--){
                if(arr[j - gap] > arr[j]){
                    swap(arr, j - gap, j);
                }
            }
        }
        gap >>= 1;
    }
}

void heapInsert(int arr[], int index){
    while(arr[index] > arr[(index - 1)/2]){
        swap(arr, index, (index - 1)/2);
        index = (index - 1)/2;
    }
}

void heapify(int arr[], int index, int size){
    int left = index*2 + 1;
    while(left < size){
        int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if(largest == index){
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index*2 + 1;
    }
}

void heapSort(int arr[], int n){
    if(arr == NULL){
        return;
    }
    int i,j;
    for(i = 0; i < n; i++){
        heapInsert(arr, i);
    }
    for(i = n - 1; i != 0; i--){
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
}

void quickSort(int arr[], int low, int high){
    int temp;
    int i = low, j = high;
    while(low < high){
        temp = arr[low];
        while(i < j){
            while(j > i && arr[j] > temp){
                j--;
            }
            if(i < j){
                arr[i++] = arr[j];
            }
            while(i < j && arr[i] < temp){
                i++;
            }
            if(i < j){
                arr[j--] = arr[i];
            }
        }
        arr[i] = temp;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}

    void mergeSort(int[] arr, int n) {
        if (arr == null || n < 2) {
            return;
        }
        mergeSort(arr, 0, n -1, int n);
    }

    public static void mergeSort(int arr[], int l, int r, int n) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r, n);
    }

    public static void merge(int arr[], int l, int m, int r, int n) {
        int help[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < n; i++) {
            arr[l + i] = help[i];
        }
    }