常见的七种排序算法解析 -买球官网平台

3顶
0踩

常见的七种排序算法解析

2017-10-26 09:51 by 副主编 jihong10102006 评论(0) 有10999人浏览
引用
来源:

选择排序

实现原理

首先从未排序序列中找到最小的元素,放置到排序序列的起始位置,然后从剩余的未排序序列中继续寻找最小元素,放置到已排序序列的末尾。所以称之为选择排序。
代码实现
    public static int[] selectionsort(int[] arr){
        if (null == arr || arr.length == 0){
            return null;
        }
        int length = arr.length;
        for (int i = 0; i < length - 1; i  ) {
            int min = i;
            for (int j = i   1; j < length; j  ) {
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }

案例分析

时间复杂度与空间复杂度

每次要找一遍最小值,最坏情况下找n次,这样的过程要执行n次,所以时间复杂度还是o(n^2)。空间复杂度是o(1)。

快速排序

实现原理

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition)。
  • 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
代码实现
       
public static int partition(int[] array, int lo, int hi) {
            // 固定的切分方式
            int key = array[lo];
            while (lo < hi) {
                while (array[hi] >= key && hi > lo) {// 从后半部分向前扫描
                        hi--;
                }
                array[lo] = array[hi];
                while (array[lo] <= key && hi > lo) {// 从前半部分向后扫描
                    lo  ;
                }
                array[hi] = array[lo];
            }
            array[hi] = key;
            return hi;
        }
        public static int[] sort(int[] array, int lo, int hi) {
            if (lo >= hi) {
                return array;
            }
            int index = partition(array, lo, hi);
            sort(array, lo, index - 1);
            sort(array, index   1, hi);
            return array;
        }

案例分析

时间复杂度与空间复杂度

快速排序也是一个不稳定排序,平均时间复杂度是o(nlogn)。空间复杂度是o(logn)。

冒泡排序

实现原理

依次比较相邻的两个元素,如果第一个元素大于第二个元素就交换它们的位置。这样比较一轮之后,最大的元素就会跑到队尾。然后对未排序的序列重复这个过程,最终转换成有序序列。

代码实现
   
public static int[] bubblesort(int[] arr){
        for (int i = 0; i < arr.length - 1; i  ) {
            for (int j = 0; j < arr.length - i -1; j  ) {
                if (arr[j] > arr[j   1]){
                    arr[j] = arr[j]   arr[j   1];
                    arr[j   1] = arr[j] - arr[j   1];
                    arr[j] = arr[j] - arr[j   1];
                }
            }
        }
        return arr;
    }

案例分析

以数组 arr = [3 4 2 8 0] 为例说明,加粗的数字表示每次循环要比较的两个数字:

第一次外循环

( 3 4 2 8 0 ) → ( 3 4 2 8 0 ), 4 > 3 位置不变 ( 3 4 2 8 0 ) → (3 2 4 8 0 ), 4 > 2 交换位置 ( 3 2 4 8 0 ) → ( 3 2 4 8 0 ), 8 > 4 位置不变 ( 3 2 4 8 0 ) → ( 3 2 4 0 8 ), 8 > 0 交换位置

第二次外循环(除开最后一个元素8,对剩余的序列)

( 3 2 4 0 8 ) → ( 2 3 4 0 8 ), 3 > 2 交换位置 ( 2 3 4 0 8 ) → ( 2 3 4 0 8 ), 4 > 3 位置不变 ( 2 3 4 0 8 ) → ( 2 3 0 4 8 ), 4 > 0 交换位置

第三次外循环(除开已经排序好的最后两个元素,对剩余的循环,直到剩余的序列为 1)

( 2 3 0 4 8 ) → ( 2 3 0 4 8 ),3 > 2 位置不变 (2 3 0 4 8 ) → (2 0 3 4 8 ),3 > 0 交换位置

第四次外循环(最后一次)

( 2 0 3 4 8 ) → (0 2 3 4 8 ),2 > 0 交换位置

时间复杂度与空间复杂度

由于我们要重复执行n次冒泡,每次冒泡要执行n次比较(实际是1到n的等差数列,也就是(a1 an) * n / 2),也就是 o(n^2)。 空间复杂度是o(1)。

插入排序

实现原理

  • 认为第一个元素是排好序的,从第二个开始遍历。
  • 拿出当前元素的值,从排好序的序列中从后往前找。
  • 如果序列中的元素比当前元素大,就把它后移。直到找到一个小的。
  • 把当前元素放在这个小的后面(后面的比当前大,它已经被后移了)。
代码实现
   
public static int[] insertionsort(int[] arr){
        for (int i = 1; i < arr.length; i  ) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]){
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        return arr;
    }

