当前位置 博文首页 > 0102的博客：数据结构与算法--经典10大排序算法（动图演示）【建

最大化 缩小

    0102的博客：数据结构与算法--经典10大排序算法（动图演示）【建

    作者：[db:作者] 时间：2021-09-03 12:18

    十大经典排序算法总结（动图演示）

    算法分类
    • 十大常见排序算法可分为两大类：
      • 比较排序算法：通过比较来决定元素的位置，由于时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
      • 非比较类型排序：不通过比较来决定元素的相对次序，他可以突破基于比较排序的时间下限，以线性时间运行，因此也称为线性时间非比较类排序
        在这里插入图片描述
    相关概念
    • 稳定排序：如果原数据中a在b之前，而且a=b，排序后a任然在b之前
    • 不稳定排序：如果原数据中a在b之前，而且a=b，排序后a在b之后
    • 时间复杂度：对排序数据的总的操作次数，反映当n变化时候，操作次数呈现出什么规律
    • 空间复杂度：指算法在计算机内执行时所需要的存储空间的度量，他也是数据规模n的函数。

    冒泡排序

    • 冒泡排序是一种简单的排序算法，重复遍历需要排序的数列，一次比较两个元素，如果他们顺序错误就把他们交换过来。持续遍历交换直到排序完成。
    算法分析
    • 比较相邻元素，如果前一个比后一个大，就交换他们
    • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该就变成了最大值
    • 针对所有元素重复以上步骤，除了最后一个
    • 重复1~3步骤直到完成排序
    动图展示

    在这里插入图片描述

    代码实现：
    public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大排序冒泡排序
     * */
    public static int[] bubbleSort(int[] arrayData){
        if(null == arrayData || arrayData.length <= 1){
            return arrayData;
        }
         for (int i = 0; i < arrayData.length; i++) {
            for (int j = 0; j < arrayData.length - 1; j++) {
                if(arrayData[j] > arrayData[i]){
                    int temp = arrayData[j];
                    arrayData[j] = arrayData[i];
                    arrayData[i] = temp;
                }
            }
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = bubbleSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[i]);
        }
    }
}

    选择排序

    • 选择排序（selection sort）是一种简单的比较容易理解的算法，工作原理：在未排序的数列中找到最小的一个，将他的位置所在数据与数列首位交换，接着从生下未排序的元素中继续找最小的元素和第二个交换，直到数列末尾。
    算法分析
    • n个数据的数列排序经过n-1次查找可以完成排序
    • 第i（0 <= i < n）次排序，默认数据第i个数据是最小的数据，从第i个数据开始遍历数列
    • 如果发现有比第i个数据更小的数据 j，记录位置 j，将最小的数据更换成第j个，持续遍历查找到 第i个数据后最小的数据 j
    • 将数列中第j个数据与第 i个数据进行交换
    • 同样，的步骤对 第 i+1 个数据进行处理，直到第n-1 个数据。
    动图演示

    在这里插入图片描述

    代码实现
    public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大选择排序
     * */
    public static int[] selectionSort(int[] arrayData){
        if(null == arrayData || arrayData.length <=1){
            return arrayData;
        }
        for (int i = 0; i < arrayData.length; i++) {
            int last = arrayData[i];
            int position = i;
            for (int j = i+1; j < arrayData.length; j++) {
                if(last > arrayData[j]){
                    last = arrayData[j];
                    position = j;
                }
            }
            int temp = arrayData[i];
            arrayData[i] = arrayData[position];
            arrayData[position] = temp;
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = selectionSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[i]);
        }
    }
}
    特点
    • 选择排序是最稳定的排序算法之一，因为无论什么数据进去时间复杂度都是O(n^2)。所以用它的时候数据规模越小越好。唯一的好处是不额外占用内存，空间复杂度O(1)，理论上选择排序可能也是凭虚最容易理解的排序算法。

    插入排序

    • 插入排序算法工作原理是通过构建有序序列，对于未排序的数据，在一家排序序列中从后向前扫描，找到相应位置插入。也可以逐步移动到对应位置
    算法分析
    • 从第一个元素开始，此元素我们看成已经有序的，我们认为第一二个数据已经有序
    • 取下一个元素，此处是第三元素，和之前有序列中的数据从后先前比较
    • 如果已排序的改元素大于新元素，将这个元素移动到下一个位置
    • 重复上这个步骤，直到找到一家排序的元素小于或者等于新元素的位置
    • 建新元素插入到该位置的后面的空位上（上一步的数据交换已经完成这部操作）
    • 重复以上2~5 步骤
    动图演示

    在这里插入图片描述

    代码实现
    public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20];
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            arrayData[i] = random.nextInt(1000);
        }
        return arrayData;
    }

    /**
     * 时间复杂度 O(n^2) 空间复杂度O(1)
     * 从小到大插入排序
     * */
    public static int[] insertionSort(int[] arrayData){
        if(null == arrayData || arrayData.length <= 1){
            return arrayData;
        }
         for (int i = 1; i < arrayData.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arrayData[j-1] > arrayData[j]){
                    int temp = arrayData[j-1];
                    arrayData[j-1] = arrayData[j];
                    arrayData[j] = temp;
                }
            }
        }
        return arrayData;
    }

    public static void main(String[] args) {
        int[] arrayData = insertionSort(getArrayData());
        for (int i = 0; i < arrayData.length; i++) {
            System.out.println(arrayData[i]);
        }
    }
}

    希尔排序

    • 1959年shell发明的，第一个突破O(n^2)的一个排序算法，是简单插入排序的改进版本。他原插入排序不同在于，会分组进行比较，并且优先比较距离较远的元素。希尔排序又称为缩小增量排序。
    算法分析
    • 先将整个待排序的记录序列分割成若干子序列，并分别对子序列进行直接插入排序，具体分析如下
    • 选择一个增量规则，将整个序列分成t1,t2，t3…tk，其中ti > tj，tk=1.
    • 按照增量个数k，对序列进行k次遍历排序
    • 每次排序，更具对应的增量ti，将待排序的序列分隔成若干个长度的m的子序列
    • 分别对每个子序列进行直接插入排序，仅仅存在增量是1 的时候，整个序列作为一个整体子序列来处理，表长度就等于整个序列长度
    • EX：此处比较绕，举个案例，长度为10的数列
      • 分组方法每次对半分组，第一次10/2 = 5 组，分别为：（0，5），（1，6），（2，7），（3，8），（4，9）
      • 接着第二次在对半分5/2 = 2组，分别为：（0，2，4，6，8），（1，3，5，7，9）
      • 第三次继续对半分2/2=1组：0，1，2，3，4，5，6，7，8，9
      • 每一次分组都将对各个组进行选择插入排序，得到最终结果
    动图说明

    在这里插入图片描述

    代码实现
    public class BubbleSort {
    public static int[] getArrayData(){
        int[] arrayData = new int[20
    上一篇：yuchen的博客：十大经典排序算法（动图演示）
    下一篇：没有了