排序算法实现

记录排序算法的实现，有空就记录一点。

冒泡排序

• 比较相邻元素，如果第一个元素大于第二个元素，那么交换它们
• 完成上述步骤后，最后的元素是已排序的元素
• 对剩余未排序的元素重复上述步骤
• 排序过程中，如果没有发生至少一次交换，那么完成排序

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：稳定

public class BubbleSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // compare adjacent elements
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            // sorted
            if (flag) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        sort(arr);
    }

}

选择排序

• 在未排序的序列中找出最小（大）元素，存放到已排序的序列的末尾
• 再从剩余未排序元素中继续重复上述步骤

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定

public class SelectSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            // select min & index
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    minIndex = j;
                    min = arr[j];
                }
            }

            // swap if needed
            if (minIndex != i) {
                int tmp = arr[i];
                arr[i] = min;
                arr[minIndex] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        sort(arr);
    }

}

插入排序

• 从第二个元素开始，循环到序列结束
• 将每一个元素准确的插入到前面已排序的序列中
  每次插入，前面已排序的序列很多元素都可能会发生挪动

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：稳定

public class InsertionSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int preIndex;
        int current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                // move to right
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            // insert
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        sort(arr);
    }

}

希尔排序

• 希尔排序可以视作冒泡排序或者插入排序的泛化
• 根据间隙序列，对原始序列进行分组，然后应用插入排序
• 例如：希尔间隙序列为
  第一个分组的步长为 ，应用插入排序
  第二个分组的步长为 ，应用插入排序
  ......
  最后一个分组的步长为 1，应用插入排序

希尔排序，发明者 Donald Shell
希尔排序有很多著名的间隙序列，不同间隙序列的希尔排序的时间复杂度也不同
参考 https://en.wikipedia.org/wiki/Shellsort 的 Gap sequences

平均时间复杂度：依赖间隙序列
最好情况：、
最坏情况：、
空间复杂度：
排序方式：In-place
稳定性：不稳定

public class ShellSort {

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 希尔增量，间隙序列 N/(2^k)，最坏时间复杂度是 O(n^2)
        for (int step = arr.length >> 1; step > 0; step >>= 1) {
            sort(arr, step);
        }
    }

    public static void hibbardSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // Hibbard 增量，间隙序列 2^k-1，最坏时间复杂度是 O(n^(3/2))
        for (int k = (int) Math.sqrt(arr.length + 1); k > 0; k--) {
            int step = (int) Math.pow(2, k) - 1;
            sort(arr, step);
        }
    }

    // insertion sort with step
    private static void sort(int[] arr, int step) {
        int preIndex;
        int current;
        for (int i = step; i < arr.length; i += step) {
            preIndex = i - step;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + step] = arr[preIndex];
                preIndex -= step;
            }
            arr[preIndex + step] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        shellSort(arr);
        hibbardSort(arr);
    }

}

归并排序

• 将序列从中间分割，递归直到只剩 1 个元素
• 排序合并序列

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：Out-place
稳定性：稳定

与快速排序比较类似：

• 归并排序 先将序列从中间递归拆成只剩 1 个元素，然后排序合并序列
• 快速排序 先把基准元素放到正确的位置，然后将序列拆成左右序列，递归排序
• 但是，归并排序的时间复杂度是固定的。因为归并排序总是从中间拆开，而快速排序的基准元素的正确位置却不一定在中间，最坏情况是在端点。

public class MergeSort {

    public static int[] sort(final int[] arr) {
        if (arr.length < 2) {
            return arr;
        }

        int middle = (int) Math.floor(arr.length / 2.0);
        // left
        int[] left = sort(Arrays.copyOfRange(arr, 0, middle));
        // right
        int[] right = sort(Arrays.copyOfRange(arr, middle, arr.length));
        // merge
        return merge(left, right);
    }

    private static int[] merge(final int[] left, final int[] right) {
        int[] result = new int[left.length + right.length];
        int index = 0;
        int leftIndex = 0;
        int rightIndex = 0;

        // merge
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] <= right[rightIndex]) {
                result[index++] = left[leftIndex++];
            } else {
                result[index++] = right[rightIndex++];
            }
        }

        // fill
        while (leftIndex < left.length) {
            result[index++] = left[leftIndex++];
        }

        // fill
        while (rightIndex < right.length) {
            result[index++] = right[rightIndex++];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        arr = sort(arr);
    }

}

快速排序

• 将基准值放到正确的位置，假设该位置的索引为 pivot
  • 基准值，一般选择 arr[low]
