常用排序算法

本文转自小豆子的菜鸡学JAVA公众号，尊重原创，转载请声明

冒泡排序

算法思想

通过两两相邻间的元素进行比较找出最小（大）的数，然后通过交换将其顺序排列
基本步骤

第一轮循环中拿第一数依次与其他元素进行比较交换确定出最大的数后，第二循环则无需与已确认的最大的数据比较，依次循环最终达到数组顺序排列
平均时间复杂度

O(N^2)，当数据接近正序时，冒泡排序性能越好

代码实现

public void sort1() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

插入排序

算法思想

是将未排序的数组插入到已排序的数组中
基本步骤

定义左边第一个数为已排序的数，循环从第二个开始，和其前一元素进行比较，若前一元素大于当前元素则进行交换，否则直接进入下一轮开始继续依次往前进行比较得出排序结果
平均时间复杂度

平均时间复杂度和冒泡排序一样为O(N^2)性能略优于冒泡排序。最差的情况是完全倒序，性能和冒泡排序一样

代码实现

public void sort2() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    int i, j;
    for (i = 1; i < arr.length; i++) {
        int temp = arr[i];
        for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
            //交换操作
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

快速排序

算法思想

通过一趟排序，将数组分割为2个独立数组，分割点左边都是比它小的数，右边都是比它大的数。然后按照此方法对这两部分进行快排，整个过程可以递归进行
基本步骤

首先以待排序数据最左边和最右边下标为边界，定义left和right，以最下标left为基数，从右边往左寻找比基数小的数赋值到下标为left进行交换，在从左边往右边寻找比基数大的数赋值到下标为right中，当left=right时，停止查找，将base赋值到left与right下标重合位置。此时得到的重合位置即为当前元素最为合适的位置，此元素左边都是比基数小的数，右边是比基数大的数，分别对两个数组再次使用首次排序的步骤进行排序
平均时间复杂度

O(Nlog2N)，最坏的情况为每次选择的base值都是最小的，时间复杂度为O(N^2)

代码实现

public void sort3() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    sort3_quick_sort(arr, 0, arr.length - 1);
    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

private int sort3_first_sort(int[] arr, int left, int right) {

    //设置最左边为基数
    int base = arr[left];
    //left和right必须不重合，否则不用排序
    while (left < right) {
        //从右往左寻找比基数小的数，替换基数
        while (left < right && arr[right] >= base) {
            right--;
        }
        arr[left] = arr[right];
        //从左往有寻找比基数大的数，替换right
        while (left < right && arr[left] <= base) {
            left++;
        }
        arr[right] = arr[left];
    }
    //替换指针重合位置
    arr[left] = base;
    return left;

}

private void sort3_quick_sort(int[] arr, int left, int right) {

    //当left与right重合时，不用排序
    if (left < right) {
        //寻找第一轮中已经排好序的下标,此位置已经最合适不用排序
        int mid = sort3_first_sort(arr, left, right);
        //排列基数左边的（比基数小的）
        sort3_quick_sort(arr, left, mid - 1);
        //排列基数右边的（比基数大的）
        sort3_quick_sort(arr, mid + 1, right);
    }

}

希尔排序

算法思想

按照最大间隔步长数进行两两比较，其中间隔步长数逐步减小一直减小到最小步长为止
基本步骤

首先取数组的一半为步长，从步长位置处开始按照间隔步长位置与前面元素进行比较交换，第二次轮训则按照第一次循环的步长的一半，按照第一次的步骤继续进行比较交换，第三次循环的步长则取第二次步长的一半，一直取到步长为1的最后一次两两比较完成时停止
平均时间复杂度

O(Nlog2N)，最坏的情况为O(N^1.5)

代码实现

public void sort4() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    int gap = arr.length / 2;
    int i, j;

    while (gap >= 1) {
        for (i = gap; i < arr.length; i++) {
            int temp = arr[i];
            for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }

        //步长/2
        gap = gap / 2;
    }

    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

选择排序

算法思想

每次循环询找到最小元素放到首个位置，在剩余N-1中在寻找最小元素放到首个位置，以此类推直到循环结束
基本步骤

第一轮循环比较找出最小的元素与第一个位置进行交换，第二轮从第二个位置元素开始寻找剩余集合中最小元素与数组第二个位置进行交换，按照此方式循环到末尾截止
平均时间复杂度

O(N^2)

代码实现

public void sort5() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    int min, index;

    for (int i = 0; i < arr.length; i++) {
        min = arr[i];
        index = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < min) {
                min = arr[j];
                index = j;
            }
        }

        if (index != i) {
            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;
        }
    }

    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

归并排序

算法思想

先将数组拆分为最小单位，然后进行两两合并，最终合并成一个
基本步骤

首先将数组拆分为2段，在递归拆分这两段，当拆分到最小单位时，再进行逐步合并，最终合并为一个数组，其核心思想为二分法
平均时间复杂度

O(Nlog2N)，算法很稳定

代码实现

public void sort6() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    sort6_sort(arr, 0, arr.length - 1);
    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}



