排序算法

排序算法

资料

面试中的 10 大排序算法总结

冒泡排序

• 从后往前循环比较相邻两数，小数前大数后，一遍完成最小数即排在最前，最后循环排序

实现

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    int index = arr.length - 1;
    for (int i = 0; i < index; i++) {
        for (int j = index; j > i; j--) {  // 最小在最前
            if (arr[j] < arr[j - 1]) {  // 小在前大在后
                exchange(arr, j, j - 1);
            }
        }
    }
}

private static void exchange(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

简单选择排序

• 从前向后循环排序，查找最小数互换位置

实现

public static void selectSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    int minIndex;
    int length = arr.length;
    for (int i = 0; i < length - 1; i++) {
        // 选择最小
        minIndex = i;
        for (int j = i + 1; j < length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 置最前
        if (minIndex != i) {
            exchange(arr, i, minIndex);
        }
    }
}

堆排序

• 使用二叉堆的特性，调整为大顶堆，选择最大值出堆，最后循环调整大顶堆出堆

特性

• 树是一对多的数据结构，从一个根结点开始，生长出它的子结点，而每一个子结点又生长出各自的子结点，成为子树。如果某个结点不再生长出子结点了，它就成为叶子。
• 二叉树每个结点最多只有两棵子树，而且左右子树是有顺序的，不可颠倒。
• 满二叉树的所有分支结点都既有左子树又有右子树，并且所有叶子都在同一层。
• 完全二叉树不一定是满的，但它自上而下，自左而右来看的话，是连续没有缺失的。
• 二叉堆是完全二叉树或者近似完全二叉树，父结点的值总是大于或等于(小于或等于)任何一个子节点的值。
• 存储为一维数组，子i父(i-1)/2，父i子2i+1和2i+2
• 入堆，末尾添加，尾元素比较上浮
• 出堆，首尾互换，首元素比较下沉，尾元素出堆

实现

public static void heapSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    int length = arr.length;
    for (int i = length / 2 - 1; i >= 0; i--) {  // 从最后一个元素的父开始整理，建立大顶堆
        adjustMaxHeap(arr, i, length);
    }

    for (int i = length - 1; i > 0; i--) {  // 堆出队列，首尾互换，最大置尾，堆调整
        exchange(arr, 0, i);
        adjustMaxHeap(arr, 0, i);
    }
}

private static void adjustMaxHeap(int[] arr, int start, int end) {
    int temp = arr[start];

    int child = start * 2 + 1; // 左边子
    while (child < end) {
        if ((child + 1) < end && arr[child] < arr[child + 1]) {  // 两子节点比较选大
            child++; // 右边子
        }

        if (arr[child] <= temp) break; // 已是大顶堆

        // 否则父沉子浮
        arr[start] = arr[child];

        // 再循环调整
        start = child;
        child = start * 2 + 1;
    }
    arr[start] = temp;
}

直接插入排序

• 分序列为左有序右无序，从第二个数开始向后循环，与有序序列循环比较大小确定位置插入

特性

• 如果序列基本有序或者长度较小时，使用直接插入排序效率就非常高

实现

public static void insertSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    int insertNum;
    int length = arr.length;
    for (int i = 1; i < length; i++) {
        insertNum = arr[i]; // 无序序列第一个数，即需要插入的数
        int j = i - 1; // 有序序列最后位置
        while (j >= 0 && arr[j] > insertNum) {  // 大则后移
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = insertNum;
    }
}

二分插入排序

• 分序列为左有序右无序，从第二个数开始向后循环，在有序序列中二分查找确定位置插入

实现

public static void binarySort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    int insertNum;
    int length = arr.length;
    for (int i = 1; i < length; i++) {
        insertNum = arr[i]; // 无序序列第一个数，即需要插入的数

        // 二分查找
        int left = 0; // 插入位置
        int right = i - 1; // 有序序列最后位置
        for (int middle; left <= right; ) {
            middle = left + (right - left) / 2;
            if (arr[middle] < insertNum) {
                left = middle + 1;
            } else if (arr[middle] > insertNum) {
                right = middle - 1;
            } else {
                left = middle + 1;
                break;
            }
        }

        // 批量后移
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        arr[left] = insertNum;
    }
}

希尔排序

• 增量分组，组内插入排序，然后增量二分缩减再插入排序，最后循环缩减增量至一

特性

• 时间复杂度可以达到O(n^1.3)

实现

public static void shellSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    for (int step = arr.length / 2; step >= 1; step /= 2) {  // 增量分组
        for (int i = 0; i < step; i++) {  // 组内插入排序
            insertSort(arr, step);
        }
    }
}

private static void insertSort(int[] arr, int step) {
    int insertNum;
    int length = arr.length;
    for (int i = step; i < length; i += step) {
        insertNum = arr[i]; // 无序序列第一个数，即需要插入的数
        int j = i - step; // 有序序列最后一个数
        while (j >= 0 && arr[j] > insertNum) {  // 大则后移
            arr[j + step] = arr[j];
            j -= step;
        }
        arr[j + step] = insertNum;
    }
}