• 以 pivot 为中心，将 arr 分为两部分，进行步骤 1

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定

提示
在 Java 中，不做额外的配置，2 万个数据左右的快速排序，就会发生 StackOverflowError 异常。这与斐波那契递归不同，因为尾递归很容易被 JIT 优化掉，用斐波那契递归测编程语言的性能，你甚至能得到 Java 性能比 C/C++ 高的错误结论。

实现 1

public class QuickSort {

    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            // partition
            int pivot = partition(arr, low, high);
            // left
            sort(arr, low, pivot - 1);
            // right
            sort(arr, pivot + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];

        while (low != high) {
            // right
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];

            // left
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }

        arr[low] = pivot;
        return low;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        sort(arr, 0, arr.length - 1);
    }

}

堆排序

基础知识
堆满足下面条件

• 堆是一颗完全二叉树（自己额外补习），可以与一维数组相互转换
• 大顶堆：每个节点的值都大于或等于其子节点的值，用于升序排列
• 小顶堆：每个节点的值都小于或等于其子节点的值，用于降序排列

• 先将序列转为大顶堆（小顶堆）
• 将根节点与最后的节点交换位置
  • 如果是大顶堆，交换后，最后元素的值为最大值
  • 如果是小顶堆，交换后，最后元素的值为最小值
• 此时只需要将数组长度减 1，重复上述步骤即可完成排序

平均时间复杂度：
最好情况：
最坏情况：
空间复杂度：
排序方式：In-place
稳定性：不稳定

其中，heapifyUp 方法在堆排序中是没有必要的，保留只是个人想记录一下。

public class HeapSort {

    public static void sort(final int[] arr) {
        if (arr.length < 2) {
            return;
        }

        int len = arr.length;

        // 构建堆，因为后续的操作要求必须是堆
        buildHeap(arr, len);

        for (int size = len - 1; size > 0; size--) {
            // 首尾交换
            int tmp = arr[0];
            arr[0] = arr[size];
            arr[size] = tmp;

            // 交换后，此时不是一个堆了，所以需要执行 heapify 操作
            // 而最后的元素是已排序的，所以这里用 size，而不是 len
            heapifyDown(arr, size, 0);
        }
    }

    private static void buildHeap(final int[] arr, int size) {
        // 从尾到首执行 heapify 操作
        // 因为叶子节点没有 left 和 right 子节点，没有向下执行 heapify 的必要
        // 因此可以优化成，从最后一个元素的 parent（即 [size / 2] - 1）开始
        for (int i = (int) (Math.floor(size / 2.0) - 1); i >= 0; i--) {
            heapifyDown(arr, size, i);
        }
    }

    /**
     * 向上执行 heapify 操作。适用场景：原先必须是一个堆，并且仅有索引为 index 的元素发生了变化。
     *
     * @param arr   完全二叉树
     * @param size  二叉树的大小
     * @param index 开始节点的索引
     */
    private static void heapifyUp(final int[] arr, final int size, int index) {
        while (index < size) {
            // parent exists || already a heap
            int parentIndex = (int) Math.floor((index - 1) / 2.0);
            if (parentIndex < 0 || arr[parentIndex] >= arr[index]) {
                return;
            }

            // swap
            int tmp = arr[index];
            arr[index] = arr[parentIndex];
            arr[parentIndex] = tmp;

            // update index
            index = parentIndex;
        }
    }

    /**
     * 向下执行 heapify 操作。适用场景：原先必须是一个堆，并且仅有索引为 index 的元素发生了变化。
     *
     * @param arr   完全二叉树
     * @param size  二叉树的大小
     * @param index 开始节点的索引
     */
    private static void heapifyDown(final int[] arr, final int size, int index) {
        while (index < size) {
            // left child not exists
            int leftIndex = 2 * index + 1;
            if (leftIndex >= size) {
                return;
            }

            int largerIndex;
            int rightIndex = 2 * index + 2;
            // right child exists && larger than left child
            if (rightIndex < size && arr[leftIndex] < arr[rightIndex]) {
                largerIndex = rightIndex;
            } else {
                largerIndex = leftIndex;
            }

            // already a heap
            if (arr[index] >= arr[largerIndex]) {
                return;
            }

            // swap
            int tmp = arr[largerIndex];
            arr[largerIndex] = arr[index];
            arr[index] = tmp;

            // update index
            index = largerIndex;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 2, 8, 4, 7};
        sort(arr);
    }

}