private void sort6_sort(int[] arr, int low, int high) {

    if (low < high) {
        //注，mid为index
        int mid = (high + low) / 2;
        sort6_sort(arr, low, mid);
        sort6_sort(arr, mid + 1, high);
        sort6_merge(arr, low, mid, high);
    }

}



private void sort6_merge(int[] arr, int low, int mid, int high) {

    int i = low;
    int j = mid + 1;
    //定义临时合并数组
    int[] tempArr = new int[high - low + 1];
    //合并下标
    int k = 0;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            tempArr[k++] = arr[i];
            i++;
        } else {
            tempArr[k++] = arr[j];
            j++;
        }
    }

    //处理低段未处理的数据
    if (i <= mid) {
        for (int l = i; l <= mid; l++) {
            tempArr[k++] = arr[l];
        }
    }

    //合并高段未处理的合并
    if (j <= high) {
        for (int l = j; l <= high; l++) {
            tempArr[k++] = arr[l];
        }
    }

    //将临时数组赋值合并到主数组中
    k = 0;
    for (int l = low; l <= high; l++) {
        arr[l] = tempArr[k++];
    }

}

堆排序

算法思想

先将数组R[0…n]调整为堆（大根堆/小根堆，堆：是一个完全二叉树，每个节点不大于其孩子节点则为小根堆，每个节点不小于其孩子节点则为大根堆），然后交换R[0]和R[n]，重新将R[0…n-1]调整为堆，交换R[0]和R[n-1]，如此反复操作，直到交换R[0]和R[1]为止
基本步骤

首先将数组R[0…n]调整为大根堆，交换R[0]和R[n]，将最大值交换到最后，在将数组末尾已经确认的最大数去掉，将剩下的数组元素调整为大根堆，交换首末元素，重复操作，直到交换R[0]和R[1]为止，则结束循环
平均时间复杂度

O(Nlog2N)，空间复杂度为O(1)，算法不稳定

代码实现

private void heapSort() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();
    //将数组调整为大根堆
    for (int i = arr.length / 2; i >= 0; i--) {
        createHeap(arr, i, arr.length);
    }

    //
    for (int i = arr.length - 1; i > 0; i--) {
        //交换首末元素
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        //除掉已确认的末尾节点，再次创建大根堆，此时根节点则为0
        createHeap(arr, 0, i);
    }

    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

private void createHeap(int[] arr, int parent, int length) {

    //临时保存父节点值
    int temp = arr[parent];
    //获取左孩子节点
    int child = 2 * parent + 1;
    while (child < length) { //存在孩子节点
        //若存在右孩子节点，且右孩子节点值是否大于左孩子节点值，则取右孩子节点
        if ((child + 1) < length && arr[child + 1] > arr[child]) {
            child++;
        }
        //判断父节点值是否大于孩子节点，若大于，则直接退出
        if (temp >= arr[child]) {
            break;
        }

        //否则交换父节点与孩子节点值
        arr[parent] = arr[child];
        arr[child] = temp;
        //设置孩子为父节点
        parent = child;
        child = 2 * parent + 1;
    }

}

基数排序

算法思想

按照0…9分别建立10个桶，将数组中每个元素的个位数大小，依次放到各个桶中，将0…9的10桶中数字连接起来；在根据元素十位进行重复操作，直到位数为最大数字的位数为止
基本步骤

首先将数组中最大的数取出，定义0-9的10个桶数组，依次从个位开始，将数组中元素按照个位数字分别放到10个桶中，循环结束后将桶中的元素依次替换到原数组中，再根据元素十位重复进行上述操作，直到位数达到最大数的位数为止
平均时间复杂度

O(d(n+r))，空间复杂度为O(n+r)，算法稳定

代码实现

private void radixSort() {

    int[] arr = new int[array.length];
    System.arraycopy(array, 0, arr, 0, array.length);
    System.out.println("原：" + Arrays.toString(arr));
    long start = System.currentTimeMillis();

    //计算最大值
    int max = arr[0];
    for (int tt : arr) {
        if (tt > max) {
            max = tt;
        }
    }

    //排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
    int[][] buckets = new int[10][arr.length];
    //用于保存每个桶里有多少个数字
    int[] order = new int[arr.length];
    int index = 0;
    //从各位开始
    for (int i = 1; max / i > 0; i *= 10) {
        //将数组里的每个数字放在相应的桶里
        for (int j = 0; j < arr.length; j++) {
            int digit = (arr[j] / i) % 10;
            buckets[digit][order[digit]++] = arr[j];
        }

        //将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
        for (int j = 0; j < order.length; j++) {
            if (order[j] > 0) {
                for (int k = 0; k < order[j]; k++) {
                    arr[index++] = buckets[j][k];
                }
            }
            order[j] = 0;
        }
        index = 0;
    }

    long end = System.currentTimeMillis();
    System.out.println("新：" + Arrays.toString(arr));
    System.out.println("耗时：" + (end - start) + "ms");

}

更多原创内容，请关注菜鸡学JAVA
xiaocaiji

Aweew

常用排序算法

常用排序算法

冒泡排序

插入排序

快速排序

希尔排序

选择排序

归并排序

堆排序

基数排序