算法の排序算法 | Monster

算法の排序算法

前言
  • 最近重新开始求职面试的原因,利用一个周末的闲暇整理了一下Java的排序算法,在面试中也是常见的笔试题。。
排序算法
  • 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程

  • 排序的分类

    • 内部排序

      指将需要处理的所有数据加载到内部存储器中进行排序

    • 外部排序

      数据量过大,无法全部加载到内存中,需要借助外部存储进行排序

  • 常见的排序算法

    • 插入排序
      1. 直接插入排序
      2. 希尔排序
    • 选择排序
      1. 简单选择排序
      2. 堆排序
    • 交换排序
      1. 冒泡排序
      2. 快速排序
    • 归并排序
    • 基数排序
算法的时间复杂度
  • 事后统计法

    就是所谓的控制相同变量,将两段程序运行过后进行效率上的比较,并没有啥实际意义

  • 事前估算法

  • 时间频度

    • 一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,他花费的时间就多。一个算法语句中的语句执行次数称为语句频度或时间频度。记为T(n)
    • 系数、常数项、低次项可以忽略
  • 时间复杂度

    • 一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用T(n)表示(时间频度),若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)T(n)的同数量级函数,记做T(n)=O(f(n))为算法的渐进时间复杂度,简称时间复杂度

    • 例:T(n) = n² + 7n + 6T(n) = 3n² + 2n + 2他们的T(n)不同,但是时间复杂度相同,去掉常数项、系数、低次项,都为O(n²)

    • 计算时间复杂度的方法:

      • 用常数1代替运行时间中的所有加法常数

        n² + 7n + 6 ==> n² + 7n + 1

      • 修改后的运行次数函数中,只保留最高阶项

        n² +7n + 1 ==>

      • 去除最高阶项的系数

    • 常见的时间复杂度(由小到大)

      1. 常数阶O(1)

        无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度都是O(1) ,当代码所消耗的时间并不会随着某个变量的增长而增长,那么无论这段代码有多长,时间复杂度都是O(1)

      2. 对数阶O(log2n)

      3. 线性阶O(n)

      4. 线性对数阶O(nlog2n)

      5. 平方阶O(n²)

      6. 立方阶O(n³)

      7. k次方阶O(n^k)

      8. 指数阶O(2^n)

    • 平均时间复杂度与最坏时间复杂度

      • 平均时间复杂度是指所有可能的输入实例以等概率出现的情况下,该算法的运行时间
      • 最坏情况下的时间复杂度称为最坏时间复杂度,一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是因为:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长
      • 平均时间复杂度和最坏时间复杂度是否一致,与算法有关
    • 空间复杂度

      • 一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间
      • 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用更多的存储单元,例如快速排序归并排序就属于这种情况
      • 在做算法分析的时候,主要讨论的是时间复杂度,从用户体验上看,更看重的是程序执行的速度,一些缓存产品和算法的本质就是用空间换时间
冒泡排序(Bubble Sorting)
  • 冒泡排序应该是所有排序中最为简单的排序了,也是一个最基本最常见的排序算法

  • 通过对待排序序列从前向后,依次比较相邻元素的值,若发现逆序则交换,使得值较大的元素逐渐从前移向后部,就如同水中的起泡一样逐渐往上冒

  • 优化:因为在排序过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列已然有序,因此需要在排序过程中设置一个标识来拍短元素是否进行了位置交换,从而减少不必要的比较

  • 图解:

  • 实现:

    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
    /**
    * @author Monster
    * @date 2020/7/14 14:10
    * 冒泡排序
    */
    public class BubbleSort {

    public static void main(String[] args) {


    int []arr = new int[]{32,17,9,38,66,99};
    /*int []arr = new int[80000];
    for (int i = 0; i < arr.length; i++) {
    arr[i] = new Random().nextInt(80000);
    }*/



    int count = 0; // 记录遍历次数


    // 优化:当某一轮外层循环执行完成之后并没有发生未知变换,则可以直接诶将冒泡排序结束
    boolean flag = false; // 记录是否发生交换

    long startTime = System.currentTimeMillis();

    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]){
    flag = true; // 发生交换 将该标识为true
    int temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    }
    count ++;


    }


    if(!flag){ // 如果并未发位置交换 则结束循环
    break;
    }

    }
    long endTime = System.currentTimeMillis();


    System.out.println("次数:" +count);
    System.out.println("耗时:" + (endTime-startTime) + "ms");
    for (int i : arr) {
    System.out.print(i+"\t");
    }
    }
    }
