Java实现常用排序算法

本文主要回顾了部分常用排序算法，包括冒泡排序，快速排序，选择排序，插入排序，希尔排序，以及归并排序。

• 稳定性和算法复杂度

稳定性：飞机插毛，即归并排序，基数排序，插入排序，冒泡排序是稳定的。 平均算法复杂度：快堆龟，即快速排序，堆排序，归并排序是nlogn。 参考blog，含gif演示，注意：该文章中的算法有误。

• 冒泡排序

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(bubbleSort(new int[]{5, 10, 25, 1, 9, 8, 15, 30, 28})));
    }

    private static int[] bubbleSort(int[] arr) {
        if (arr == null || arr.length <= 0) {
            return arr;
        }
        for (int i = 0; i < arr.length; ++i) { // 用于记录每一轮排序之后，已经确定位置的元素个数
            for (int j = 0; j < arr.length - i - 1; ++j) { // 注意arr.length - i - 1，因为j从0开始
                if (arr[j + 1] < arr[j]) { // 从小到大
                  arr[j + 1] = arr[j + 1] + arr[j];
                  arr[j] = arr[j + 1] - arr[j];
                  arr[j + 1] = arr[j + 1] - arr[j];
                }
            }
        }
        return arr;
    }
}

• 快速排序

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{15, 8, 9, 20, 1, 18, 3, 9, 11, 22};
        System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
    }

    private static int[] quickSort(int[] arr, int start, int end) {
        if (arr == null || start < 0 || end >= arr.length || start > end) {
            return null;
        }
        int partitionIndex = partition(arr, start, end);
        if (partitionIndex > start) {
            quickSort(arr, start, partitionIndex - 1);
        }
        if (partitionIndex < end) {
            quickSort(arr, partitionIndex + 1, end);
        }
        return arr;
    }

    // 算法参考geeksforgeeks
    private static int partition(int[] arr, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1)); // 随机选择一个数作为对比点
        int biggerIndex = start - 1; // 挖坑，用比对比点小的数来填
        swap(arr, pivot, end); // 将对比点置于最后一位
        for (int i = start; i < end; ++i) {
            if (arr[i] >= arr[end]) {
                biggerIndex++;
                swap(arr, i, biggerIndex);
            }
        }
        biggerIndex++;
        swap(arr, biggerIndex, end); // 最后需要将对比点归位
        return biggerIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i == j) { // 如果不加此条件，会出现置换0的情况
            return;
        }
        arr[j] = arr[j] + arr[i];
        arr[i] = arr[j] - arr[i];
        arr[j] = arr[j] - arr[i];
    }
}

• 选择排序

最稳定，无论什么数据，时间复杂度都是n^2。

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(selectionSort(new int[]{8, 19, 22, 1, 38, 2, 56, 9, 10, 34})));
    }

    private static int[] selectionSort(int[] arr) {
        if (arr.length <= 0) {
            return arr;
        }
        for (int i = 0; i < arr.length; ++i) { // 用于控制位置
            int minIndex = i;
            for (int j = i + 1; j < arr.length; ++j) { // 每次选最小的替换第一位
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }
}

• 插入排序

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(insertionSort(new int[]{2, 11, 28, 4, 81, 8, 20, 33, 15, 29})));
    }

    private static int[] insertionSort(int[] arr) {
        if (arr.length <= 0) {
            return arr;
        }
        int current;
        for (int i = 0; i < arr.length- 1; ++i) {
            current = arr[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < arr[preIndex]) { // 前插，所有数据后移
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current; // 插入
        }
        return arr;
    }
}

• 希尔排序

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(shellSort(new int[]{33, 18, 2, 30, 21, 8, 9, 65, 29, 38})));
    }

    private static int[] shellSort(int[] arr) {
        if (arr.length <= 0) {
            return null;
        }
        int temp, gap = arr.length / 2; // 以数组长度的一半作为距离
        while (gap > 0) {
            for (int i = gap; i < arr.length; ++i) {
                temp = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > temp) { // 同一代内排序，前插
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return arr;
    }
}

• 归并排序

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{18, 28, 8, 11, 20, 37, 52, 1, 89, 21})));
    }

    private static int[] mergeSort(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; ++index) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] > right[j]) {
                result[index] = right[j++];
            } else {
                result[index] = left[i++];
            }
        }
        return result;
    }
}