扫一扫下方二维码,关注本站官方公众号
回复:2020加油
获取永久解锁本站全部文章的验证码

数据结构与算法之排序算法-Go语言中文社区

数据结构与算法之排序算法


数据结构与算法之排序算法

排序算法的介绍

​ 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排序的过程

排序的分类

  • 1)内部排序:指将需要处理的数据都加载到内部存储器(内存) 中进行排序
  • 2)外部排序:数据量过大,无法全部加载到内存中,需要借助外部存储(文件等) 进行排序
  • 3)常见的排序算法分类

在这里插入图片描述

算法的时间复杂度

度量一个程序(算法)执行时间的两种方法

  • 1)事后统计的方法:

    ​ 这种方法可行,但是有两个问题,一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较哪个算法速度更快。

  • 2)事前估算的方法

    ​ 通过分析某个算法的时间复杂度来判断哪个算法更优

时间频度

介绍

一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费的时间就多。一个算法中的语句执行次数成为语句频度或时间频度 。记为T(n)

案例1:计算1-100所有数字的和
int total = 0;
int end = 100;
//使用for循环计算
for(int i = 1;i <= end; i++){
    total += i;
}
// T(n) = n+1;
//直接计算
total = (1+end)*end/2;
// T(n) = 1;
案例2:忽略常数项

在这里插入图片描述
结论:

  • 1)2n+20和2n 随着n变大,执行曲线无限接近,20可以忽略
  • 2)3n+10和3n 随着n变大,执行曲线无限接近,10可以忽略
案例3:忽略低次项

在这里插入图片描述
结论:

  • 1)2n^2+3n+10 和2n^2 随着n变大,执行曲线无限接近,3n+10可以忽略
  • 2)n^2+5n+20 和n^2 随着n变大,执行曲线无限接近,5n+20可以忽略
案例4:忽略系数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-APvDqChT-1583072191081)(../学习笔记img/image-20200229121021105.png)]

结论:

  • 1)随着n值变大,5n^ 2+7n和3n^2+2n,执行曲线重合,说明这种情况下,5和3可以忽略
  • 2)而n^ 3+5n和6n^3+4n,执行曲线分离,说明多少次方关是键

时间复杂度

  • 一般情况下,算法中的基本操作语句 重复执行次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记做T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。
  • T(n)不同,但时间复杂度可能相同。如:T(n)=n^ 2+7n+6与T(n)=3n^ 2+2n+2,他们的T(n)不同,但时间复杂度相同,都为O(n^2)
  • 计算时间复杂度的方法:
    • 用常数1代替运行时间中的所有加法常数 :T(n)=n^ 2+7n+6=>T(n)=n^2+7n+1
    • 修改后的运行此数函数中,只保留最高阶项 :T(n)=n^ 2+7n+1=>T(n)=n^2
    • 去除最高阶项的系数 :T(n)=n^ 2=>T(n)=n^ 2 =>O(n)=n^2

常见的时间复杂度

  • 1)常数阶 O(1)

无论代码执行了多少行,只要没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)

int i=1;
int j=1;
++i;
j++;
int m = i + j;

上述代码在执行的时候,它消耗的时间并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O()

  • 2)对数阶O(nlog2n)
int i=1;
while(i<n){
    i = i * 2;
   
}

说明: 在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就退出了,也就是说2的x次方等于n,那么x=log2n也就是说循环log2n次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(log2n)。O(log2n)的这个2时间上是根据代码变化的,i=i*3,则是O()

  • 3)线性阶O(n)
for(int i = 0;i < n;i++){
    j = i;
    j++;
}

说明: 这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用O()

  • 4)线性对数阶O(nlog2n)
for(int i = 0;i < n;i++){
    m = 1;
    while(m < n){
        m = m * 2;
    }
}

说明: 线性对数阶其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是n*O(logN),也就是O(nlogN)

  • 5)平方阶O(n^2)(双层for循环)
for(int i = 0;i<=n;i++){
    for(int j = i;j<=n;j++){
        m = i * j;
    }
}

说明: 平方阶就更容易理解了,如果把O(n)的代码再嵌套循环一遍,它的时间复杂度就是O(n^ 2),这段代码其实就是嵌套了2层n循环,它的时间复杂度就是O(nn),即O(n^2),如果将其中一层循环的n改成m,那么它的时间复杂度就变成了O(mn)

  • 6)立方阶O(n^3)(三层for循环)

  • 7)k次方阶O(n^k)(k层for循环)

说明: 参考上面的O(n^2)去理解就好了,O()

  • 8)指数阶O(2^n)(应尽量避免指数阶算法)

常见的时间复杂度对应的图

说明:

  • 常见的算法时间复杂度由小到大依次为:O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^ 2)<O(n^ 3)<O(n^k)<O(n!),随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低
  • 从图中可见,我们应该尽量避免使用指数阶的算法

