时间复杂度和空间复杂度

空间复杂度 用了多少内存
时间复杂度 反应执行效率执行的次数，实际是渐进时间复杂度 n趋于无穷 T(n)/f(n)–> 不为0的常数，同数量级的函数 T(n)=O(f(n)) 大O表达式

如何求得时间复杂度呢？

1.程序运行的次数和要处理的量n的大小没有关系，用常量1表示 O(1).
2.程序运行的次数和要处理的量n的大小有关系,只保留关系函数中的最高阶.比如0.5n^2+0.5n 就是O(n^2)
3.如果高阶项存在，则省去最高阶前面的系数比如0…5n^2+0.5n 就是O(n^2)

	  大O表达式    算法的好坏
	  O(1)         最好         常数间
	  O(logn)      比较好       对数间
	  O(n)         良好         线性间
	  O(n^2)       不好         平方间
	  O(n^3)       很不好       立方间
	  O(2^n)       很很不好     2^n间
	  O(n!)        最不好       阶乘间

时间空间是可以互换的，时间换空间(请求分页)，空间换时间(缓存)

排序算法总结

十大经典排序算法

在这里插入图片描述

冒泡排序

漫画：什么是冒泡排序？

	public static void sort1(int[] arr) {
		int temp = 0;
		for (int i = 0; i < arr.length - 1; i++) { // N个元素比较N-1轮
			for (int j = 0; j < arr.length - 1 - i; j++) { // 最后一位是 arr.length-2 不是 arr.length-1，j和j+1去比
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
			System.out.println(Arrays.toString(arr));
		}
	}

优化

	public static void sort2(int[] arr) {
		int temp = 0;
		for (int i = 0; i < arr.length - 1; i++) {
			boolean isSorteed = true;
			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;
					isSorteed = false;
				}
			}
			if (isSorteed) {
				break;
			}
			System.out.println(Arrays.toString(arr));
		}
	}

优化

		int temp = 0;
		int sortBorder = arr.length - 1;// 无界数据边界 因为是所有轮共用的所以拿到外面来
		int lastExchangeIndex = 0;
		for (int i = 0; i < arr.length - 1; i++) { // N个元素比较N-1轮
			boolean isSorteed = true;
			for (int j = 0; j < sortBorder; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					isSorteed = false;
					lastExchangeIndex = j;
				}
			}
			sortBorder = lastExchangeIndex;
			if (isSorteed) {
				break;
			}
			System.out.println(Arrays.toString(arr));
		}
	}