排序算法

又回到最初的起点~

swap方法

使用异或来进行数组中两个位置上值的交换。

private void swap(int[] array, int i, int j) {
    if (i == j || array[i] == array[j]) {
        return;
    }
    array[j] = array[i] ^ array[j];
    array[i] = array[i] ^ array[j];
    array[j] = array[i] ^ array[j];
}

冒泡

public void bubbleSort(int[] array) {
    for (int i = array.length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

选择

每次遍历选出一个最大的，与最后一个进行交换，下次遍历不包含最后一个。

public void selectSort(int[] array) {
    for (int i = array.length - 1; i > 0; i--) {
        int maxIndex = 0;
        for (int j = 1; j <= i; j++) {
            if (array[maxIndex] < array[j]) {
                maxIndex = j;
            }
        }
        swap(array, maxIndex, i);
    }
}

插入

从 0 到 i （不包括 i ）的元素已经排好序，i 到 array.length-1 为未排序。将i与之前的元素进行比较，找到自己的位置并插入。

public void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if (array[j] < array[j - 1]) {
                swap(array, j, j - 1);
            } else {
                break;
            }
        }
    }
}

归并

public void mergeSort(int[] array) {
    if (array.length == 1) {
        return;
    }
    mergeProcess(array, 0, array.length - 1);
}
private void mergeProcess(int[] array, int l, int r) {
    if (l == r) {
        return;
    }
    int[] temp = new int[array.length];
    int mid = l + ((r - l) >> 1);
    mergeProcess(array, l, mid);
    mergeProcess(array, mid + 1, r);
    int p1 = l;
    int p2 = mid + 1;
    int index = l;
    while (p1 <= mid && p2 <= r) {
        temp[index++] = array[p1] > array[p2] ? array[p2++] : array[p1++];
    }
    while (p1 <= mid) {
        temp[index++] = array[p1++];
    }
    while (p2 <= r) {
        temp[index++] = array[p2++];
    }
    for (int i = l; i <= r; i++) {
        array[i] = temp[i];
    }
}

堆排

public void heapSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        heapInsert(array, i);
    }
    int size = array.length;
    swap(array, 0, --size);
    while (size > 0) {
        heapify(array, 0, size);
        swap(array, 0, --size);
    }
}
private void heapInsert(int[] array, int index) {
    //(index-1)/2 -> 父节点的index
    while (array[index] > array[(index - 1) / 2]) {
        swap(array, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
private void heapify(int[] array, int index, int size) {
    int left = index << 1 + 1;
    while (left < size) {
        int largest = left + 1 < size && array[left] < array[left + 1] ? left + 1 : left;
        largest = array[index] > array[largest] ? index : largest;
        if (largest == index) {
            return;
        }
        swap(array, largest, index);
        index = largest;
        left = index << 1 + 1;
    }
}

快排

public void quickSort(int[] array) {
    if (array.length <= 1) {
        return;
    }
    quickSort(array, 0, array.length - 1);
}
public void quickSort(int[] array, int left, int right) {
    if (left < right) {
        int radom = (int) (Math.random() * (right - left + 1));
        swap(array, left + radom, right);
        int[] result = partition(array, left, right);
        quickSort(array, 0, result[0] - 1);
        quickSort(array, result[1] + 1, right);
    }
}
public int[] partition(int[] array, int left, int right) {
    int midValue = array[right];
    //左部分右边界初始值
    int less = left - 1;
    //右部分左边界初始值
    int more = right;
    while (left < more) {
        if (array[left] < midValue) {
            swap(array, ++less, left++);
        } else if (array[left] > midValue) {
            swap(array, --more, left);
        } else {
            left++;
        }
    }
    swap(array, more, right);
    //返回的是中间区域的左右边界。
    return new int[]{less + 1, more};
}