原理图解

案例1


案例2

时间复杂度与空间复杂度

因为要选择n次,而且插入时最坏要比较n次,所以时间复杂度同样是o(n^2)。空间复杂度是o(1)。

希尔排序

实现原理

  • 先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
  • 然后取 d2(d2 < d1)
  • 重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。
代码实现
   
public static int[] shellsort(int[] arr){
        for (int gap = arr.length/2; gap > 0 ; gap/=2) {
            for (int i = gap; i < arr.length; i  ) {
                int j = i;
                while (j-gap>=0 && arr[j] < arr[j-gap]){
                    int temp = arr[j];
                    arr[j] = arr[j-gap];
                    arr[j-gap] = temp;
                    j -= gap;
                }
            }
        }
        return arr;
    }

案例分析

假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10],首先取 d1 = 4,将数组分为 4 组,如下图中相同颜色代表一组:

然后分别对 4 个小组进行插入排序,排序后的结果为:

然后,取 d2 = 2,将原数组分为 2 小组,如下图:

然后分别对 2 个小组进行插入排序,排序后的结果为:

最后,取 d3 = 1,进行插入排序后得到最终结果:

时间复杂度与空间复杂度

希尔排序的时间复杂度受步长的影响,平均时间复杂度是o(n log2 n),空间复杂度是o(1)。

归并排序

实现原理

  • 把 n 个记录看成 n 个长度为 l 的有序子表
  • 进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表
  • 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
总而言之,归并排序就是使用递归,先分解数组为子数组,再合并数组。