选择排序(Select Sorting)
  • 选择排序,就是将数组中的数据两两比对,得到一个最值,然后将这个最值与该数组的第一个位置互换,然后以此类推放置到第二、第三位置,直至排序结束

  • 图解:

  • 实现:

    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
    /**
    * @author Monster
    * @date 2020/7/14 16:19
    * 选择排序
    */
    public class SelectSort {

    public static void main(String[] args) {
    int arr[] = new int[]{77,66,38,32,1,23};



    for (int j = 0; j < arr.length-1; j++) {
    // 记录第一个位置的数
    int min = arr[j];
    // 记录需要交换的数的索引
    int index= j;

    for (int i = 1+j; i < arr.length; i++) {
    // 将第一个数与其他数逐个遍历比较 如果第一个数较大则记录那个小的数和索引
    if(min > arr[i]){
    min = arr[i];
    index = i;
    }
    }

    // 如果最小的数不在第一个 则将最小的数与第一个数交换
    if(index!=j){
    arr[index] = arr[j];
    arr[j] = min;
    }

    }



    for (int i : arr) {
    System.out.print(i+"\t");
    }
    }
    }
插入排序(Insertion Sorting)
  • 插入排序法属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的

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

  • 图解:

  • 实现:

    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
    /**
    * @author Monster
    * @date 2020/7/16 16:22
    * 插入排序
    */
    public class InsertionSort {

    public static void main(String[] args) {

    int arr[] = new int[]{37,32,68,83,12,9};

    for (int i = 1; i < arr.length; i++) {

    int temp = arr[i]; // 待插入的数
    int index = i-1; // 待插入的数的前一个数的索引

    while(index>=0 && temp < arr[index]){ // 如果待插入的数小于前一个数
    arr[index+1] = arr[index];

    index -- ; //继续向前比较 如果没有数则退出循环 说明该数已找到要插入的位置
    }

    arr[index+1] = temp; // 将待插入的数放置位置中

    }


    for (int i : arr) {
    System.out.print(i+"\t");
    }
    }
    }