平均时间复杂度和最坏时间复杂度

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

算法的空间复杂度

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

常用的排序算法

冒泡排序

基本介绍

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

优化:

因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序。 因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里的优化,可以在冒泡排序写好后,在进行)

图解冒泡排序

在这里插入图片描述

小结:

  • 1)一共进行 数组的大小-1 次大的循环
  • 2)每一堂排序的次数在逐渐的减少
  • 3)如果我们发现在某趟排序中,没有发生一次交换,可以提前结束冒泡排序,这就是优化。

案例

有五个无序的数:3,9,-2,10,-2,使用冒牌排序法将其排成一个从小到大的有序数列

package cn.aixuxi.sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {3, 9, -1, 10, -2};
        //测试冒泡排序
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));
        bubble(arr);
        System.out.println("排序后:");
        System.out.println(Arrays.toString(arr));
        //为了容易理解,我们把冒泡排序的演变过程,展示出来
        //第一趟排序,将最大的数排在最后
//        int temp = 0;//临时变量
//        for (int i = 0; i < arr.length - 1; i++) {
            //如果前面的数比后面的数大,则交换
//            if (arr[i] > arr[i + 1]) {
//                temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//        System.out.println("第一趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
        //第二趟排序,就是将第二大的数字排在倒数第二位
//        for (int i = 0; i < arr.length - 1 - 1; i++) {
            //如果前面的数比后面的数大,则交换
//            if (arr[i] > arr[i + 1]) {
//                temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//        System.out.println("第二趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
        //第三趟排序,就是将第三大的数字排在倒数第三位
//        for (int i = 0; i < arr.length - 1 - 2; i++) {
            //如果前面的数比后面的数大,则交换
//            if (arr[i] > arr[i + 1]) {
//                temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//        System.out.println("第三趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
        //第四趟排序,就是将第四大的数字排在倒数第四位
//        for (int i = 0; i < arr.length - 1 - 3; i++) {
//            如果前面的数比后面的数大,则交换
//            if (arr[i] > arr[i + 1]) {
//                temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//        System.out.println("第四趟排序后的数组");
//        System.out.println(Arrays.toString(arr));
    }

    //封装的优化冒泡排序算法
    public static void bubble(int[] arr) {
        int temp = 0;
        //冒泡排序 时间复杂度为O(n^2)
        //优化
        boolean flag = true;//标识变量,表示是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                //如果前面的数比后面的大,则交换
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) {
                //在一趟排序中,一次交换都没有发生过
                break;
            } else {
                flag = false;//重置flag,进行下次的判断
            }
        }
    }
}

选择排序

基本介绍

​ 选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再以规定交换位置后达到排序的目的

选择排序思想

​ 选择排序(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次,得到一个排序码从小到大排列的有序序列。

思路分析图

在这里插入图片描述

说明:

  • 1)选择排序一共有数组大小-1 轮排序
  • 2)每一轮排序,又是一个循环,循环的规则(代码)
  • 3)先假定当前这个数是最小数
  • 4)然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
  • 5)当遍历到数组的最后时,就得到每轮最小数和下标
  • 6)交换代码中在继续循环

案例

使用选择排序从低到高进行排序:101 34 119 1

package cn.aixuxi.sort;

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //算法:先简单 ==> 做复杂,就是可以把一个复杂的算法,拆分成简单的问题,并逐步解决
    public static void selectSort(int[] arr){
        // 根据以下推导,简化代码
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j < arr.length; j++) {
                if (min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        //使用逐步的方式,讲解选择排序
        //第一轮
        //原始的数组:101,34,119,1
        //第一轮排序:1,34,119,101
//        int minIndex = 0;
//        int min = arr[minIndex];
//        for (int i = 1; i < arr.length ; i++) {
//            if (min>arr[i]){//说明假定的最小值,并不是最小值
//                min = arr[i];//重置min
//                minIndex = i;//重置minIndex
//            }
//        }
        //将最小值,放在arr[0],即交换
//        if (minIndex!=0){
//            arr[minIndex] = arr[0];
//            arr[0] = min;
//        }
        //第二轮
//        minIndex = 1;
//        min = arr[minIndex];
//        for (int i = 2; i < arr.length ; i++) {
//            if (min>arr[i]){//说明假定的最小值,并不是最小值
//                min = arr[i];//重置min
//                minIndex = i;//重置minIndex
//            }
//        }
        //将最小值,放在arr[0],即交换
//        if (minIndex!=1){
//            arr[minIndex] = arr[1];
//            arr[1] = min;
//        }
        //第三轮
//        minIndex = 2;
//        min = arr[minIndex];
//        for (int i = 3; i < arr.length ; i++) {
//            if (min>arr[i]){//说明假定的最小值,并不是最小值
//                min = arr[i];//重置min
//                minIndex = i;//重置minIndex
//            }
//        }
        //将最小值,放在arr[2],即交换
//        if (minIndex!=2){
//            arr[minIndex] = arr[2];
//            arr[2] = min;
//        }
    }
}

