devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

各排序算法介绍、图解说明、代码详解、复杂度分析、选择_执行空间与辅助空间的区别

作者：weixin_40725706 | 2024-08-15 02:07:34

赞

踩

执行空间与辅助空间的区别

各排序算法介绍、图解说明、代码详解、复杂度分析、选择

一、排序的分类：

  1. 内部排序:
    指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。
  2. 外部排序法：
    数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。

常见的排序算法分类：
在这里插入图片描述
我们这里主要介绍内排序的多种方法。

二、内排序算法性能主要影响因素

对于内排序而言，排序算法的性能主要受3个方面影响：

1、时间性能

排序算法的时间开销是衡量它好坏的最重要的标志。而内排序主要进行两种操作：比较和移动。所以我们应该尽可能少的关键字比较次数和尽可能少的记录移动次数。

2、辅助空间（空间复杂度）

辅助空间是除了存放排序所占用的存储空间外，执行算法所需要的其他存储空间。

3、算法的复杂性

这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然，算法过于复杂也会影响排序的性能。

三、各排序算法详解

1、冒泡排序

1）简介

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

2)初级冒泡排序

a、图解

在这里插入图片描述
（摘自《大话数据结构》）

b、代码实现
package cn.jc.demo1;

import java.util.Arrays;

public class BubbleSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr1 = bubbleSort1(arr);
    System.out.println(Arrays.toString(arr1));


  }
  public static int[] bubbleSort1 (int[] arr){
    int temp=0;
    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]){
          temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        }
      }
    }
    return arr;
  }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
排序前
[9, 1, 5, 8, 3, 7, 4, 6, 2]
排序后
[1, 2, 3, 4, 5, 6, 7, 8, 9]


  • 1
  • 2
  • 3
  • 4
  • 5

这个严格意义上不算标准的冒泡排序，因为他不满足两两比较相邻记录，他更应该是最最简单的交换排序而已。

3）中阶冒泡排序

a、图解

在这里插入图片描述
（摘自《大话数据结构》）

b、代码实现

从后往前循环

public class BubbleSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr2 = bubbleSort1(arr);
    System.out.println(Arrays.toString(arr2));

  }
  public static int[] bubbleSort2(int[] arr){
    int temp=0;
    for (int i = 0; i <arr.length-1; i++) {
      for (int j = arr.length; j>=i; j--) {
        if(arr[j]>arr[j+1]){
          temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        }
      }

    }
    return arr;
  }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

输出一致

4）高阶冒泡排序

a、图解

当i=1时，交换了2和1，此时排序已经有序了，但是算法还是将i=2到9和每个循环中的j循环了一遍，我们可以设置医德标志flag判断元素是否进行过交换，如果没有交换了，就结束循环，减少不必要的比较。
在这里插入图片描述

（摘自《大话数据结构》）

b、代码实现
 public static int[] bubbleSort3(int[] arr){
    int temp=0;
    boolean flag=false;
    for (int i = 0; i <arr.length-1&&flag; i++) {
      for (int j = arr.length; j>=i; j--) {
        if(arr[j]>arr[j+1]){
          temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
          flag=true;//有交换则改为true
        }
      }
    if(!flag){//在这一趟中。一次交换都没有发生
      break;
    }else {
      flag=false;//重置flag，进行下一次判断
    }
    }
    return arr;
  }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

5）时间复杂度分析

最好情况下，即本身是有序的，那就是n-1次的比较，即O（n）

2、选择排序

1）简介

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值， 与 arr[0]交换，第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，第三次从 arr[2]~arr[n-1]中选取最小值，与arr[2] 交换，…，第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…, 第 n-1 次从arr[n-2]~arr[n-1]中选取最小值， 与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

即通过n-1次关键字的比较，从aar[i]到arr[n-1]中选出最小值，并和arr[i]交换。

2）图解

在这里插入图片描述

（摘自《大话数据结构》）

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class SelectSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr3 = selectSort(arr);
    System.out.println(Arrays.toString(arr3));

  }

  public static int[] selectSort(int[] arr){

    for (int i =0; i <arr.length-1; i++) {
      int minIndex=i;//记录aar[i]到arr[n-1]中的最小值的下标
      int min=arr[i];//记录aar[i]到arr[n-1]中的最小值
      for (int j = i+1; j <arr.length; j++) {
        if(min>arr[j]){//说明假定的最小值并非是最小
          min=arr[j];
          minIndex=j;
        }
      }
      if(minIndex!=i){//如果minIndex不是原本的i，说明最小的那个的下标应该是 minIndex，替换
        arr[minIndex]=arr[i];
        arr[i]=min;
      }
    }
    return arr;
  }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

