第 7 章排序算法-阿里云开发者社区

1、排序算法介绍

1.1、排序算法的简介

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

1.2、排序算法的分类

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

2、算法的复杂度

2.1、时间复杂度的度量方法

事后统计的方法：这种方法可行, 但是有两个问题：

一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；

二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快。

事前估算的方法：通过分析某个算法的时间复杂度来判断哪个算法更优

2.2、时间频度

基本介绍时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。 [举例说明]
举例说明-基本案例：比如计算 1-100 所有数字之和，我们设计两种算法：

int tatal =0;
        int end =100;
        //使用for循环计算
        for (int i = 0; i <=end; i++){
            tatal+=i;
        }
        T(n) =n+1;
       //直接计算
        tatal=(1+end)*end/2;
        T(n) =1;

举例说明-忽略常数项：

2n+20 和 2n 随着 n 变大，执行曲线无限接近, 20 可以忽略
3n+10 和 3n 随着 n 变大，执行曲线无限接近, 10 可以忽略

举例说明-忽略低次项：

2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10
n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+20

举例说明-忽略系数：

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

2.3、时间复杂度

事后统计的方法：这种方法可行, 但是有两个问题：

一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；

二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快。

事前估算的方法：通过分析某个算法的时间复杂度来判断哪个算法更优

2.2、时间频度

基本介绍时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。 [举例说明]
举例说明-基本案例：比如计算 1-100 所有数字之和，我们设计两种算法：

举例说明-忽略常数项：

2n+20 和 2n 随着 n 变大，执行曲线无限接近, 20 可以忽略
3n+10 和 3n 随着 n 变大，执行曲线无限接近, 10 可以忽略

举例说明-忽略低次项：

2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10
n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+20

举例说明-忽略系数：

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

2.3、时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时， T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=Ｏ ( f(n) )，称Ｏ ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。
T(n) 不同，但时间复杂度可能相同。如： T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的 T(n) 不同，但时间复杂度相同，都为 O(n²)。
计算时间复杂度的方法：

用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1

修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²

去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

2.4、常见的时间复杂度

2.4.1、常见时间复杂度概述

常见时间复杂度

常数阶 O(1)
对数阶 O(log2n)
线性阶 O(n)
线性对数阶 O(nlog2n)
平方阶 O(n^2)
立方阶 O(n^3)
k 次方阶 O(n^k)
指数阶 O(2^n)

结论：

常见的算法时间复杂度由小到大依次为： Ο (1)＜Ο (log2n)＜Ο (n)＜Ο (nlog2n)＜Ο (n2)＜Ο (n3)＜ Ο (nk) ＜ Ο (2n) ，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

从图中可见，我们应该尽可能避免使用指数阶的算法

2.4.2、常数阶 O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

2.4.3、对数阶 O(log2n)

2.4.4、线性阶 O(n)

说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

2.4.5、线性对数阶 O(nlogN)

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

2.4.6、平方阶 O(n²)

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

2.4.7、其他阶

立方阶 O(n³)、 K 次方阶 O(n^k)
说明：参考上面的 O(n²) 去理解就好了， O(n³)相当于三层 n 循环，其它的类似

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

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图)。

2.6、算法的空间复杂度

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

3、冒泡排序

3.1、基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
优化：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。 (这里说的优化，可以在冒泡排序写好后，再进行)

3.2、冒泡排序图解

第一趟：

从数组 arr 第一个元素开始，与其后面一个元素比较大小
如果 arr[i] > arr[i+1] ，则交换，将大的元素换到后面去
由于是当前元素与其后面一个元素比较大小，所以只需要执行 arr.length - 1 次循环

第二趟：

从数组 arr 第一个元素开始，与其后面一个元素比较大小
由于第一趟排序完成，数组最后一个元素已是最大元素，所以只需要执行 arr.length - 1 - 1 次循环

啥时候完成？下面两个条件满足任意一个即可：
当其中有一趟排序没有元素交换位置时，说明数组已经有序
或：按照上述流程，跑完第arr.length - 1趟之后

这样来想：5 个元素的数组，最多只需要跑 4 趟

为什么最多只需要跑 4 趟？因为跑完 4 趟之后，数组第二个元素已经成为了数组第二小的元素，那么数组自然就是有序数组
即数组长度如果为 n ，那么则需要跑 n - 1 趟

