常用排序算法及java示例

本文主要是介绍常用排序算法及java示例，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

排序算法

冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O(n^2)	是
快排、归并	O(nlogn)	是
桶、计数、基数	O(n)	否

冒泡排序

排序过程

只操相邻的两个元素
每次冒泡操作比较相邻元素，如果不满足大小关系，进行交换
每趟遍历找到当前剩余元素中最大的那个，并放到合适位置
n趟遍历后完成排序

特点

稳定排序、原地排序（空间复杂度为O(1)）

代码

    public void bubbleSort(int array[]) {
        for (int i = 0; i < array.length - 1; i++) {
            // 减去i，是因为已经找到了最大的i个元素，放到了最后面，不用再比较了
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 如果左边的元素大于右边的，进行交换
                // 必须是大于，不能用大于等于，如果相等，不操作，保持排序的稳定性
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

优化点

如果在排序过程中，某一趟遍历没有进行任何交换操作，说明已经有序了，后面的遍历就不必再进行了，所以可以加个标记，判断当前遍历是否发生过交换操作，如果没有就结束排序吧。

插入排序

排序过程

将数组分为两个区间：已排序和未排序区间
已排序区间初始只有第一个元素
取未排序区间的元素在已排序区间找到合适的位置插入，并保证已排序区间的有序性
重复第3步，直到未排序区间的元素为空

特点

稳定排序、原地排序（空间复杂度为O(1)）

代码

    public void insertionSort(int[] array) {
        // 从索引1开始，索引0为已排序区间的第一个元素
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) {
                    // 这里作数据移动，就是交换当前的两个元素，把比目标元素大的，最终都交换到它的后面
                    // 因为只处理比目标元素大的，等于它的时候已经结束了，所以保证排序的稳定性
                    int tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                }
            }
        }
    }

优化点

示例代码采用了每一步比较的时候，元素交换的写法来移动元素。还有另外一种写法：就是先记录下目标元素的值，比较的时候，如果被比较的元素比目标元素大，直接后移，最后找到合适位置，将目标元素赋值给它。

选择排序

排序过程

将数组分为两个区间：已排序和未排序区间
已排序区间最初为空
每次从未排序里找到一个最小的元素放到已排序区间的末尾
重复第3步，直到未排序区间只剩一个元素

特点

不稳定排序、原地排序（空间复杂度为O(1)）

代码

    public void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    // 找到最小的那个
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                // 交换元素，把最小的放到已排序区间末尾
                int tmp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = tmp;
            }
        }
    }

归并排序

排序过程

归并采用分治的思想，将待排序的数组从中间分成左右两个更小的数组，分别进行排序并合并，该过程递归处理，直到数组不可再分割。

特点

稳定排序，非原地排序（空间复杂度O(n)）

代码

public class MergeSort {

    public void sort(int[] array) {
        // 左右边界索引
        sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(array, left, mid);
            sort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }

    private void merge(int[] array, int left, int mid, int right) {
        // 创建一个容纳left -> right元素的额外数组
        int[] tmp = new int[right - left + 1];
        // 左半区间的起始索引
        int ll = left;
        // 右半区间的起始索引
        int rl = mid + 1;
        // tmp数组的起始索引
        int k = 0;
        while (ll <= mid && rl <= right) {
            // 谁小取谁
            tmp[k++] = array[ll] < array[rl] ? array[ll++] : array[rl++];
        }
        // 将左半区间剩余的元素复制过来，也可以直接调用 System.arraycopy方法
        while (ll <= mid) {
            tmp[k++] = array[ll++];
        }
        // 将右半区间剩余的元素复制过来
        while (rl <= right) {
            tmp[k++] = array[rl++];
        }
        // 此时tmp里的都是两个区间合并后有序的，copy进原数组，从原数组的left位置开始
        System.arraycopy(tmp, 0, array, left, tmp.length);
    }
}

快速排序

排序过程

采用分治思想，从数组里选取一个元素作为分区点，将数组分为两个区间，将比它小的放到左区间，比它大的放到右区间，重复处理这两个区间，直到子区间大小为1结束。

特点

非稳定排序，原地排序（空间复杂度O(1)），也可以借用额外空间，非原地排序。

代码

public class QuickSort {

