注册 登录
中国红客联盟 返回首页

KinseyD的个人空间 http://www.cnhonkerarmy.com/?1201031 [收藏] [复制] [分享] [RSS]

日志

动画图解:十大经典排序算法动画与解析,看我就够了!(配代码完全版)(一)

已有 56 次阅读2019-11-21 10:01 |个人分类:算法学习| 算法, 排序

排序算法是《数据结构与算法》中最基本的算法之一。
排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括:
十大经典排序算法动画与解析,看我就够了!(配代码完全版)

时间复杂度与空间复杂度

关于时间复杂度:
    平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
    线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;
    O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序
    线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性:

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。
    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

1. 冒泡排序

1.1 算法步骤
    比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    针对所有的元素重复以上的步骤,除了最后一个。
    持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

1.2 动画演示
十大经典排序算法动画与解析,看我就够了!(配代码完全版)
1.3 参考代码
     1// Java 代码实现
     2public class BubbleSort implements IArraySort {
     3
     4    @Override
     5    public int[] sort(int[] sourceArray) throws Exception {
     6        // 对 arr 进行拷贝,不改变参数内容
     7        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
     8
     9        for (int i = 1; i < arr.length; i++) {
    10            // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
    11            boolean flag = true;
    12
    13            for (int j = 0; j < arr.length - i; j++) {
    14                if (arr[j] > arr[j + 1]) {
    15                    int tmp = arr[j];
    16                    arr[j] = arr[j + 1];
    17                    arr[j + 1] = tmp;
    18
    19                    flag = false;
    20                }
    21            }
    22
    23            if (flag) {
    24                break;
    25            }
    26        }
    27        return arr;
    28    }
    29}
2. 选择排序

2.1 算法步骤

  • 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

  • 重复第二步,直到所有元素均排序完毕。

2.2 动画演示

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

2.3 参考代码

     1//Java 代码实现
     2public class SelectionSort implements IArraySort {
     3
     4    @Override
     5    public int[] sort(int[] sourceArray) throws Exception {
     6        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
     7
     8        // 总共要经过 N-1 轮比较
     9        for (int i = 0; i < arr.length - 1; i++) {
    10            int min = i;
    11
    12            // 每轮需要比较的次数 N-i
    13            for (int j = i + 1; j < arr.length; j++) {
    14                if (arr[j] < arr[min]) {
    15                    // 记录目前能找到的最小值元素的下标
    16                    min = j;
    17                }
    18            }
    19
    20            // 将找到的最小值和i位置所在的值进行交换
    21            if (i != min) {
    22                int tmp = arr[i];
    23                arr[i] = arr[min];
    24                arr[min] = tmp;
    25            }
    26
    27        }
    28        return arr;
    29    }
    30}


————————————————
版权声明:本文为CSDN博主「程序员吴师兄」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

红盟社区--中国红客联盟 

Processed in 0.069627 second(s), 8 queries.

站点统计| 举报| Archiver| 手机版| 黑屋 |   

Powered by HUC © 2001-2017 Comsenz Inc.

手机扫我进入移动触屏客户端

关注我们可获取更多热点资讯

Honor accompaniments. theme macfee

返回顶部