希尔排序(ShellSort)
  • 希尔排序是希尔于1959年提出的一种排序算法,希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也被称为缩小增量排序

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

  • 图解:

  • 实现

    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
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    /**
    * @author Monster
    * @date 2020/8/23 17:19
    * 希尔排序
    */
    public class ShellSort {
    public static void main(String[] args) {

    // 原始数据
    int [] arr = {4,3,1,9,6,7,5,8,2,0};

    System.out.println(Arrays.toString(arr));




    // 方式一:交换式
    // 每次将增量除以二进行分组
    /* for (int i = arr.length/2; i >0 ; i/=2) {

    // 遍历各组中的所有元素,步长为 i
    for(int j = i; j<arr.length; j++){

    // 将每组的元素进行插入排序 比较进行交换
    for(int k = j-i; k>= 0; k-=i){
    if(arr[k] > arr[k+i]){
    int temp = arr[k];
    arr[k] = arr[k+i];
    arr[k+i] = temp;
    }
    }
    }

    }

    System.out.println(Arrays.toString(arr));*/


    // ---------------------------
    // 使用交换式的希尔排序在效率上还不及普通德插入排序,需要对其进行优化,改进成移位法


    // 方式二:移位式

    for (int i = arr.length/2; i >0 ; i/=2) {

    for (int j = i; j <arr.length ; j++) {

    int k = j; // 记录当前下标
    int temp = arr[k]; // 记录当前下标的元素

    // 使用while循环比较当前组的数据 依照插入法的方式找到放置的位置 待结束后在将其设置
    while(k - i >= 0 && temp < arr[k-i]){
    // 移动
    arr[k] = arr[k-i];
    k -=i;
    }

    //退出 while 循环找到插入的位置
    arr[k] = temp;

    }
    }


    System.out.println(Arrays.toString(arr));



    }

    // 逐步分析法
    public static void sort(int [] arr){

    // 第一轮排序
    for (int i = 5; i<arr.length ; i++) {

    for (int j = i-5; j >=0 ; j-=5) {

    if(arr[j] > arr[j+5]){
    int temp = arr[j];
    arr[j] = arr[j+5];
    arr[j+5] = temp;
    }
    }
    }

    System.out.println(Arrays.toString(arr));

    // 第二轮排序
    System.out.println("---------------------------------------------------");
    for (int i = 2; i<arr.length ; i++) {

    for (int j = i-2; j >=0 ; j-=2) {

    if(arr[j] > arr[j+2]){
    int temp = arr[j];
    arr[j] = arr[j+2];
    arr[j+2] = temp;
    }
    }
    }

    System.out.println(Arrays.toString(arr));


    // 第三轮排序
    System.out.println("---------------------------------------------------");
    for (int i = 1; i<arr.length ; i++) {

    for (int j = i-1; j >=0 ; j-=1) {

    if(arr[j] > arr[j+1]){
    int temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    }
    }
    }

    System.out.println(Arrays.toString(arr));
    }
    }
快速排序(QuickSort)
  • 快速排序是对冒泡排序的一种改进,其基本思想是:通过一趟排序将要排序的数据分割成独立的两个部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归执行

  • 图解:

  • 实现:

    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
    /**
    * @author Monster
    * @date 2020/8/24 23:54
    * 快速排序
    */
    public class QuickSort {

    public static void main(String[] args) {
    int []arr = {2,9,3,38,7,65,11,32,86,0};

    int leftIndex = 0; //左下标
    int rightIndex = arr.length-1; // 右下标

    QuickSort(arr,leftIndex,rightIndex);


    }

    public static void QuickSort(int[]arr,int left,int right){
    int leftIndex = left;
    int rightIndex = right;

    int pivot = arr[(leftIndex+rightIndex)/2]; //中轴值

    while(leftIndex < rightIndex){

    // 在中轴的左边一直找 直至找到比中轴值大的
    while(arr[leftIndex] < pivot){
    leftIndex++;
    }

    // 在中轴值的右边一直找,直至找到比中轴小的
    while(arr[rightIndex] > pivot){
    rightIndex--;
    }

    // 说明 两边的值已经按照中轴左右划分
    if(leftIndex >= rightIndex){
    break;
    }

    // 交换
    int temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;

    // 如果left与中轴值相等 则前移一步
    if(arr[leftIndex] == pivot){
    rightIndex --;
    }

    // 如果right与中轴值相等 则后移一步
    if(arr[rightIndex] == pivot){
    leftIndex++;
    }
    }

    // 如果 left == right 必须 left ++ 否则会出现栈溢出
    if(leftIndex == rightIndex){
    leftIndex++;
    rightIndex--;
    }

    System.out.println(Arrays.toString(arr));

    // 向左递归
    if(left<rightIndex){
    QuickSort(arr,left,rightIndex);
    }

    // 向右递归
    if(right>leftIndex){
    QuickSort(arr,leftIndex,right);
    }


    }
    }
