常见的排序算法有哪些

本篇内容介绍了“常见的排序算法有哪些”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

冒泡排序

最常见的排序算法之一，每次比较相邻的两个元素，如果需要的话则交换位置。

看下面的动图一目了然。

代码实现：

    public static int[] sort(int[] arr){
        if (arr.length < 2){
            return arr;
        }
        //定义一个标志位，主要考虑到已经排好序的数组，避免不必要的计算
        boolean flag;
        for(int i=1;i<arr.length;i++){
            flag = true;
            for(int j=0;j<arr.length-i;j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if (flag){
                break;
            }
        }
        return arr;
    }

性能分析：

• 时间复杂度：O(n2)

• 空间复杂度：O(1)

• 算法稳定性：元素相等不会交换，是稳定的排序算法

选择排序

选择排序，每次循环需要找出数组中最小的元素，放在数组的最前面。

动画：

代码实现：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
        return arr;
    }

性能分析：

• 时间复杂度：O(n2)

• 空间复杂度：O(1)

插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

动画：

代码实现：

    public static int[] sort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            for (; j > 0; j--) {
                if (temp < arr[j - 1]) {
                    //符合条件往后挪
                    arr[j] = arr[j - 1];
                } else {
                    //此处break不能省略，用来停止 j 的自减
                    break;
                }
            }
            arr[j] = temp;
        }
        return arr;
    }

上面这种写法容易直观也容易理解；如果你能理解上面的写法，那么可以进一步把if判断表达式进行提取：

    public static int[] sort1(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            for (; j > 0 && temp < arr[j - 1]; j--) {
                //符合条件往后挪
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
        return arr;
    }

“常见的排序算法有哪些”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！