代码实现
  
 public static int[] mergesort(int[] arr){
        int[] temp =new int[arr.length];
        internalmergesort(arr, temp, 0, arr.length-1);
        return temp;
    }
    private static void internalmergesort(int[] a, int[] b, int left, int right){
        //当left==right的时,已经不需要再划分了
        if (left

案例分析

案例1

以数组 array = [4 2 8 3 5 1 7 6] 为例,首先将数组分为长度为 2 的子数组,并使每个子数组有序:

[4 2] [8 3] [5 1] [7 6] ↓
[2 4] [3 8] [1 5] [6 7]

然后再两两合并:

[2 4 3 8] [1 5 6 7] ↓
[2 3 4 8] [1 5 6 7]

最后将两个子数组合并:

[2 3 4 8 1 5 6 7] ↓
[1 2 3 4 5 6 7 8]

案例2

时间复杂度与空间复杂度

在合并数组过程中,实际的操作是当前两个子数组的长度,即2m。又因为打散数组是二分的,最终循环执行数是logn。所以这个算法最终时间复杂度是o(nlogn),空间复杂度是o(1)。

堆排序

实现原理

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:
  • 最大堆调整(max-heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(build-max-heap):将堆所有数据重新排序,使其成为最大堆
  • 堆排序(heap-sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算
  • parent(i) = floor((i-1)/2),i 的父节点下标
  • left(i) = 2i 1,i 的左子节点下标
  • right(i) = 2(i 1),i 的右子节点下标
代码实现
   
/**
     * 堆排序
     */
    public static int[] heapsort(int[] arr) {
        // 将待排序的序列构建成一个大顶堆
        for (int i = arr.length / 2; i >= 0; i--){
            heapadjust(arr, i, arr.length);
        }
        // 逐步将每个最大值的根节点与末尾元素交换,并且再调整二叉树,使其成为大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapadjust(arr, 0, i); // 交换之后,需要重新检查堆是否符合大顶堆,不符合则要调整
        }
        return arr;
    }
    /**
     * 构建堆的过程
     * @param arr 需要排序的数组
     * @param i 需要构建堆的根节点的序号
     * @param n 数组的长度
     */
    private static void heapadjust(int[] arr, int i, int n) {
        int child;
        int father;
        for (father = arr[i]; leftchild(i) < n; i = child) {
            child = leftchild(i);
            // 如果左子树小于右子树,则需要比较右子树和父节点
            if (child != n - 1 && arr[child] < arr[child   1]) {
                child  ; // 序号增1,指向右子树
            }
            // 如果父节点小于孩子结点,则需要交换
            if (father < arr[child]) {
                arr[i] = arr[child];
            } else {
                break; // 大顶堆结构未被破坏,不需要调整
            }
        }
        arr[i] = father;
    }
    // 获取到左孩子结点
    private static int leftchild(int i) {
        return 2 * i   1;
    }
    // 交换元素位置
    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

案例分析

时间复杂度与空间复杂度

堆执行一次调整需要o(logn)的时间,在排序过程中需要遍历所有元素执行堆调整,所以最终时间复杂度是o(nlogn)。空间复杂度是o(1)。
  • 大小: 306.8 kb
  • 大小: 279.6 kb
  • 大小: 311 kb
  • 大小: 89.8 kb
  • 大小: 7.6 kb
  • 大小: 11.1 kb
  • 大小: 9.4 kb
  • 大小: 11.4 kb
  • 大小: 15.6 kb
  • 大小: 97.2 kb
  • 大小: 22.6 kb
  • 大小: 300.4 kb
来自:
3
0
评论 共 0 条 请登录后发表评论

发表评论

您还没有登录,请您登录后再发表评论

相关推荐

  • 详细讲述了8中常见算法的原理及思想,并用java进行了实现,代码中有详细的注释,解释了算法的实现逻辑和一些小技巧。

  • 1、安装mono遇到的错误: /usr/local/src/mono /eglib/src/gunicode.c : undefined reference to `locale_charset' 解决:http://www.cnblogs.com/shiningrise/archive/2012/11/23/2785120.html run ./configure

  • 常见10大算法,从原理,动图解析到代码实现,逐步分析,让你轻松入门算法

  • 排序算法的稳定性: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,如果排序以后,保证这些记录的相对次序保持不变,即在原序列中,a[i]=a[j],且 a[i] 在 a[j] 之前,排序后保证 a[i] 仍在 a[j] ...

  • 这里写自定义目录标题排序算法复杂度对比冒泡排序实现合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...

  • 直接插入排序 核心思想就是:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,则交换,直到全部元素都比较过。 因此,从上面的描述中我们可以发现,直接插入排序可以用两个循环...

  • 排序算法作为数据结构中重要的部分,是必须要掌握的知识之一。 目录 前言 一、插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 二、交换类排序 1.冒泡排序(相邻比序法) 2.快速排序 三、选择类...

  • 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求能在内外村之间移动数据的排序首先我们先来了解一下如何判断一个排序算法的性能好坏?依据是什么?一般而言有三个依据:稳定性、时间复杂度和空间...

  • 人工智能,零基础入门!... 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序...

  • 本文将介绍常见的排序算法中的“快速排序”。 基本思想 快速排序(quicksort)是对冒泡排序的一种改进。快速排序由c. a. r. hoare在1962年提出。它的基本思想是: 从要排序的数据中取一个数为“基准数”。 ...

  • 并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析4个方面进行了详细的解析,可以帮助c语言初学者轻松理解几种常用的排序算法。关键词:c语言;排序;算法思想;数组中图分类号:tp301.6 ...

  • 10种常见排序算法的原理,包括冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序、计数排序、桶排序、基数排序。并且每种排序都提供了java代码的实现案例。

  • 本篇文章总结了数据结构中常见的七大排序,让大家一篇文章能够收集到七大排序算法。包括:直接插入排序,冒泡排序,选择排序,希尔排序,堆排序,快速排序,归并排序。 目录 1. 什么是排序 1.1常见的排序算法 ...

  • 当然,这篇文章会为大家讲解众多排序算法中最经典的部分,也是大家最熟悉的几种算法,包括冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、桶排序、希尔排序、堆排序。同时也会利用一些手...

  • java面试题之:java算法一、二分查找 一、二分查找   二分查找又叫折半查找,要求待查找的序列有序。每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果...

  • 万字长文加n多图片喂你七大排序的知识点, 让你用脚都能写出排序算法

  • 时间限制是1s,所以数量级最大为1000万级别,因为题目中的n取值范围不大于100,所以即使采用o(n2n^2n2)的算法,如冒泡排序,时间复杂度最多也只是一万,符合要求。 内存限制32m,因为冒泡排序空间复杂度为o(n),所以...

  • 十大排序算法汇总 比较和非比较的区别 常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的...

  • 十大经典排序算法简介0、算法概述0.1 算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破o(nlogn),因此也称为非线性时间比...

  • 十大经典排序算法简介0、算法概述0.1 算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破o(nlogn),因此也称为非线性时间比...

global site tag (gtag.js) - google analytics