public void bubbleSort(int[] array) {
    // 外循環(huán)控制比較的趟數(shù)
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = true;
        // 內循環(huán)控制需要比較的元素個數(shù)
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                flag = false;
            }
        }
        if (flag) {
            return;
        }
    }
}

public void quickSort(int[] array) { 
    quick(array, 0, array.length - 1);
}

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1); //左區(qū)間
    quick(array, pivot + 1, right); //右區(qū)間
}
private int partitionHoare(int[] array, int left, int right) {
    int pivot = array[left]; //將該區(qū)間第一個數(shù)作為基準值
    int begin = left;
    int end = right;
    while (begin < end) {
        // 右邊找比基準小的數(shù)的下標, 為什么要取 >= 呢？
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        // 左邊找比基準大的數(shù)的下標
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        // 交換
        swap(array, begin, end);
    }
    swap(array, left, begin);
    return begin; //返回基準值當前所處的下標, 左邊都比它小, 右邊都比它大
}

private int findMidValOfIndex(int[] array, int left, int right) {
    int mid = (left + right) >> 1;
    if (array[left] < array[right]) {
        if (array[left] < array[mid]) {
            // 走到這里面, left位置一定是最小的值
            // 我們這里只需要判斷 mid 和 right 哪個位置小即可
            if (array[mid] < array[right]) {
                //mid是第二大的值
                return mid;
            } else {
                return right;
            }
        } else {
            // 走到這里, 則left位置小于等于right位置, 并大于mid位置, 則left是第二大的值
            return left;
        }
    } else { // 走這個else表示left位置大于等于right位置
        if (array[left] > array[mid]) {
            // 走到這里表示 left 位置一定是最大的值,
            // 我們只需要判斷 mid 和 right 位置哪個大即可
            if (array[mid] > array[right]) {
                return mid;
            } else  {
                return right;
            }
        } else {
            //走到這表示 left位置大于right位置, 并小于等于mid位置, 則left是第二大的值
            return left;
        }
    }
}

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 三數(shù)取中
    int mid = findMidValOfIndex(array, left, right);
    swap(array, left, mid);
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1);
    quick(array, pivot + 1, right);
}

private void quick(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    // 小區(qū)間優(yōu)化 -> 如果待排序的數(shù)據(jù)小于15個,我們直接使用直接插入排序
    if ((right - left + 1) < 15) {
        insertSort(array);
        return;
    }
    // 三數(shù)取中
    int mid = findMidValOfIndex(array, left, right);
    swap(array, left, mid);
    int pivot = partitionHoare(array, left, right);
    quick(array, left, pivot - 1);
    quick(array, pivot + 1, right);
}

private int partitionPivot(int[] array, int left, int right) {
    int pivot = array[left];
    int begin = left;
    int end = right;
    while (begin < end) {
        while (begin < end && array[end] >= pivot) {
            end--;
        }
        array[begin] = array[end];
        while (begin < end && array[begin] <= pivot) {
            begin++;
        }
        array[end] = array[begin];
    }
    array[begin] = pivot;
    return begin;
}

private int partitionPointer(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        // && 后面的避免自己跟自己交換
        if (array[cur] < array[left] && ++prev != cur) {
            swap(array, prev, cur);
        }
        cur++;
    }
    swap(array, left, prev);
    return prev;
}

public void mergeSort(int[] array) {
    mergeSortChild(array, 0, array.length - 1);
}
private void mergeSortChild(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
 
    int mid = (left + right) >> 1;
    mergeSortChild(array, left, mid);
    mergeSortChild(array, mid + 1, right);
    merge(array, left, mid, right);
}
private void merge(int[] array, int left, int mid, int right) {
    // 準備歸并 -> 將傳過來的兩個有序區(qū)間, 合并成一個有序區(qū)間
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int[] tmp = new int[right - left + 1];
    int k = 0;
    while (begin1 <= end1 && begin2 <= end2) {
        if (array[begin1] < array[begin2]) {
            tmp[k++] = array[begin1++];
        } else {
            tmp[k++] = array[begin2++];
        }
    }
    // 跳出循環(huán)之后, begin1 和 begin2 區(qū)間總有一個區(qū)間還有剩余的元素未拷貝進tmp
    while (begin1 <= end1) {
        tmp[k++] = array[begin1++];
    }
    while (begin2 <= end2) {
        tmp[k++] = array[begin2++];
    }
    // 將tmp的數(shù)據(jù)拷回array中
    for (int i = 0; i < k; i++) {
        array[i + left] = tmp[i];
    }
}