Java 数据结构：八大排序算法

运行结果如下：

时间复杂度：O(N^2)，最慢情况为 1+2+3……+n，求和 n(n+1)/2。 空间复杂度：O(1)，仅多开辟了 temp。 稳定性：稳定，遇到 <= temp 就会退出循环，相同元素不会改变位置。 特点：元素集合越接近有序，效率越高。

希尔排序

思想：将待排序列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表间隔，最终完成整个序列的排序。

1. 选择增量序列 gap，常用 (n/2, n/4...1)。
2. 分组进行插入排序，逐渐缩小增量，直到增量为 1，对整个序列进行一次插入排序。

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 3, 4};
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2;
            shell(array, gap);
        }
    }

    public static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > temp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = temp;
        }
    }
}

运行结果如下：

稳定性：不稳定。 时间复杂度：O(N) ~ O(N^2)。 空间复杂度：O(1)。

直接选择排序

思想：每次从待排序数据元素中找到最小或最大的一个元素，放在待排序的起始位置，直到全部排完。

实现：遍历待排序列，记录当前下标 i，再遍历其后面的元素，判断是否有比它小的，如果有记录当前下标，然后进行交换。

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 3, 4};
        selectSort(array);
        System.out.println(Arrays.toString(array));
    }

    // 选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

时间复杂度：O(N^2)。 空间复杂度：O(1)。 稳定性：不稳定。

堆排序

思想：利用堆这种数据结构进行排序。大根堆用于排升序，小根堆用于排降序。

思路（以排升序为例）：

1. 将数组创建为大根堆。
2. 定义 end 表示最后一个元素下标，每次堆顶元素最大，将堆顶与堆底交换，end--，重新向下调整为大根堆。
3. 直到 end 为 0 截止。

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 3, 4};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    // 堆排序（从小到大，使用大堆）
    public static void heapSort(int[] array) {
        createHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            siftDown(array, 0, end);
            end--;
        }
    }

    private static void createHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(array, parent, array.length);
        }
    }

    private static void siftDown(int[] array, int parent, int length) {
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

时间复杂度：O(N*logN)。 空间复杂度：O(1)。 稳定性：不稳定。

冒泡排序

思想：通过重复地遍历待排序列表，比较相邻元素并交换位置。每遍历一次确定一个最后一个元素。

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 3, 4};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

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

快速排序

思想：高效的排序算法，使用分治法。找到一个基准值，将列表分为两部分，左边小于基准值，右边大于基准值，递归处理左右部分。

1. 通常以第一个为基准值，调整左右。
2. 递归基准值下标左边和右边，直到左边下标 >= 右边下标结束。
3. 使用 Hoare 方法调整：high 从右向左找比基准值小的值，low 从左向右找比基准值大的值，交换，直到 low >= high，将 low 下标与基准值交换。

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 11, 4};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

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

    private static void quick(int[] array, int left, int right) {
        if (left >= right) return;
        int key = hoare(array, left, right);
        quick(array, left, key - 1);
        quick(array, key + 1, right);
    }

    private static int hoare(int[] array, int low, int high) {
        int i = low;
        int temp = array[low];
        while (low < high) {
            while (low < high && array[high] >= temp) high--;
            while (low < high && array[low] <= temp) low++;
            swap(array, low, high);
        }
        swap(array, i, low);
        return low;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

上面使用的是 Hoare 方法来调整列表。

也可以使用挖坑法：先定义临时变量存放基准值，先从后向前找小于基准值的值放入低处坑中，再从前往后找大于基准值的值放入高处坑中，重复直到 low >= high，最后将基准值放入坑中。

private static int partition(int[] array, int low, int high) {
    int temp = array[low];
    while (low < high) {
        while (low < high && array[high] >= temp) high--;
        array[low] = array[high];
        while (low < high && array[low] <= temp) low++;
        array[high] = array[low];
    }
    array[low] = temp;
    return low;
}

快速排序优化：三数取中

为了避免数列有序导致时间复杂度退化为 N^2，可以使用三数取中法，将 low、mid、high 下标的值中最中间的值作为基准值。

private static int mid(int[] array, int low, int high) {
    int m = (low + high) / 2;
    if (array[low] < array[high]) {
        if (array[m] < array[low]) return low;
        else if (array[m] > array[high]) return high;
        else return m;
    } else {
        if (array[m] < array[high]) return high;
        else if (array[m] > array[low]) return low;
        else return m;
    }
}

时间复杂度：O(N*logN) ~ O(N^2)。 空间复杂度：O(logN)。 稳定性：不稳定。

快速排序非递归形式

使用栈进行操作，符合条件将下标入栈，缩小基准值调整范围，不断入栈出栈，当栈为空时结束。

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 11, 99, 33, 22, 11, 4, 7, 8};
        quickSortNor(array);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSortNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        int par = partition(array, 0, end);
        Stack<Integer> stack = new Stack<>();
        if (par > start + 1) {
            stack.push(start);
            stack.push(par - 1);
        }
        if (par < end - 1) {
            stack.push(par + 1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            par = partition(array, start, end);
            if (par > start + 1) {
                stack.push(start);
                stack.push(par - 1);
            }
            if (par < end - 1) {
                stack.push(par + 1);
                stack.push(end);
            }
        }
    }

    private static int partition(int[] array, int low, int high) {
        int temp = array[low];
        while (low < high) {
            while (low < high && array[high] >= temp) high--;
            array[low] = array[high];
            while (low < high && array[low] <= temp) low++;
            array[high] = array[low];
        }
        array[low] = temp;
        return low;
    }
}

运行结果如下：

归并排序

思想：采用分治法，先将子序列变为有序，再将子序列归并进行排序，最终整体有序。

即分解和合并两个操作。先将其分解到不能分解，合并过程中注意合并成有序数列。

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 11, 4, 7, 8};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void mergeSort(int[] array) {
        mergeSortChild(array, 0, array.length - 1);
    }

    private static void mergeSortChild(int[] array, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSortChild(array, left, mid);
        mergeSortChild(array, mid + 1, right);
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                temp[k++] = array[s1++];
            } else {
                temp[k++] = array[s2++];
            }
        }
        while (s1 <= e1) temp[k++] = array[s1++];
        while (s2 <= e2) temp[k++] = array[s2++];
        for (int i = 0; i < temp.length; i++) {
            array[i + left] = temp[i];
        }
    }
}

运行结果如下：

时间复杂度：O(N*logN)。 空间复杂度：O(N)。 稳定性：稳定。

计数排序

思想：非比较型排序。通过数组下标来存放对应的值，如果值和某个下标相同，将该下标对应的值++，相当于用 count 数组记录每个数出现的次数。

1. 获取最大值和最小值，确定数组长度 range = max - min + 1。
2. 将 array[i] 对应的值为 count 的下标，遇到就++（需减去 min 防止越界）。
3. 循环 count 数组，如果 count[i] != 0，将下标放入 array 数组（需加上 min）。

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] array = {3, 1, 2, 11, 4, 7, 8};
        countSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void countSort(int[] array) {
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) max = array[i];
            if (array[i] < min) min = array[i];
        }
        int range = max - min + 1;
        int[] count = new int[range];
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - min]++;
        }
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                array[k] = i + min;
                count[i]--;
                k++;
            }
        }
    }
}

时间复杂度：O(n + k)，n 是列表长度，k 是数据范围。 空间复杂度：O(n + k)。