总结：两层 for 循环

第一层 for 循环控制走多少趟：for (int i = 0; i < arr.length - 1; i++) {
第二层 for 循环实现针对该趟循环，进行冒泡：for (int j = 0; j < arr.length - 1 - i; j++) {
伪代码：

for (int i = 0; i < ; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        // 执行冒泡操作
    }
    if(/* 该趟没有交换 */) {
        // 数组已然有序，跳出循环
    }
}

3.3、代码实现

3.3.1、理解冒泡排序

上面的例子不好，我们把数组改成：int arr[] = { 3, 9, -1, 10, -2 }; 这样更能说明冒泡排序的特点

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

程序运行结果

排序前
[3, 9, -1, 10, -2]
第一趟排序后的数组
[3, -1, 9, -2, 10]
第二趟排序后的数组
[-1, 3, -2, 9, 10]
第三趟排序后的数组
[-1, -2, 3, 9, 10]
第四趟排序后的数组
[-2, -1, 3, 9, 10]

3.3.2、编写冒泡排序

测试极端情况

public static void main(String[] args) {
 int arr[] = { 1, 2, 3, 4, 5, 6 };
 // 为了容量理解，我们把冒泡排序的演变过程，给大家展示
 System.out.println("排序前");
 System.out.println(Arrays.toString(arr));
 bubbleSort(arr);
}
// 将前面额冒泡排序算法，封装成一个方法
public static void bubbleSort(int[] arr) {
 // 冒泡排序 的时间复杂度 O(n^2), 自己写出
 int temp = 0; // 临时变量
 boolean flag = false; // 标识变量，表示是否进行过交换
 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;
    temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
   }
  }
  System.out.println("第" + (i + 1) + "趟排序后的数组");
  System.out.println(Arrays.toString(arr));
  if (!flag) { // 在一趟排序中，一次交换都没有发生过
   break;
  } else {
   flag = false; // 重置flag!!!, 进行下次判断
  }
 }
}

程序运行结果

排序前
[1, 2, 3, 4, 5, 6]
第1趟排序后的数组
[1, 2, 3, 4, 5, 6]

3.3.3、测试冒泡排序性能

测试代码

public static void main(String[] args) {
 // 测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
 // 创建要给80000个的随机的数组
 int[] arr = new int[80000];
 for (int i = 0; i < 80000; i++) {
  arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
 }
 Date date1 = new Date();
 SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
 String date1Str = simpleDateFormat.format(date1);
 System.out.println("排序前的时间是=" + date1Str);
 // 测试冒泡排序
 bubbleSort(arr);
 Date date2 = new Date();
 String date2Str = simpleDateFormat.format(date2);
 System.out.println("排序后的时间是=" + date2Str);
}
// 将前面额冒泡排序算法，封装成一个方法
public static void bubbleSort(int[] arr) {
 // 冒泡排序 的时间复杂度 O(n^2), 自己写出
 int temp = 0; // 临时变量
 boolean flag = false; // 标识变量，表示是否进行过交换
 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;
    temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
   }
  }
  if (!flag) { // 在一趟排序中，一次交换都没有发生过
   break;
  } else {
   flag = false; // 重置flag!!!, 进行下次判断
  }
 }
}

程序运行结果

排序前的时间是=2020-07-15 11:44:08
排序后的时间是=2020-07-15 11:44:16

4、选择排序

4.1、选择排序基本介绍

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

4.2、选择排序思想

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是（n 是数组大小）：
第一次从 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 次，得到一个按排序码从小到大排列的有序序列。

4.3、选择排序图解

选择排序流程：
第一次循环，默认 arr[0] 是最小的元素，将其与 arr[1]~arr[n-1] 进行比较，找到最小的元素，并与 arr[0] 的位置位置

第二次循环，默认 arr[1] 是最小的元素，将其与 arr[2]~arr[n-1] 进行比较，找到最小的元素，并与 arr[1] 的位置位置

第 i 次循环，默认 arr[i] 是最小的元素，将其与 arr[i+1]~arr[n-1] 进行比较，找到最小的元素，并与 arr[i] 的位置位置

直到循环执行 n - 1 次

总结：两层 for 循环

