Java 常见排序算法实现与原理分析

排序

1. 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
2. 内部排序：在内存上的排序
3. 外部排序：需要借助磁盘等外部空间进行的排序

插入排序

1. 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入

// 插入排序
public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int j = i - 1;
        int tmp = array[i];
        for (; j >= 0; j--) {
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

分析

1. 时间复杂度：O(N^2) 最坏情况：O(N^2) 最好情况：有序的数组，O(N) 数据越有序，排序越快 适用于待排序数组基本上趋于有序了，时间复杂度趋于 O(N)
2. 空间复杂度：O(1)
3. 稳定性：是一个稳定的排序 例子：5 5 7 稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序

希尔排序

1. 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为 O(N^2)
2. 分组：分完组后，每组都采用直接插入排序
3. 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
4. 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的 5 3 都是预排序，真正的排序是最后的一组
5. 缩小增量的目的：为了让排序更接近 O(N)，为了让排序更快

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

// 对每组进行插入排序
public static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int j = i - gap;
        int tmp = array[i];
        for (; j >= 0; j -= gap) {
            if (array[j] > tmp) {
                array[j + gap] = array[j];
            } else {
                break;
            }
        }
        array[j + gap] = tmp;
    }
}

分析

1. 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

检测排序速度：

public static void testInsert(int[] array) {
    long startTime = System.currentTimeMillis();
    int[] tmp = Arrays.copyOf(array, array.length);
    Sort.insertSort(tmp);
    long endTime = System.currentTimeMillis();
    System.out.println(" " + (endTime - startTime));
}

public static void testShell(int[] array) {
    long startTime = System.currentTimeMillis();
    int[] tmp = Arrays.copyOf(array, array.length);
    Sort.shellSort(tmp);
    long endTime = System.currentTimeMillis();
    System.out.println(" " + (endTime - startTime));
}

// 逆序初始化
public static void initOrder(int[] array) {
    for (int i = 0; i < array.length; i++) {
        array[i] = array.length - i;
    }
}

public static void main(String[] args) {
    int[] arr = new int[10000];
    initOrder(arr);
    testInsert(arr);
    testShell(arr);
}

选择排序

在当前 i 下标对应的值的后面，找到后面最小的值和 i 下标对应的值交换

// 交换
public static void swap(int i, int j, int[] array) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

// 选择排序
public static void selectSort(int[] array) {
    // 在 i 下标的后面找到比 i 下标对应的值的最小值，然后交换
    int n = array.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[i]) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
        }
        swap(i, minIndex, array);
    }
}

双向选择排序 时间复杂度还是 O(N^2) 左边找最大的，右边找最小的，和第一个数和最后一个数交换

存在缺陷，maxIndex 下标可能是在 0 下标是最大的，0 下标会和最小值小标的值交换，那么 0 下标就不是最大值下标，应该更新为 maxIndex = minIndex

public static void selectSort2(int[] array) {
    // 在 i 下标的后面找到比 i 下标对应的值的最小值，然后交换
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int minIndex = left;
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < array[minIndex]) {
                minIndex = i;
            }
            if (array[i] > array[maxIndex]) {
                maxIndex = i;
            }
        }
        swap(left, minIndex, array);
        // 第一个数是最大的数，防止最小的下标和第一个数换了，最大值就在 minIndex 的位置了
        if (maxIndex == left) {
            maxIndex = minIndex;
        }
        swap(right, maxIndex, array);
        left++;
        right--;
    }
}

分析

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

堆排序