4)时间复杂度分析

O（n^2）

3、直接插入排序法

1）简介

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

基本思想是：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有 序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

2）图解

在这里插入图片描述

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class InsertSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr3 = insertSort(arr);
    System.out.println(Arrays.toString(arr3));
  }

  public static int[] insertSort(int[] arr){

    for (int i =1; i <arr.length; i++) {
      int k=arr[i];//设置哨兵用于比较
      int j;
      for (j = i-1; j>=0&&arr[j]>k; j--) {
        arr[j+1]=arr[j];//记录后移，给a[i]腾位置
      }
      arr[j+1]=k;//插入到正确的位置
    }
    return arr;
  }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

4)时间复杂度分析

O（n^2），但比冒泡和简单选择排序性能要好些

4、希尔排序法

1）简介

我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是： {2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

希尔排序是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序的思想是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含 的关键词越来越多，当增量减至1 时，整个文件恰被分成一组，算法便终止

2）图解

在这里插入图片描述

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class ShellSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr3 = shellSort(arr);
    System.out.println(Arrays.toString(arr3));
  }

  public static int[] sshellSort(int[] arr) {
    int temp = 0;
    int count = 0;
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < arr.length; i++) {
        // 遍历各组中所有的元素(共 gap 组，每组有个元素), 步长 gap
        for (int j = i - gap; j >= 0; j -= gap) {
          // 如果当前元素大于加上步长后的那个元素，说明交换
          if (arr[j] > arr[j + gap]) {
            temp = arr[j];
            arr[j] = arr[j + gap];
            arr[j + gap] = temp;
          }
        }
      }
    }
    return arr;
  }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

4）时间复杂度分析

O（n^3/2）

5、快速排序

1）简介

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两
部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有
继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

2）图解

方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。
在这里插入图片描述
首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iw0eKzrj-1592983621613)(E:\User\markdown笔记\img\快排2)]
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：

6 1 2 5 9 3 4 7 10 8
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vbQ1P7Ih-1592983621614)(E:\User\markdown笔记\img\快排3)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A6d43HNv-1592983621615)(E:\User\markdown笔记\img\快排4)]
到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：

3 1 2 5 4 6 9 7 10 8
在这里插入图片描述
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错，调整完毕之后的序列的顺序应该是：

2 1 3 5 4

OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下：

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下

1 2 3 4 5 6 7 8 9 10

到此，排序完全结束。我们可以发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
在这里插入图片描述
这是为什么呢？

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class QuickSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr3 = quickSort(arr,0,arr.length-1);
    System.out.println(Arrays.toString(arr3));
  }



  public static int[] quickSort(int[] arr,int low,int high) {
    //如果left等于right，即数组只有一个元素，直接返回
    if(low>=high) {
      return arr;
    }
    int i=low;
    int j=high;
    int key=arr[low];//取最左边的为基准点
    while (j>i){
      //因为基准点取的是最左边的，所以要先从找后面中比基准点小的数，
      while (arr[j]>=key&&j>i) {
        //如果比关键值大的，比较下一个，直到有比关键值小的
        j--;
      }
      //再找前面中比基准点小的数
      while (arr[i]<=key&&j>i){
        //如果比关键值小的，比较下一个，直到有比关键值大的
        i++;
      }
      if(i<j){//如果满足条件，则交换上面两个while找到的右边比关键值小的和左边比关键值大的两个数
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
      }
    }

    arr[low]=arr[i];
    arr[i]=key;
    //此时low=high
    quickSort(arr,low,j-1);//递归调用左半数组
    quickSort(arr,j+1,high);//递归调用左半数组
    return arr;
  }

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

4）时间复杂度分析

O（nlogn）

5）优化

可以优选基准值的位置，如果我们选取的基准点处于整个序列的中间位置，那么我们就可以将整个序列分成小数集合和大数集合。我们可以选取 三数取中，即取三个关键字先进行排序，将中间数作为基准点，一般是取左端、右端和中间三个数。

6、归并排序

1）简介

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer） 策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修 补"在一起，即分而治之)。

2）图解

