常见排序算法

admin管理员组

文章数量:1487745

常见排序算法

冒泡排序

相邻的数据两两比较，小的放前面，大的放后面，当经过一轮排序后最大值就在最右边，之后在剩余数据中重复以上操作，找到次大值，依次类推，最终将数据由小到大依次排列

以下是具体代码实现：

代码语言：javascript代码运行次数：0运行复制

public class bubbleDemo {
    public static void main(String[] args) {
        //定义一个一维数组
        int arr[] = {1,2,5,3,4};
        //外循环表示循环的轮次
        for (int i = 0; i < arr.length - 1; 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;
                }
            }
        }
        //输出排好顺序的数字
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

运行结果如下：

需要注意的是，第一层循环中 i 应该是小于 arr.length - 1 的，否则数组会越界 冒泡排序的优缺点 优点：简单易懂，实现方便，稳定。 缺点：时间复杂度为O(n^2)，对大规模数据的处理效率低。

选择排序

从0索引开始，用每个索引的元素和后面的元素进行比较，小的放前面，大的放后面，例如 0 索引元素和后面的所有元素依次比较，接下来用 1 索引元素和后面元素比较，以此类推。

代码实现：

代码语言：javascript代码运行次数：0运行复制

public class selectDemo {
    public static void main(String[] args) {
        //定义一个一维数组
        int [] arr = {5,1,2,4,3};
        //外循环表示循环的轮次
        for (int i = 0; i < arr.length - 1; i++) {
            //内循环表示每轮循环的次数
            for (int j = i + 1; j < arr.length; j++) {
                //如果前一个元素大于下一个元素，交换顺序
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        //输出排好的数
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

运行结果如下：

代码中，外层循环表示这一轮循环中用 第 i 索引的元素和后面的元素比较，内层循环表示 i 和 i 后面的元素进行比较交换 选择排序优缺点 优点： 1.简单直观：选择排序同样简单易懂，容易实现。 2.不占用额外空间：选择排序只需要常数级的额外空间。 缺点： 1.效率较低：与冒泡排序一样，选择排序的时间复杂度也是 O(n^2)。 2.不稳定：选择排序是一种不稳定的排序算法，可能改变相同元素的相对位置。

插入排序

将 0 索引的元素到 n 索引的元素 看作是有顺序的，其余 n + 1 到最后一个 元素看作是无序的，遍历无序数组，将遍历到的数组插入到有序序列中适当位置，如果是相同元素，就排到后面

代码实现：

代码语言：javascript代码运行次数：0运行复制

public class insertDemo {
    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 1, 4, 5, 9, 6, 7};
        //找出 n （前 n 个元素是有序的），默认按照从小到大的顺序
        int startIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            //当此元素大于后面的元素时，前 i 个元素就是有序的
            if (arr[i] > arr[i + 1]) {
                startIndex = i + 1;
                break;
            }
        }
        //无序元素从 i + 1 开始到最后，遍历无序元素
        for (int i = startIndex; i < arr.length; i++) {
            //由于下面的操作会不断修改 i 的值，所以用 j 来记录 i
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                //交换位置
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                //表示下一次循环和 startIndex 前面索引的元素进行判断
                j--;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

运行结果：

插入排序的优缺点 优点： 1.稳定：插入排序是稳定的，相同元素的相对位置在排序前后不会改变。 2.对于小规模数据较为高效：在小规模数据或基本有序的数据集上，插入排序的性能较好。 缺点： 1.效率较低：对于大规模数据集，插入排序的性能也较差，时间复杂度为 O(n^2)。 2.对逆序数据集的处理效果较差：如果数据集是逆序的，插入排序的性能会明显下降。

快速排序

首先把 0 索引的元素作为基准数 ，确定基准数在数组中正确的位置 ，此时，比基准数小的全在左边，比基准数大的全在右边,之后通过递归调用，分别将归位后的基准数两边的数字再次执行以上步骤，以此类推最后实现排序的效果

以下是具体的代码实现：

代码语言：javascript代码运行次数：0运行复制

public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /* 定义方法，确定基准数在数组中正确的位置
       i : 表示要排数组的起始索引
       j : 表示要排数组的结束索引
    * */
    public static void quickSort(int[] arr, int i, int j) {
        int start = i;
        int end = j;
        //递归出口
        if (end < start) {
            return;
        }
        //定义基准数
        int baseNumber = arr[i];
        while (start != end) {
            //通过end从后往前找出比基准数小的数字
            while (true) {
                if (end <= start || arr[end] < baseNumber) {
                    break;
                }
                end--;
            }
            //通过start从前往后找出比基准数大的数字
            while (true) {
                if (end <= start || arr[start] > baseNumber) {
                    break;
                }
                start++;
            }
            //将找到的 end指向的数字 和 start 指向的数字交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        /*当start 和 end 指向同一个位置时，将基准数和当前start指向的元素交换位置
         * 此时，基准数左边都是小于基准数的，右边都是大于基准数的*/
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //递归调用，对start左边的数字进行以上步骤
        quickSort(arr, 0, start - 1);
        //对start右边的数字进行递归调用
        quickSort(arr, start + 1, j);
    }
}

运行结果：

需要注意的是 将 end 遍历的数和 start 遍历的数交换时 一定要先遍历 end 再遍历 start 否则在最后基准数归位时，可能会把比基准数大的数字交换到前面 快速排序的优缺点 优点： 1.高效：在平均情况下，快速排序是最快的排序算法之一，时间复杂度为 O(n log n)。 2.原地排序：快速排序通常是原地排序，不需要额外的存储空间。 缺点： 1.不稳定：快速排序是一种不稳定的排序算法，可能改变相同元素的相对位置。 2.对于小规模数据性能较差：在小规模数据集上，快速排序的性能可能不如插入排序好。 3.对于基本有序数据集的处理效果不佳：在基本有序的数据集上，快速排序的性能可能会下降。 4.较难理解，代码写起来比较多

总结

以上对这四种排序算法进行了简单的介绍，无论是哪种排序，都有它自身的特点，使用时应结合实际情况 ，希望本次分享对大家有帮助 。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除前往查看排序算法数据数组索引排序

本文标签： 常见排序算法