    public void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        // 选取最后一个元素作为分区点
        int pivot = array[right];
        // 用来查下一个分区位置
        int pos = left;
        // 从第一个元素开始
        for (int i = left; i < right; i++) {
            if (array[i] < pivot) {
                // array[i] 得放到小区间了
                int tmp = array[i];
                array[i] = array[pos];
                array[pos] = tmp;
                // 我们是从第一个元素开始的，如果第一个元素小于pivot怎么办，那就会走到这里，让pos指向下一个元素，不过这种情况上面的这个交换其实意义不大了
                // 如果遇到下一个元素比pivot大了，这时候刚好pos指向它。因为array[i] < pivot，才能走到这个逻辑，所以找到下一个比pivot小的，然后进行交换
                pos++;
            }
        }
        // 把pos位置的和pivot换了
        int tmp = array[right];
        array[right] = array[pos];
        array[pos] = tmp;

        sort(array, left, pos - 1);
        sort(array, pos + 1, right);
    }
}

下面的3种排序，存在使用场景及限制条件，对要排序的数据要求比较苛刻，用的也不广泛，就当是为了面试了解下吧

桶排序

排序过程

将待排序的n个元素均匀到划分到m个桶
每个桶内平均有k=n/m个元素，这是最理想的情况下。如果数据分布不均匀，可能有的桶多，有的桶少，桶装不下还得扩容。
每个桶内部继续排序，可选择快排等其它排序算法
桶本身是有序的，每个桶内部排好序后，一次遍历即可

既然每个桶内部还要排序，为什么说它是O(n)的排序算法？当桶的数量接近待排序元素的数据量时，时间复杂度就接近O(n)。

场景

要求数据分布均匀，如果分布不均匀，最坏情况下时间复杂度会退化为O(nlogn)
数据天然有序，这样划分的每个桶也是有序的

比较适合外排这样的场景。

代码

这个代码是我根据这个排序过程写出来的，只作示例，仅供参考。

这个demo看一下明白啥意思就行，这个demo写的太简单了，要求测试数据必须大于0，且不能重复。

public class BucketSort {

    public static void main(String[] args) {

        int[] array = {5, 2, 8, 99, 4, 60, 77, 13, 55, 22};
        Arrays.stream(array).forEach(n-> System.out.printf("%d ", n));
        System.out.println();
        new BucketSort().sort(array);
        Arrays.stream(array).forEach(n-> System.out.printf("%d ", n));
        System.out.println();
    }

    public void sort(int[] array) {
        // 只是测试，设置桶大小为1,这样后面就不考虑插入数据扩容问题了,但是这样要求元素不能重复了，这样搞有点计数排序的味道了
        int bucketSize = 1;

        // 第一次遍历，找到最大值和最小值
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int n : array) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }

        // 计算桶的个数
        int bucketNums = (max - min) / bucketSize + 1;
        // 毕竟是示例，直接初始化每个桶固定大小，不要考虑扩容问题
        int[][] bucket = new int[bucketNums][bucketSize];

        // 将元素分布到每个桶里，第2次遍历了
        for (int n : array) {
            // 找到和最小值的差值，然后计算在哪个桶
            int diff = n - min;
            int bucketIndex = diff / bucketSize;
            // 因为每个桶大小 就是1，找到哪个桶就放入就行，不用考虑该放到这个桶的哪个位置了
            bucket[bucketIndex][0] = n;
        }

        // 对桶做一个排序，其实桶里只有一个元素的时候，不排也行
        int index = 0;
        for (int i = 0; i < bucketNums; i++) {
            Arrays.sort(bucket[i]);
            for (int j = 0; j < bucket[i].length; j++) {
                // 所以这里认为数据为0就是不存在，测试的时候，测试数据必须都得大于0
                if (bucket[i][j] != 0) {
                    // 将每个桶的元素copy到原来的数组里
                    array[index++] = bucket[i][j];
                }
            }
        }

    }
}

计数排序

排序过程

获取待排数据的最大值和最小值
根据最大值和最小值计算需要多少个桶，差值多少差不多就是多少个桶，一对一的比例
将数据相同的放到对应索引的桶，该桶的值就是当前小于等于该值的元素个数
把桶遍历一遍，输出到原数组就是排序后的数据

上面实现的桶排序的demo虽然不规范，但是前半部分还是比较像计数排序的实现。