插入排序

基本介绍

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

插入排序法思想

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

插入排序思路图

在这里插入图片描述

案例

请用插入排序法将101,34,119,1从小到大进行排序

package cn.aixuxi.sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101,34,119,1};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    //插入排序
    public static void insertSort(int[] arr){
        //根据以下推导,简化代码
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal<arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1] = insertVal;
        }
        //逐步推导,便于理解
        //第一轮 {101,34,119,1} => {34,101,119,1}
        //定义待插入的数
//        int insertVal = arr[1];
//        int insertIndex = 0;//即arr[1]前面这个数的下标
        //给insertVal找到插入的位置
        /**
         * 说明:
         * 1.insertIndex >= 0 保证在给insertVal找插入位置,不越界
         * 2.insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置
         * 3.就需要将arr[insertIndex]后移
         */
//        while (insertIndex >= 0 && insertVal<arr[insertIndex]){
//            arr[insertIndex+1] = arr[insertIndex];//
//            insertIndex--;
//        }
        //当退出while循环时,说明插入的位置找到,insertIndex+1;
//        arr[insertIndex+1] = insertVal;

        //第二轮
//        insertVal = arr[2];
//        insertIndex = 1;
//        while (insertIndex >= 0 && insertVal<arr[insertIndex]){
//            arr[insertIndex+1] = arr[insertIndex];//
//            insertIndex--;
//        }
//        arr[insertIndex+1] = insertVal;
        //第三轮
//        insertVal = arr[3];
//        insertIndex = 2;
//        while (insertIndex >= 0 && insertVal<arr[insertIndex]){
//            arr[insertIndex+1] = arr[insertIndex];//
//            insertIndex--;
//        }
//        arr[insertIndex+2] = insertVal;
    }
}

希尔排序

简单插入排序存在的问题

假设数组 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时,整个文件恰被分成一组,算法遍终止。

希尔排序的示意图

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

案例

请对数组arr={8,9,1,7,2,3,5,4,6,0}从小到大进行排序,要求:

1)希尔排序时,对有序序列在插入时采用交换法

2)希尔排序时,对有序序列在插入时采用移动法

package cn.aixuxi.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        //换位法
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
        //移位法
        shellSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr) {
        int temp = 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;
                    }
                }

            }
        }
        //逐步推导的方式编写希尔排序(交换法)
        //希尔排序的第一轮
        //第一轮排序,将10个数据分成了5组
//        for (int i = 5; i < arr.length; i++) {
//            //遍历个组中的所有元素(共5组,每组有2个元素),步长5
//            for (int j = i - 5; j >= 0; j -= 5) {
//                //如果当前元素大于加上步长后的那个元素,说明交换
//                if (arr[j] > arr[j + 5]) {
//                    temp = arr[j];
//                    arr[j] = arr[j + 5];
//                    arr[j + 5] = temp;
//                }
//            }
//        }
        //希尔排序第二轮
        //第二轮排序,将10个数据分成了5/2组
//        for (int i = 2; i < arr.length; i++) {
//            for (int j = i - 2; j >= 0; j -= 2) {
//                //如果当前元素大于加上步长后的那个元素,说明交换
//                if (arr[j] > arr[j + 2]) {
//                    temp = arr[j];
//                    arr[j] = arr[j + 2];
//                    arr[j + 2] = temp;
//                }
//            }
//        }
        //希尔排序第三轮
        //第三轮排序,将10个数据分成了2/2组
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i - 1; j >= 0; j -= 1) {
//                //如果当前元素大于加上步长后的那个元素,说明交换
//                if (arr[j] > arr[j + 1]) {
//                    temp = arr[j];
//                    arr[j] = arr[j + 1];
//                    arr[j + 1] = temp;
//                }
//            }
//        }

    }
    //对交换式的希尔排序的优化==>移位法
    public static void shellSort2(int[] arr){
        //增量gap,并逐步的缩小增量
       for (int gap = arr.length / 2; gap > 0; gap /= 2) {
           //从第gap个元素,逐个对其所在的组进行直接插入排序
           for (int i = gap; i < arr.length; i++) {
               int j = i;
               int temp = arr[i];
               if (arr[j]<arr[j-gap]){
                   while (j-gap>=0 && temp < arr[j-gap]){
                        //移动

                    
版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/ruozhuliufeng/article/details/104601823
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。

0 条评论

请先 登录 后评论

官方社群