第一层 for 循环控制走多少趟：for (int i = 0; i < arr.length - 1; i++) {

从数组第一个元素开始，因为每次都是拿当前元素 arr[j] 和其后一个元素 arr[j+1] 进行比较

到数组倒数第二个元素结束，将 arr[arr.length - 2] 与 arr[arr.length - 1] 进行比较后，数组就已经是有序数组

如果数组大小为 n ，那么执行完第 n - 1 趟时，数组就已经是有序数组

第二层 for 循环控制从第几个元素开始执行选择排序：for (int j = i + 1; j < arr.length; j++)

每次进入第二层 for 循环时，先假设当前元素 arr[i] 是最小的元素：min = arr[i]; ，并记录最小元素的下标：index = i;

然后依次和其后面的元素 arr[j] 比较，如果找到比 arr[i] 小的元素，则更新最小值和最小值的索引：min = arr[j]; index = j ;

4.4、代码实现

4.4.1、理解选择排序

一步一步理解选择排序算法

//选择排序
public class SelectSort {
 public static void main(String[] args) {
  int[] arr = { 101, 34, 119, 1 };
  selectSort(arr);
 }
 // 选择排序
 public static void selectSort(int[] arr) {
  // 使用逐步推导的方式来，讲解选择排序
  // 第1轮
  // 原始的数组 ： 101, 34, 119, 1
  // 第一轮排序 : 1, 34, 119, 101
  // 算法 先简单--》 做复杂， 就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决
  // 第1轮
  int minIndex = 0;
  int min = arr[0];
  for (int j = 0 + 1; j < arr.length; j++) {
   if (min > arr[j]) { // 说明假定的最小值，并不是最小
    min = arr[j]; // 重置min
    minIndex = j; // 重置minIndex
   }
  }
  // 将最小值，放在arr[0], 即交换
  if (minIndex != 0) {
   arr[minIndex] = arr[0];
   arr[0] = min;
  }
  System.out.println("第1轮后~~");
  System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
  // 第2轮
  minIndex = 1;
  min = arr[1];
  for (int j = 1 + 1; j < arr.length; j++) {
   if (min > arr[j]) { // 说明假定的最小值，并不是最小
    min = arr[j]; // 重置min
    minIndex = j; // 重置minIndex
   }
  }
  // 将最小值，放在arr[0], 即交换
  if (minIndex != 1) {
   arr[minIndex] = arr[1];
   arr[1] = min;
  }
  System.out.println("第2轮后~~");
  System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
  // 第3轮
  minIndex = 2;
  min = arr[2];
  for (int j = 2 + 1; j < arr.length; j++) {
   if (min > arr[j]) { // 说明假定的最小值，并不是最小
    min = arr[j]; // 重置min
    minIndex = j; // 重置minIndex
   }
  }
  // 将最小值，放在arr[0], 即交换
  if (minIndex != 2) {
   arr[minIndex] = arr[2];
   arr[2] = min;
  }
  System.out.println("第3轮后~~");
  System.out.println(Arrays.toString(arr));// 1, 34, 101, 119
 }
}

程序运行结果

第1轮后~~
[1, 34, 119, 101]
第2轮后~~
[1, 34, 119, 101]
第3轮后~~
[1, 34, 101, 119]

4.4.2、编写选择排序

编写选择排序算法

//选择排序
public class SelectSort {
 public static void main(String[] args) {
  int[] arr = { 101, 34, 119, 1 };
  selectSort(arr);
 }
 // 选择排序
 public static void selectSort(int[] arr) {
  // 在推导的过程，我们发现了规律，因此，可以使用for来解决
  // 选择排序时间复杂度是 O(n^2)
  for (int i = 0; i < arr.length - 1; i++) {
   int minIndex = i;
   int min = arr[i];
   for (int j = i + 1; j < arr.length; j++) {
    if (min > arr[j]) { // 说明假定的最小值，并不是最小
     min = arr[j]; // 重置min
     minIndex = j; // 重置minIndex
    }
   }
   // 将最小值，放在arr[0], 即交换
   if (minIndex != i) {
    arr[minIndex] = arr[i];
    arr[i] = min;
   }
   System.out.println("第" + (i + 1) + "轮后~~");
   System.out.println(Arrays.toString(arr));
  }
 }
}

程序运行结果

第1轮后~~
[1, 34, 119, 101]
第2轮后~~
[1, 34, 119, 101]
第3轮后~~
[1, 34, 101, 119]

4.4.3、测试选择排序性能

测试代码

//选择排序
public class SelectSort {
 public static void main(String[] args) {
  //创建要给80000个的随机的数组
  int[] arr = new int[80000];
  for (int i = 0; i < 80000; i++) {
   arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
  }
  Date data1 = new Date();
  SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
  String date1Str = simpleDateFormat.format(data1);
  System.out.println("排序前的时间是=" + date1Str);
  selectSort(arr);
  Date data2 = new Date();
  String date2Str = simpleDateFormat.format(data2);
  System.out.println("排序前的时间是=" + date2Str);
 }
 // 选择排序
 public static void selectSort(int[] arr) {
  // 在推导的过程，我们发现了规律，因此，可以使用for来解决
  // 选择排序时间复杂度是 O(n^2)
  for (int i = 0; i < arr.length - 1; i++) {
   int minIndex = i;
   int min = arr[i];
   for (int j = i + 1; j < arr.length; j++) {
    if (min > arr[j]) { // 说明假定的最小值，并不是最小
     min = arr[j]; // 重置min
     minIndex = j; // 重置minIndex
    }
   }
   // 将最小值，放在arr[0], 即交换
   if (minIndex != i) {
    arr[minIndex] = arr[i];
    arr[i] = min;
   }
  }
 }
}

程序运行结果

排序前的时间是=2020-07-15 19:59:19
排序前的时间是=2020-07-15 19:59:20

4.5、总结

由于选择排序算法在最内层的 for 循环中，满足 if (min > arr[j]) { 条件后，只需要记录最小值和最小值在数组中的索引，无需像冒泡排序那样每次都要执行交换操作，所以选择排序算法的执行速度比冒泡排序算法快一些

第 7 章排序算法

1、排序算法介绍

1.1、排序算法的简介

1.2、排序算法的分类

2、算法的复杂度

2.1、时间复杂度的度量方法

2.2、时间频度

2.3、时间复杂度

2.2、时间频度

2.3、时间复杂度

2.4、常见的时间复杂度

2.4.1、常见时间复杂度概述

2.4.2、常数阶 O(1)

2.4.3、对数阶 O(log2n)

2.4.4、线性阶 O(n)

2.4.5、线性对数阶 O(nlogN)

2.4.6、平方阶 O(n²)

2.4.7、其他阶

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

2.6、算法的空间复杂度

3、冒泡排序

3.1、基本介绍

3.2、冒泡排序图解

3.3、代码实现

3.3.1、理解冒泡排序

3.3.2、编写冒泡排序

3.3.3、测试冒泡排序性能

4、选择排序

4.1、选择排序基本介绍

4.2、选择排序思想

4.3、选择排序图解

4.4、代码实现

4.4.1、理解选择排序

4.4.2、编写选择排序

4.4.3、测试选择排序性能

4.5、总结

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

第 7 章 排序算法

1、排序算法介绍

1.1、排序算法的简介

1.2、排序算法的分类

2、算法的复杂度

2.1、时间复杂度的度量方法

2.2、时间频度

2.3、时间复杂度

2.2、时间频度

2.3、时间复杂度

2.4、常见的时间复杂度

2.4.1、常见时间复杂度概述

2.4.2、常数阶 O(1)

2.4.3、对数阶 O(log2n)

2.4.4、线性阶 O(n)

2.4.5、线性对数阶 O(nlogN)

2.4.6、平方阶 O(n²)

2.4.7、其他阶

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

2.6、算法的空间复杂度

3、冒泡排序

3.1、基本介绍

3.2、冒泡排序图解

3.3、代码实现

3.3.1、理解冒泡排序

3.3.2、编写冒泡排序

3.3.3、测试冒泡排序性能

4、选择排序

4.1、选择排序基本介绍

4.2、选择排序思想

4.3、选择排序图解

4.4、代码实现

4.4.1、理解选择排序

4.4.2、编写选择排序

4.4.3、测试选择排序性能

4.5、总结

热门文章

最新文章

相关电子书

第 7 章排序算法