场景

要求元素的数据范围不能太大，要不然桶太多了。
需要数据是非负整数，否则也要转换为非负整数

代码

下面的实现也只是一个demo，另外假定元素中没有负数的，仅作参考。

public class CountingSort {

    public static void main(String[] args) {
        int[] array = {5, 2, 8, 99, 4, 60, 77, 13, 55, 22};
        Arrays.stream(array).forEach(n -> System.out.printf("%d ", n));
        System.out.println();
        new CountingSort().sort(array);
        Arrays.stream(array).forEach(n -> System.out.printf("%d ", n));
        System.out.println();
    }

    public void sort(int[] array) {
        // 找到数组中的最大值
        int max = Integer.MIN_VALUE;
        for (int n : array) {
            max = Math.max(max, n);
        }

        // 计数数组，需要包含max的值，大小就是max+1
        int[] count = new int[max + 1];
        // java默认初始化每个元素都是0

        // 计算每个索引对应的值个数
        for (int i = 0; i < array.length; i++) {
            count[array[i]]++;
        }
        // 计算小于等于当前值的个数
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }

        // 将数据排序写入到一个临时数组
        int[] tmp = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            // 当前值
            int curValue = array[i];
            // 小于等于当前值的数量
            int countValue = count[curValue];
            // 该值减1对应的就是排序后的索引位值
            int index = countValue - 1;
            tmp[index] = array[i];
            // 当前值的数量少了一个
            count[curValue]--;
        }

        //将临时数组copy到原数组
        System.arraycopy(tmp, 0, array, 0, array.length);
    }
}

基数排序

排序过程

将数据的每一位采用稳定算法分别进行排序

场景

对数据有要求，要求数据能分割成单独的位。

代码

代码示例，用来理解用的，仅作参考。

public class BasicSort {

    public static void main(String[] args) {
        int[] array = {5, 2777, 833, 99666, 432, 60, 77, 16663, 55, 22, 833};
        Arrays.stream(array).forEach(n -> System.out.printf("%d ", n));
        System.out.println();
        new BasicSort().sort(array);
        Arrays.stream(array).forEach(n -> System.out.printf("%d ", n));
        System.out.println();
    }

    public void sort(int[] array) {
        // 先找到最大的那一位数
        int max = Integer.MIN_VALUE;
        for (int n : array) {
            max = Math.max(max, n);
        }

        // 将数据拆分成对应的位，比如最大的数max为9999，可以拆分为4位，其它数据最多也只拆分成4位，不足了补上
        // 计算下多少位吧
        int bits = 1;
        while ((max /= 10) > 0)
            bits++;

        // 将每个数拆成对应的位，如[9,9,9,9],[0,7,9,6],[0,0,1,6]...
        int[][] matrix = new int[array.length][bits];
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int col = bits - 1;
            while (true) {
                int mod = tmp % 10;
                matrix[i][col--] = mod;
                if ((tmp /= 10) == 0) {
                    break;
                }
            }
        }
//        Arrays.stream(matrix).forEach(x -> {
//            Arrays.stream(x).forEach(xx -> System.out.printf("%d ", xx));
//            System.out.println();
//        });

        // 从低位开始，对每一位比较来排序
        for (int c = bits - 1; c >= 0; c--) {
            // 需要一种稳定排序算法，对每一位比较来排序，这里用插入排序试一下吧
            for (int i = 1; i < array.length; i++) {
                for (int j = i; j > 0; j--) {
                    if (matrix[j][c] < matrix[j - 1][c]) {
                        // 把matrix中对应的元素交换了
                        int[] tmp = matrix[j];
                        matrix[j] = matrix[j - 1];
                        matrix[j - 1] = tmp;

                        // 把索引对应的array中的元素也要交换了
                        int arr = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = arr;
                    }
                }
            }

        }
    }
}

这篇关于常用排序算法及java示例的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

常用排序算法及java示例

排序算法

冒泡排序

排序过程

特点

代码

优化点

插入排序

排序过程

特点

代码

优化点

选择排序

排序过程

特点

代码

归并排序

排序过程

特点

代码

快速排序

排序过程

特点

代码

桶排序

排序过程

场景

代码

计数排序

排序过程

场景

代码

基数排序

排序过程

场景

代码

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