Java数据结构之常见排序算法（下）

public void bubbleSort(int[] array) {
    // 外循环控制比较的趟数
    for (int i = 0; i < array.length - 1; i++) {
        boolean flag = true;
        // 内循环控制需要比较的元素个数
        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); //左区间
    quick(array, pivot + 1, right); //右区间
}
private int partitionHoare(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--;
        }
        // 左边找比基准大的数的下标
        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;
    }
    // 三数取中
    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;
    }
    // 小区间优化 -> 如果待排序的数据小于15个,我们直接使用直接插入排序
    if ((right - left + 1) < 15) {
        insertSort(array);
        return;
    }
    // 三数取中
    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) {
    // 准备归并 -> 将传过来的两个有序区间, 合并成一个有序区间
    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++];
        }
    }
    // 跳出循环之后, begin1 和 begin2 区间总有一个区间还有剩余的元素未拷贝进tmp
    while (begin1 <= end1) {
        tmp[k++] = array[begin1++];
    }
    while (begin2 <= end2) {
        tmp[k++] = array[begin2++];
    }
    // 将tmp的数据拷回array中
    for (int i = 0; i < k; i++) {
        array[i + left] = tmp[i];
    }
}