归并排序(MergeSort
  • 归并排序是利用归并的思想实现的排序方法,该算法采用分治策略(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将粉的阶段得到的答案修补在一起,即分而治之)

  • 图解:

  • 实现:

    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
    /**
    * @author Monster
    * @date 2020/8/25 23:34
    * 归并排序
    */
    public class MergeSort {

    public static void main(String[] args) {

    int []arr = {8,4,5,7,1,3,6,2,9,0};

    int []temp = new int[arr.length]; // 归并排序需要额外的空间

    mergeSort(arr,0,arr.length-1,temp);


    System.out.println(Arrays.toString(arr));
    }



    // 分解的方法
    public static void 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);
    }
    }


    // 合并的方法
    /**
    *
    * @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; // 左边有序序列的初始索引
    int j = mid + 1; //右边序列的初始索引
    int t= 0; // temp的索引

    // 首先将左右两边的有序数据按照规则填充到temp数组
    // 直到左右两边的有序序列 有一边处理完毕为止
    while(i<=mid && j<=right){
    // 如果左边有序序列的当前元素小于后边的当前元素
    // 将左边的当前元素填充到temp数组中
    if(arr[i] <= arr[j]){
    temp[t] = arr[i];
    t++;
    i++;
    }else{
    // 如果右边的更小 则将右边的填充到temp数组中
    temp[t] = arr[j];
    t++;
    j++;
    }
    }

    // 把有剩余的一边的数据依次填充到temp数组
    // 左边还有剩余
    while(i <= mid){
    temp[t] = arr[i];
    t++;
    i++;
    }

    // 右边还有剩余
    while(j <= right){
    temp[t] = arr[j];
    t++;
    j++;
    }

    // 将temp数组中的数据拷贝至arr
    // 并不是每次都拷贝所有

    t = 0;
    int tempLeft= left;
    while(tempLeft <= right){
    arr[tempLeft] = temp[t];
    t++;
    tempLeft++;
    }

    }
    }
基数排序(RadixSort)
  • 基数排序属于“分配式排序”,又称为“桶子法”,顾名思义,它是通过键值的各个位的值将要排序的元素分配至某些中,达到排序的作用

  • 基数排序是属于稳定性的排序,基数排序法是效率高的稳定性排序法

  • 基数排序是1887年赫尔曼·何乐礼发明的,它是这样实现的,将整数按位数切割成不同的数字,然后每个位数分别比较

  • 图解:

  • 代码:

    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
    /**
    * 基数排序
    * @author ChengMiao
    * @date 2020/9/17 9:16
    */
    public class RadixSort {



    public static void main(String[] args) {


    int arr[] = {53,9,722,361,884,214};

    // 得到要排序的数中的最大的位数
    int maxPosition = maxPosition(arr);

    // 桶
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    // 桶初始化
    list.forEach(item-> new ArrayList<Integer>());

    // 将各个位数比较一次 则排序结束 rate 定义为每次求模的被除数 10 100 1000
    for (int i = 0, rate = 10; i <maxPosition ; i++, rate *= 10) {

    // 数据入桶
    for (int j = 0; j < arr.length ; j++) {

    int k = arr[j] % rate; // 求模的结果
    list.get(k).add(arr[j]); // 将当前数据放入指定的桶
    }

    // 遍历 将桶中的数据依次放入原数组中 然后继续向前入桶
    for (int j = 0, l = 0; j < list.size(); j++) {

    // 如果桶中的数据不为空 则将其取出 这里是通过获取第一个 然后将其删除直至为null 来拿到数据
    while(!list.get(j).isEmpty()){

    arr[l] = list.get(j).get(0); // 得到第一个数
    list.get(j).remove(0);
    l++;
    }
    }
    }

    }


    // 计算数组中最大的数的位数
    public static int maxPosition(int []arr){

    int maxLength = 0;

    for (int i = 0; i < arr.length; i++) {
    int length = Integer.toString(arr[i]).length();
    maxLength = length > maxLength ? length : maxLength;
    }

    return maxLength;
    }
    }

。。。后续补充

-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%