在这里插入图片描述
在治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将 [4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
在这里插入图片描述

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class MergeSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] temp=new int[arr.length];
    int[] arr3 = mergeSort(arr,0,arr.length-1,temp);
    System.out.println(Arrays.toString(arr3));
  }


  //合并的方法

  /**
   *
   * @param arr 排序的原始数组
   * @param left 左边有序序列的初始索引
   * @param mid 中间索引
   * @param right 右边索引
   * @param temp 做中转的数组
   */
  public static void merge(int[] arr,int left,int mid,int right,int[] temp){
    int i = left; // 初始化 i, 左边有序序列的初始索引
    int j = mid + 1; //初始化 j, 右边有序序列的初始索引
    int t = 0; // 指向 temp 数组的当前索引

    //(一)
    //先把左右两边(有序)的数据按照规则填充到 temp 数组
    //直到左右两边的有序序列，有一边处理完毕为止
    while (i <= mid && j <= right) {//继续
      //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
      // 即将左边的当前元素，填充到 temp 数组
      //然后 t++, i++
      if (arr[i] <= arr[j]) {
        temp[t] = arr[i];
        t += 1;
        i += 1;
      } else { //反之,将右边有序序列的当前元素，填充到 temp 数组
        temp[t] = arr[j];
        t += 1;
        j += 1;
      }
      //以上if语句作用就是将arr[i]和arr[j]小的那个填充到temp数组，并右移被填充的那个序列索引
    }
    //(二)
    //把有剩余数据的一边的数据依次全部填充到 temp
    //因为子序经过前面的分处理，已是有序，再经过以上一的处理，剩余的数据已经都大于temp[t]，所以全部移过来
    while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp，如图二中的第五步
      temp[t] = arr[i];
      t += 1;
      i += 1;
    }
    while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
      temp[t] = arr[j];
      t += 1;
      j += 1;
    }
    //(三)
    //将 temp 数组的元素拷贝到arr
    //注意，并不是每次都拷贝所有（9个）
    t = 0;
    int tempLeft = left; //
    //第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
    // 最后一次 tempLeft = 0 right = 7
    while(tempLeft <= right) {
      arr[tempLeft] = temp[t];
      t += 1;
      tempLeft += 1;
    }
  }


  //分+合方法
  public static int[] mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
      int mid = (left + right) / 2; //中间索引
    //向左递归进行分解
      mergeSort(arr, left, mid, temp);
    //向右递归进行分解
      mergeSort(arr, mid + 1, right, temp);
    //全部分解后，合并
      merge(arr, left, mid, right, temp);
    }
    return arr;
  }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93

4）时间复杂度分析

时间复杂度：O(nlogn）空间复杂度：O(n+logn）

7、基数排序

1）简介

  • 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾
    名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
  • 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
  • 基数排序(Radix Sort)是桶排序的扩展
  • 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个
    位数分别比较。

它的基本思想是将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

2）图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3）代码实现

package cn.jc.demo1;

import java.util.Arrays;

public class RadixSort {
  public static void main(String[] args) {
    int arr[]={9,1,5,8,3,7,4,6,2};
    System.out.println("排序前");
    System.out.println(Arrays.toString(arr));

    System.out.println("排序后");
    int[] arr3 = radixSort(arr);
    System.out.println(Arrays.toString(arr3));
  }

  public static int[] radixSort(int[] arr) {
    //1. 得到数组中最大的数的位数
    int max = arr[0]; //假设第一数就是最大数 for(int i = 1; i < arr.length; i++) {
    for (int i = 1; i <arr.length; i++) {
      if (arr[i] > max) {
        max = arr[i];
      }
    }
    //得到最大数是几位数
    int maxLength = (max + "").length();

    //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
    //说明
    //1. 二维数组包含 10 个一维数组
    //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length
    //3. 很明确，基数排序是使用空间换时间的经典算法
    int[][] bucket = new int[10][arr.length];

    //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
    //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
    int[] bucketElementCounts = new int[10];

    //循环取出各个位数
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
      for (int j = 0; j < arr.length; j++) {
        //取出每个元素的对应位的值
        int digitOfElement = arr[j] / n % 10;
        //放入到对应的桶中
        bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
        bucketElementCounts[digitOfElement]++;
      }
      //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
      int index = 0;
      //遍历每一桶，并将桶中是数据，放入到原数组
      for (int k = 0; k < bucketElementCounts.length; k++) {
        //如果桶中，有数据，我们才放入到原数组
        if (bucketElementCounts[k] != 0) {
          //循环该桶即第k 个桶(即第 k 个一维数组), 放入
          for (int l = 0; l < bucketElementCounts[k]; l++) {
            //取出元素放入到 arr
            arr[index++] = bucket[k][l];
          }
        }
        //第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
        bucketElementCounts[k] = 0;
      }
      //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    }
    return arr;
  }

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

4)说明

  1. 基数排序是对传统桶排序的扩展，速度很快.
  2. 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。 3) 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些
    记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前， 则称这种排序算法是稳定的；否则称为不稳定的]
  3. 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

