学习地址：【数据结构与算法基础-java版】 🚀数据结构--Java专栏🚀
笔记01【01-09】【概述、数组基本使用】【源码、课件】笔记02【10-18】【栈、队列、单链表(增删节点)、循环链表、双向循环链表、递归(斐波那契、汉诺塔)】笔记03【19-27】【（时间、空间复杂度）；八大排序（冒泡、快速、插入、希尔、选择、归并、基数、队列基数）】笔记04【28-33】【树结构(二叉树)概述、创建、遍历、查找节点、删除节点】笔记05【34-39】【顺序存储二叉树概述、二叉树遍历、堆排序、线索二叉树实现及遍历】笔记06【40-48】【赫夫曼树、概述、原理分析、代码实现(数据压缩、创建编码表、解码、压缩文件、解压文件)】笔记07【49-54】【二叉排序树（添加、查找、删除节点）】笔记08【55-57】【二叉平衡树(AVL)-概述、单旋转、双旋转】笔记09【58-60】【计算机中数据的存储原理、2-3树的插入原理、B树和B+树】笔记10【61-63】【哈希表概述、散列函数的设计、散列冲突解决方案】笔记11【64-67】【图结构概述、图遍历原理(BFS\DFS)、图遍历代码实现】
目 录
P19-3.1算法的时间复杂度和空间复杂度
1、时间复杂度
1.1、忽略常数
1.2、忽略低次项
1.3、忽略系数
2、衡量一个算法的优劣（时间复杂度、空间复杂度）
2.1、语句频度T(n)
2.2、时间复杂度
2.3、常见的时间复杂度
2.4、时间复杂度
2.5、平均时间复杂度和最坏时间复杂度
P20-3.2排序算法之冒泡排序
P21-3.3排序算法之快速排序
P22-3.4排序算法之插入排序
P23-3.5排序算法之希尔排序
P24-3.6排序算法之选择排序
P25-3.7排序算法之归并排序
P26-3.8排序算法之基数排序
P27-3.9基数排序之队列实现
P19-3.1算法的时间复杂度和空间复杂度
1、时间复杂度
1.1、忽略常数
1.2、忽略低次项
1.3、忽略系数
2、衡量一个算法的优劣（时间复杂度、空间复杂度）
一、事后统计的方法
二、事前分析估算的方法
计算1-100所有数字之和
2.1、语句频度T(n)
一个算法中的语句执行次数称为语句频度，记为T(n)。
2.2、时间复杂度
一般情况下，算法中的基本操作语句的重复执行次数是问题规模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²+5n+6 与 T(n)=3n²+3n+2 它们的T(n)不同，但时间复杂度相同，都为O(n²)。
2.3、常见的时间复杂度
常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n2)
立方阶O(n3)
k次方阶O(nk)
指数阶O(2n)
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
2.4、时间复杂度
计算时间复杂度的方法：
用常数1代替运行时间中的所有加法常数
修改后的运行次数函数中，只保留最高阶项
去除最高阶项的系数
2.5、平均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
P20-3.2排序算法之冒泡排序
package demo4;import java.util.Arrays;public class BubbleSort {public static void main(String[] args) {int[] arr = new int[] { 5, 7, 2, 9, 4, 1, 0, 5, 7 };System.out.println(Arrays.toString(arr));bubbleSort(arr);System.out.println(Arrays.toString(arr));}/**冒泡排序 * 共需要比较length-1轮* 5,7,2,9,4,1,0,5,7【5、7】* 5,7,2,9,4,1,0,5,7【7、2】* 5,2,7,9,4,1,0,5,7...* 5,2,7,4,1,0,5,7,9* 2,5 */public static void bubbleSort(int[] arr) {// 控制共比较多少轮for (int i = 0; i < arr.length - 1; i++) {// 控制比较的次数for (int j = 0; j < arr.length - 1 - i; j++) { // 减i,比较过的数字,不再进行比较if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}// 冒泡排序优化public static void bubbleSort2(int[] arr) {// 控制共比较多少轮for (int i = 0; i < arr.length - 1; i++) {boolean flag = false;// 控制比较的次数for (int j = 0; j < arr.length - 1 - i; j++) { // 减i,比较过的数字,不再进行比较if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true; // 加入标记}}if(flag) { // 如果没有交换过元素，则已经有序！return;}}}}
冒泡排序优化：/hansionz/article/details/80822494
P21-3.3排序算法之快速排序
找一个数字，作为标准(基准横线)来排序（通常取数组第一个数字！），将数组拆分为2部分，大数在右；小数在左；再将拆分后的数组，继续拆分。递归。【第一次排序，对所有的数据进行排序；之后的排序 对 部分数据 进行排序。】low、high重合，数组按照基数分配完毕。比基数大的数字，在右边；比基数小的数字，在左边；继续递归。
设定一个基准数a。【通常取第一个数字！】
比a大的数字，往右移动；比a小的数字，往左移动！递归！！！
设置 前后 2个 标记，标记重合，进行下一次 递归！【递归结束条件：开始位置==结束位置】
package demo4;import java.util.Arrays;public class QuickSort {public static void main(String[] args) {int[] arr = new int[] { 3, 4, 6, 7, 2, 7, 2, 8, 0, 9, 1 };quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}public static void quickSort(int[] arr, int start, int end) {if (start < end) {int stard = arr[start]; // 把数组中的第0个数字做为标准数【从数组的开始位置取标准数】int low = start; // 记录坐标-记录需要排序的下标int high = end; // 记录坐标while (low < high) { // 循环找比标准数大的数和比标准数小的数【高右低左】// 1、右边的数字比标准数大，则数字不需要移动，high--// stard <= arr[high]：基准数要小于右边指针所指的数字while (low < high && stard <= arr[high]) {high--;//基准数小于右边指针所指的数字，high--前移}arr[low] = arr[high];// 使用右边的数字替换左边的数// 2、如果左边的数字比标准数小，则数字不需要移动，low++while (low < high && arr[low] <= stard) {low++;//下标右移}arr[high] = arr[low];}// low、high重合---把标准数赋给低所在的位置的元素arr[low] = stard;// low、high重合---根据low与high所在的下标-处理所有的小的数字-从开始位置~低的位置quickSort(arr, start, low);// low、high重合---根据low与high所在的下标-处理所有的大的数字-从开始位置~高的位置quickSort(arr, low + 1, end);}}}
P22-3.4排序算法之插入排序
认为所有的数字，都是有序的。将数字依次往前移动，一个一个插入到前面的有序序列中！
从第2个数字开始，把之后的数字挨个遍历一遍。遍历的时候，认为前面的数字都是有序的。
在遍历下一个数字的时候，如果该数字比当前数字更小，则将该数字往前移动，直到前面的数字序列有序；
在遍历下一个数字的时候，如果该数字比当前数字更大，则将该数字往后移动，直到已经遍历的数字序列有序。
// 把临时变量（外层for循环的当前元素）赋给不满足条件的后一个元素
arr[j + 1] = temp;
package demo4;import java.util.Arrays;public class InsertSort {public static void main(String[] args) {int[] arr = new int[] { 5, 3, 2, 8, 5, 9, 1, 0 };insertSort(arr);System.out.println(Arrays.toString(arr));}// 插入排序public static void insertSort(int[] arr) {// 遍历所有的数字【从第2个数字开始比较！依次往后比。】for (int i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) { // 如果 当前数字arr[i] 比 前一个数字arr[i - 1] 小int temp = arr[i]; // 1、把当前遍历数字存起来int j;//(内层for循环)遍历当前数字前面所有的数字【temp < arr[j]：当前遍历的数字，要大于temp】for (j = i - 1; j >= 0 && temp < arr[j]; j--) {arr[j + 1] = arr[j]; // 数字后移-把前一个数字赋给后一个数字}// 把临时变量(外层for循环的当前元素)赋给不满足条件的后一个元素arr[j + 1] = temp;}}}}
P23-3.5排序算法之希尔排序
将 数组 分为 4部分，每一部分都进行插入排序！
第1轮步长：4；【9/2 == 4】
第2轮步长：2；【4/2 == 2】
第3轮步长：1。【2/2 == 1】
package demo4;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {int[] arr = new int[] { 3, 5, 2, 7, 8, 1, 2, 0, 4, 7, 4, 3, 8 };System.out.println(Arrays.toString(arr));shellSort(arr);System.out.println(Arrays.toString(arr));}public static void shellSort(int[] arr) {int k = 1;// 遍历所有的步长for (int d = arr.length / 2; d > 0; d /= 2) {// 遍历所有元素for (int i = d; i < arr.length; i++) {// 遍历本组中所有的元素for (int j = i - d; j >= 0; j -= d) {// 如果当前元素大于加上步长后的那个元素if (arr[j] > arr[j + d]) {int temp = arr[j];arr[j] = arr[j + d];arr[j + d] = temp;}}}System.out.println("第" + k + "次排序结果：" + Arrays.toString(arr));k++;}}}
P24-3.6排序算法之选择排序
简单选择排序
标注一个相对较小的数字(x)，依次向后找，找一个 比 此数字(x) 还小的数字，遍历完此数组，将找到的比x小 且 最小的数字，移至最前面。接着从上一个找到的最小的数字，开始往后找，每次只找数组中最小的元素，将其移至前面。一直这样...
从第1个数字，开始往后找。
从第2个数字，开始往后找。
从第3个数字，开始往后找。
把 所有的数字 遍历一遍，有多少数字，便选多少次最小的数字。
package demo4;import java.util.Arrays;public class SelectSort {public static void main(String[] args) {int[] arr = new int[] { 3, 4, 5, 7, 1, 2, 0, 3, 6, 8 };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;// 把当前遍历的数和后面所有的数依次进行比较，并记录下最小的数的下标for (int j = i + 1; j < arr.length; j++) {// 如果后面比较的数比记录的最小的数小。if (arr[minIndex] > arr[j]) {// 记录下最小的那个数的下标minIndex = j;}}// 如果最小的数和当前遍历数的下标不一致,说明下标为minIndex的数比当前遍历的数更小。if (i != minIndex) {int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}}
P25-3.7排序算法之归并排序
package demo4;import java.util.Arrays;public class MergeSort {public static void main(String[] args) {int[] arr = new int[] { 1, 3, 5, 2, 4, 6, 8, 10 };//【3 1】System.out.println(Arrays.toString(arr));mergeSort(arr, 0, arr.length - 1);//【0 0 1】System.out.println(Arrays.toString(arr));}// 归并排序public static void mergeSort(int[] arr, int low, int high) {int middle = (high + low) / 2;if (low < high) {// 处理左边mergeSort(arr, low, middle);// 处理右边mergeSort(arr, middle + 1, high);// 归并merge(arr, low, middle, high);}}public static void merge(int[] arr, int low, int middle, int high) {// 用于存储归并后的临时数组int[] temp = new int[high - low + 1];// 记录第一个数组中需要遍历的下标int i = low;// 记录第二个数组中需要遍历的下标int j = middle + 1;// 用于记录在临时数组中存放的下标int index = 0;// 遍历两个数组取出小的数字，放入临时数组中while (i <= middle && j <= high) {// 第一个数组的数据更小if (arr[i] <= arr[j]) {// 把小的数据放入临时数组中temp[index] = arr[i];// 让下标向后移一位；i++;} else {temp[index] = arr[j];j++;}index++;}// 处理多余的数据while (j <= high) {temp[index] = arr[j];j++;index++;}while (i <= middle) {temp[index] = arr[i];i++;index++;}// 把临时数组中的数据重新存入原数组for (int k = 0; k < temp.length; k++) {arr[k + low] = temp[k];}}}
P26-3.8排序算法之基数排序
大小都有，数字位数不一样！
排序次数，取决于，数组中最大数字的位数！
先找出数组中最大的数字【int max = Integer.MIN_VALUE;】，
将数字转为字符串---计算位数【int maxLength = (max + "").length();】===》确定循环次数。
第1次，按照个位进行排序！
第2次，按照十位进行排序！
第3次，按照十位进行排序！
余数：0~9 ==> 最多需要10个数组
package demo4;import java.util.Arrays;public class RadixSort {public static void main(String[] args) {int[] arr = new int[] { 23, 6, 189, 45, 9, 287, 56, 1, 798, 34, 65, 652, 5 };radixSort(arr);System.out.println(Arrays.toString(arr));}public static void radixSort(int[] arr) {// 存最数组中最大的数字int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}// 计算最大数字是几位数int maxLength = (max + "").length();// 用于临时存储数据的二维数组int[][] temp = new int[10][arr.length];// arr.length 避免 空指针异常// 用于记录在temp中相应的数组中存放的数字的数量int[] counts = new int[10];// 根据最大长度的数决定比较的次数for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {// 把每一个数字分别计算余数for (int j = 0; j < arr.length; j++) {// 计算余数int ys = arr[j] / n % 10;// 把当前遍历的数据放入指定的数组中temp[ys][counts[ys]] = arr[j];// 记录数量counts[ys]++;}// 记录取的元素需要放的位置int index = 0;// 把数字取出来for (int k = 0; k < counts.length; k++) {// 记录数量的数组中当前余数记录的数量不为0if (counts[k] != 0) {// 循环取出元素for (int l = 0; l < counts[k]; l++) {// 取出元素arr[index] = temp[k][l];// 记录下一个位置index++;}// 把数量置为0counts[k] = 0;}}}}}
P27-3.9基数排序之队列实现
先放进去的先取；后放进去的后取。先进先出！！！队列！！！
package demo4;import java.util.Arrays;import demo2.MyQueue;public class RadixQueueSort {public static void main(String[] args) {int[] arr = new int[] { 23, 6, 189, 45, 9, 287, 56, 1, 798, 34, 65, 652, 5 };radixSort(arr);System.out.println(Arrays.toString(arr));}public static void radixSort(int[] arr) {// 存最数组中最大的数字int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}// 计算最大数字是几位数int maxLength = (max + "").length();// 用于临时存储数据的队列的数组MyQueue[] temp = new MyQueue[10];// 为队列数组赋值for (int i = 0; i < temp.length; i++) {temp[i] = new MyQueue();}// 根据最大长度的数决定比较的次数for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {// 把每一个数字分别计算余数for (int j = 0; j < arr.length; j++) {// 计算余数int ys = arr[j] / n % 10;// 把当前遍历的数据放入指定的队列中temp[ys].add(arr[j]);}// 记录取的元素需要放的位置int index = 0;// 把所有队列中的数字取出来for (int k = 0; k < temp.length; k++) {// 循环取出元素while (!temp[k].isEmpty()) {// 取出元素arr[index] = temp[k].poll();// 记录下一个位置index++;}}}}}
多谢观看~~~
数据结构Java03【（时间 空间复杂度） 排序（冒泡 快速 插入 希尔 选择 归并 基数 队列基数）】