// 堆排序
private static void shiftDown(int[] array, int parent, int len) {
    int child = 2 * parent + 1;
    while (child < len) {
        if (child + 1 < len && array[child] < array[child + 1]) {
            child++;
        }
        if (array[child] > array[parent]) {
            swap(child, parent, array);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

private static void createHeap(int[] array) {
    // 建立大根堆
    for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
        shiftDown(array, parent, array.length);
    }
}

public static void heapSort(int[] array) {
    createHeap(array);
    int end = array.length - 1;
    while (end > 0) {
        swap(end, 0, array);
        shiftDown(array, 0, end);
        end--;
    }
}

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(1)
3. 稳定性：不稳定的排序

冒泡排序

// 冒泡排序
public static void bubbleSort(int[] array) {
    // i 是趟数
    for (int i = 0; i < array.length; i++) {
        // j 是比较的大小的
        boolean flag = true;
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(j, j + 1, array);
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
}

分析

1. 时间复杂度：O(N ^ 2)
2. 空间复杂度：O(1)
3. 稳定性：稳定的排序

快速排序

霍尔法

1. 根据二叉树进行递归划分

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

private static void quick(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = partitionHoare(array, start, end);
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

private static int partitionHoare(int[] array, int left, int right) {
    // 基准元素
    int tmp = array[left];
    // 记录第一个基准下标
    int i = left;
    while (left < right) {
        // 必须先找先右再左
        // 找小
        while (left < right && array[right] >= tmp) {
            right--;
        }
        // 找大
        while (left < right && array[left] <= tmp) {
            left++;
        }
        swap(left, right, array);
    }
    swap(i, left, array);
    return left;
}

2. 为什么有等于号？ 没有等于号，会死循环，比如两端都是 6

为什么先从右边开始，不先从左边开始？ 先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6 的左边有一个数比 6 大

分析

1. 时间复杂度： 最好情况下：O(N * logN) 每层都有 N 个节点，高度为 logN，需要每个节点都遍历到，N * logN 次遍历 最坏情况下：O(N^2)，有序/逆序，单分支的树
2. 空间复杂度： 最好情况下：O(logN) 最坏情况下：O(N)，有序/逆序，单分支的树 递归左边再递归右边，递归右边左边没有释放
3. 稳定性：不稳定的排序

挖坑法找基准

1. 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中

// 挖坑法
private static int partitionHole(int[] array, int left, int right) {
    // 基准元素
    int tmp = array[left];
    while (left < right) {
        // 必须先找先右再左
        // 找小
        while (left < right && array[right] >= tmp) {
            right--;
        }
        array[left] = array[right];
        // 找大
        while (left < right && array[left] <= tmp) {
            left++;
        }
        array[right] = array[left];
    }
    array[left] = tmp;
    return left;
}

前后指针法

1. 如果 cur 比基准元素小并且 cur 下标的值和 prev 下标的值不相等

// 前后指针法
public static int partition(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        while (array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(cur, prev, array);
        }
        cur++;
    }
    swap(prev, left, array);
    return prev;
}

题目

1. 优先试挖坑法，其次是 Hoare，最后是前后指针法

快排的优化

1. 均匀的分割数组
2. 让递归的次数变少

三数取中法

1. 三数取中法：left，right，mid 三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值

规定 array[mid] <= array[left] <= array[right]

// 三数取中法，求中位数的下标
private static int middleNum(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (array[left] < array[right]) {
        // 1. x < 3 < 9
        // 2. 3 < 9 < x
        // 3. 3 < x < 9
        if (array[mid] < array[left]) {
            return left;
        } else if (array[mid] > array[right]) {
            return right;
        } else {
            return mid;
        }
    } else {
        // 9 > 3 == left > right
        // 1. x > left > right
        if (array[mid] > array[left]) {
            return left;
        } else if (array[right] > array[mid]) {
            // 2. left > right > x
            return right;
        } else {
            // 3. left > x > right
            return mid;
        }
    }
}

private static void quick(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    // 1 2 3 4 5 6 7
    // 中间值的下标和第一个数交换，作为新的基准元素
    int index = middleNum(array, start, end);
    swap(index, start, array);
    // 4 2 3 1 5 6 7
    // 为了让左右分布更均匀，降低树的高度，减少递归的次数
    int pivot = partition(array, start, end);
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了

public static void insertSort(int[] array, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int j = i - 1;
        int tmp = array[i];
        for (; j >= left; j--) {
            if (array[j] > tmp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = tmp;
    }
}

private static void quick(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    if (end - start + 1 <= 15) {
        // 减少递归的次数
        // 因为最后几层节点数最多，递归次数也多
        insertSort(array, start, end);
        return;
    }
    // 1 2 3 4 5 6 7
    // 中间值的下标和第一个数交换，作为新的基准元素
    int index = middleNum(array, start, end);
    swap(index, start, array);
    // 4 2 3 1 5 6 7
    // 为了让左右分布更均匀，降低树的高度，减少递归的次数
    int pivot = partition(array, start, end);
    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}

非递归实现快排

1. 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置

// 非递归实现快速排序
public static void quickSortNor(int[] array) {
    int start = 0;
    int end = array.length - 1;
    Stack<Integer> stack = new Stack<>();
    int pivot = partitionHoare(array, start, end);
    if (pivot - 1 > start) {
        // 左边有两个元素
        stack.push(start);
        stack.push(pivot - 1);
    } else if (pivot + 1 < end) {
        // 右边至少有两个元素
        stack.push(pivot + 1);
        stack.push(end);
    }
    // 找基准里面会互换元素进行排序
    while (!stack.empty()) {
        end = stack.pop();
        start = stack.pop();
        pivot = partitionHoare(array, start, end);
        if (pivot - 1 > start) {
            // 左边有两个元素
            stack.push(start);
            stack.push(pivot - 1);
        } else if (pivot + 1 < end) {
            // 右边至少有两个元素
            stack.push(pivot + 1);
            stack.push(end);
        }
    }
}

归并排序

1. 分解：根据 mid 进行分解 合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中

// 归并排序
public static void mergeSort(int[] array) {
    merge(array, 0, array.length - 1);
}

private static void merge(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    // 分解
    merge(array, start, mid);
    merge(array, mid + 1, end);
    // 合并
    mergeHeB(array, start, mid, end);
}

private static void mergeHeB(int[] array, int left, int mid, int right) {
    int s1 = left;
    int e1 = mid;
    int s2 = mid + 1;
    int e2 = right;
    // 新数组的下标
    int k = 0;
    int[] tmpArray = new int[right - left + 1];
    while (s1 <= e1 && s2 <= e2) {
        if (array[s1] < array[s2]) {
            tmpArray[k++] = array[s1++];
        } else {
            tmpArray[k++] = array[s2++];
        }
    }
    while (s1 <= e1) {
        tmpArray[k++] = array[s1++];
    }
    while (s2 <= e2) {
        tmpArray[k++] = array[s2++];
    }
    // left 是因为有左边还有右边的数组
    // tmpArray 是临时数组，会销毁的，需要拷贝回原来的数组
    for (int i = 0; i < tmpArray.length; i++) {
        array[i + left] = tmpArray[i];
    }
}

分析

1. 时间复杂度：O(N * logN)
2. 空间复杂度：O(N)，因为每次合并数组的时候要开 O(N) 大小的额外空间
3. 稳定性：稳定的排序

非递归实现归并排序

1. 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
2. gap = 1 left = i mid = left + gap - 1 right = mid + gap gap *= 2
3. 每组合并完，最终就有序了

// 非递归实现归并排序
public static void mergeSortNor(int[] array) {
    // gap 表示每组的数据个数
    int gap = 1;
    while (gap < array.length) {
        for (int i = 0; i < array.length; i = i + 2 * gap) {
            int left = i;
            // mid 和 right 可能会越界
            // 比如只有 5 个元素
            // 分解右边一半的时候
            // l = i mid = 5 r = 7
            int mid = left + gap - 1;
            int right = mid + gap;
            if (mid >= array.length) {
                mid = array.length - 1;
            }
            if (right >= array.length) {
                right = array.length - 1;
            }
            mergeHeB(array, left, mid, right);
        }
        gap *= 2;
    }
}

海量数据的排序

1. 使用归并排序进行外部排序，如果内存中不够空间的话

非比较的排序

计数排序

1. 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
2. 适用的场景：指定范围内的数据

// 计数排序，指定范围内的数据进行排序
// O(Max(N，范围))
public static void countSort(int[] array) {
    int minVal = array[0];
    int maxVal = array[0];
    // O(N)
    for (int i = 0; i < array.length; i++) {
        if (minVal > array[i]) {
            minVal = array[i];
        }
        if (maxVal < array[i]) {
            maxVal = array[i];
        }
    }
    int len = maxVal - minVal + 1;
    int[] count = new int[len];
    // O(N)
    for (int i = 0; i < array.length; i++) {
        count[array[i] - minVal]++;
    }
    // 写回 array 数组中
    // O(范围)
    // 因为 count 数组集中于一个数字，那么也是 O(范围)
    // 如果 count 数组不集中于一个数子，也是 N 倍的范围
    // 也是 O(范围)
    int k = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            array[k++] = i + minVal;
            count[i]--;
        }
    }
}

分析

1. 时间复杂度：O(Max(N，范围))
2. 空间复杂度：O(范围)
3. 稳定性：稳定的排序

基数排序

1. 开 10 个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列

桶排序

1. 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了