8、堆排序

1）简介

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复 杂度均为 O(nlogn)，它也是不稳定排序。
  2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有
    要求结点的左孩子的值和右孩子的值的大小关系。
  3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
  4. 大顶堆举例说明
    在这里插入图片描述

5）小顶堆举例说明
在这里插入图片描述
6) 一般升序采用大顶堆，降序采用小顶堆

2）基本思想

堆排序的基本思想是：

  1. 将待排序序列构造成一个大顶堆
  2. 此时，整个序列的最大值就是堆顶的根节点。
  3. 将其与末尾元素进行交换，此时末尾就为最大值。
  4. 然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序
    序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

3）图解

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

  1. .假设给定无序序列结构如下
    在这里插入图片描述

  2. .此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整。
    在这里插入图片描述

  3. .找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换。且这是8比9小。没有破坏结构，否则需要交换。
    在这里插入图片描述

  4. 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6。
    在这里插入图片描述

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

  1. .将堆顶元素 9 和末尾元素 4 进行交换
    在这里插入图片描述

  2. .重新调整结构，使其继续满足堆定义
    在这里插入图片描述

  3. .再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8.
    在这里插入图片描述

  4. 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
    在这里插入图片描述

再简单总结下堆排序的基本思路：
1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤， 直到整个序列有序。

4）代码实现

package com.atguigu.tree;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class HeapSort {

	public static void main(String[] args) {
		//要求将数组进行升序排序
		//int arr[] = {4, 6, 8, 5, 9};
		// 创建要给80000个的随机的数组
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		System.out.println("排序前");
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);
		
		heapSort(arr);
		
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的时间是=" + date2Str);
		//System.out.println("排序后=" + Arrays.toString(arr));
	}

	//编写一个堆排序的方法
	public static void heapSort(int arr[]) {
		int temp = 0;
		System.out.println("堆排序!!");
		
//		//分步完成
//		adjustHeap(arr, 1, arr.length);
//		System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
//		
//		adjustHeap(arr, 0, arr.length);
//		System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
		
		//完成我们最终代码
		//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
		for(int i = arr.length / 2 -1; i >=0; i--) {
			adjustHeap(arr, i, arr.length);
		}
		
		/*
		 * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
　　			3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
		 */
		for(int j = arr.length-1;j >0; j--) {
			//交换
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j); 
		}
		
		//System.out.println("数组=" + Arrays.toString(arr)); 
		
	}
	
	//将一个数组(二叉树), 调整成一个大顶堆
	/**
	 * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
	 * 举例  int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
	 * 如果我们再次调用  adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}
	 * @param arr 待调整的数组
	 * @param i 表示非叶子结点在数组中索引
	 * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
	 */
	public  static void adjustHeap(int arr[], int i, int lenght) {
		
		int temp = arr[i];//先取出当前元素的值，保存在临时变量
		//开始调整
		//说明
		//1. k = i * 2 + 1 k 是 i结点的左子结点
		for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
			if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值
				k++; // k 指向右子结点
			}
			if(arr[k] > temp) { //如果子结点大于父结点
				arr[i] = arr[k]; //把较大的值赋给当前结点
				i = k; //!!! i 指向 k,继续循环比较
			} else {
				break;//!
			}
		}
		//当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
		arr[i] = temp;//将temp值放到调整后的位置
	}
	
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

四、各排序算法比较

在这里插入图片描述

  1. 稳定：如果 a 原本在 b 前面，而 a=b，排序之后a 仍然在 b 的前面；

  2. 不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后a 可能会出现在 b 的后面；

  3. 内排序：所有排序操作都在内存中完成；

  4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

  5. 时间复杂度： 一个算法执行所耗费的时间。

  6. 空间复杂度：运行完一个程序所需内存的大小。 7) n: 数据规模

  7. k: “桶”的个数

  8. In-place: 不占用额外内存

  9. Out-place: 占用额外内存