快速排序

• 确定首数为基准数比较大小，从右往左循环小数换位，从左往右循环大数换位，循环至中间相遇位置置为基准数，最后以中间位置分左右两个序列递归

实现

public static void quickSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;

    int baseNumber = arr[start]; // 基准数
    int left = start, right = end;
    while (left < right) {
        while (left < right && arr[right] >= baseNumber) right--; // 右边寻找小与基准数
        if (left < right) arr[left++] = arr[right]; // 小数左移
        while (left < right && arr[left] <= baseNumber) left++; // 左边寻找大于基准数
        if (left < right) arr[right--] = arr[left]; // 大数右移
    }
    arr[left] = baseNumber; // 基准赋值

    // 分开递归
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
}

归并排序

• 二分序列归并排序，最后比较大小合并

特性

• 使用了递归分治的思想，先递归划分子问题，然后合并结果

实现

public static void mergeSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    mergeSort(arr, 0, arr.length - 1);
}

private static void mergeSort(int[] arr, int start, int end) {
    if (start >= end) return;

    // 二分递归
    int middle = (start + end) / 2;
    mergeSort(arr, start, middle);
    mergeSort(arr, middle + 1, end);

    merge(arr, start, middle, end); // 合并
}

private static void merge(int[] arr, int start, int middle, int end) {
    int left = start, right = middle + 1;
    int length = end - start + 1;
    int[] temp = new int[length]; // 临时数组

    // 存入临时数组
    int index = 0;
    while (left <= middle && right <= end) {  // 左右两数组比较，小的存入
        temp[index++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
    }
    // 剩下的存入临时数组
    while (left <= middle) {
        temp[index++] = arr[left++];
    }
    while (right <= end) {
        temp[index++] = arr[right++];
    }

    // 还原
    for (int i = 0; i < length; i++) {
        arr[start + i] = temp[i];
    }
}

计数排序

• 序列的值作为计数数组的下标，统计每个数字的个数，最后依次输出计数数组的下标

特性

• 待排序的数要满足一定的范围的正整数
• 计数排序需要比较多的辅助空间
• 时间复杂度为O(n)

实现

public static void countSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    // 以值为脚标建立计数数组
    int max = 0;
    for (int item : arr) {
        if (item > max) max = item;
    }

    // 映射分配，排序
    int[] count = new int[max + 1];
    Arrays.fill(count, 0);
    for (int i : arr) {
        count[i]++;
    }

    // 还原
    int index = 0;
    for (int i = 0; i <= max; i++) {
        for (int j = 0; j < count[i]; j++) {
            arr[index++] = i;
        }
    }

}

桶排序

• 序列分别映射至有序的桶，桶内排序，最后依次输出

特性

• 映射函数：关键字k1 < k2，那么f(k1) <= f(k2)，即桶(i)最大的数小于桶(i+1)中最小的数
• 桶越多，桶内需排序的数则越少，单占用空间越大

实现

public static void bucketSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    // 创建桶，使用链表
    int bucketNumber = 10;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucketNumber; i++) {
        buckets.add(new LinkedList<Integer>());
    }

    // 映射分配
    int index;
    for (int item : arr) {
        index = item / bucketNumber; // 映射关系
        buckets.get(index).add(item);
    }

    // 排序，还原
    index = 0;
    for (List<Integer> bucket : buckets) {
        if (!bucket.isEmpty()) {
            Collections.sort(bucket); // 桶内排序
            for (Integer integer : bucket) {
                arr[index++] = integer; // 还原
            }
        }
    }
}

基数排序

• 序列按最大位数分趟，按进制分桶，按位的值映射至桶，再依次输出，最后趟循环

特性

• 多关键字分成多趟单关键字，单关键字排序，最后趟循环

实现

public static void radixSort(int[] arr) {
    if (arr == null || arr.length == 0) return;

    // 确定趟数，趟数为最大位数
    int max = 0;
    for (int item : arr) {
        int length = Integer.toString(item).length();
        if (length > max) max = length;
    }

    // 创建桶，桶数为进制数
    int bucketNumber = 10;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucketNumber; i++) {
        buckets.add(new LinkedList<Integer>());
    }

    // 按趟排序
    int index;
    for (int i = 0; i < max; i++) {
        // 映射分配，排序
        for (int item : arr) {
            // 映射关系，按位获取
            String s = Integer.toString(item);
            index = 0;
            if (s.length() > i) {
                index = s.charAt(s.length() - i - 1) - '0';
            }

            buckets.get(index).add(item);
        }

        // 还原
        index = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                for (Integer integer : bucket) {
                    arr[index++] = integer;
                }
            }
            bucket.clear();
        }
    }
}