五、排序算法的选择

本节参考自https://blog.csdn.net/iMatt/article/details/83781169

没有一种算法显然是“最佳”算法。这取决于一系列因素。

首先，能将数据放入主内存吗？如果你能，那么需要依赖外部排序算法。这些算法通常基于快速排序（quicksort）和归并排序（mergesort），【译注：如果不能，根据使用的数据集的大小和类型，使用专用数据库加载数据或利用Google的BigQuery等基于云的服务】。

其次，输入数据的分布是什么样的？如果它大多数都是有序的，那么像Timsort这样的东西可能是一个很好的选择，因为它的设计可以很好地处理排序数据。如果它几乎是随机的，那么Timsort可能不是一个好选择。

第三，排序什么类型的的元素？如果要对一般对象进行排序，那么几乎可以锁定比较排序。如果没有，也许可以使用非比较排序，如计算排序（counting sort）或基数排序（radix sort）。

第四，数据有多少模块？一些排序算法（quicksort，mergesort，MSD基数排序）非常好并行化，而其他排序算法（如heapsort）则不是好的选择。

第五，数据如何表示？如果它们存储在数组中，则快速排序或快速排序变体可能会因为引用的位置而表现良好，而mergesort可能由于需要额外的内存而变慢。但是，如果它们在链表中，则来自quicksort的引用位置消失，mergesort再次突然变得具有竞争力。

最好的选择可能是考虑很多不同的因素，然后从那里做出决定。设计和研究算法如此有趣的原因之一是，很少有一个单一的最佳选择;通常，最好的选择取决于具体情况和根据所看到的情况而变化。

（虽然quicksort有一个退化的O（n2）最坏的情况，但是有很多方法可以避免这种情况。如果看起来快速排序会退化，则内省排序（introsort）算法会跟踪递归深度并将算法切换到堆栈。这可以保证O（n log n）最坏情况下的内存开销，并最大限度地提高从quicksort获得的好处随机快速排序虽然仍然具有O（n2）最坏情况，但实际上击中最坏情况的概率极小。

Heapsort在实践中是一种很好的算法，但在某些情况下并不像其他算法那么快，因为它没有良好的参考局部性。也就是说，它永远不会退化并只需要O（1）辅助空间这一事实是一个巨大的卖点。

Mergesort确实需要大量的辅助内存，这就是为什么在有大量数据需要排序时可能不想使用它的原因之一。但值得了解的是，因为它的变体被广泛使用。）

行排序，那么几乎可以锁定比较排序。如果没有，也许可以使用非比较排序，如计算排序（counting sort）或基数排序（radix sort）。

第四，数据有多少模块？一些排序算法（quicksort，mergesort，MSD基数排序）非常好并行化，而其他排序算法（如heapsort）则不是好的选择。

第五，数据如何表示？如果它们存储在数组中，则快速排序或快速排序变体可能会因为引用的位置而表现良好，而mergesort可能由于需要额外的内存而变慢。但是，如果它们在链表中，则来自quicksort的引用位置消失，mergesort再次突然变得具有竞争力。

最好的选择可能是考虑很多不同的因素，然后从那里做出决定。设计和研究算法如此有趣的原因之一是，很少有一个单一的最佳选择;通常，最好的选择取决于具体情况和根据所看到的情况而变化。

（虽然quicksort有一个退化的O（n2）最坏的情况，但是有很多方法可以避免这种情况。如果看起来快速排序会退化，则内省排序（introsort）算法会跟踪递归深度并将算法切换到堆栈。这可以保证O（n log n）最坏情况下的内存开销，并最大限度地提高从quicksort获得的好处随机快速排序虽然仍然具有O（n2）最坏情况，但实际上击中最坏情况的概率极小。

Heapsort在实践中是一种很好的算法，但在某些情况下并不像其他算法那么快，因为它没有良好的参考局部性。也就是说，它永远不会退化并只需要O（1）辅助空间这一事实是一个巨大的卖点。

Mergesort确实需要大量的辅助内存，这就是为什么在有大量数据需要排序时可能不想使用它的原因之一。但值得了解的是，因为它的变体被广泛使用。）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/981630
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号