排序算法
Sort Algorithm
常见排序分类
### 常见排序：
直接插入排序
希尔排序
简单选择排序
堆排序
冒泡排序
快速排序
排序算法
定义
将一组数据，按照指定的顺序进行排列的过程。
分类
内部排序
将需要处理的所有数据 加载到 内部存储器（内存） 进行排序。
外部排序
数据量大，无法全部加载到内存中，需要借助外部存储等文件进行排序。
算法时间复杂度
衡量一个程序or算法执行的时间长度。
时间频度
一个算法 花费的时间 和 算法中语句的执行次数 成正比。
语句执行次数 ； 语句频道，or，时间频度。
T(n)。
eg: 举例对比时间频度
常数项可以忽略
低次项也可以忽略
系数也可以忽略
时间复杂度
算法中的 基本操作语句的 重复执行次数 是 问题规模n的某个函数。
时间复杂度的计算
常见的时间复杂度
常数阶O(1)
对数阶O(log2N)
比如说 n = 1024
那么·这个循环 i = i * 2 执行10次就可以了。
线性阶O(N)
线性对数阶 O(nlogN)
平方阶O(N^2)
双重for 循环
立方阶O(N3 ) K次阶段
参照平方阶
一次增加for循环就好
O（n^3）相当于三层n循环
平均时间复杂度 和 最坏时间复杂度
平均时间复杂度： 所有可能的输入实例 均 以等概率 出现的情况下， 该算法的运行时间。
最坏时间复杂度： 最坏情况下，算法的时间复杂度。
希尔排序 介于 n 和 n^2 之间
空间复杂度
一个算法的空间复杂度： 该算法 所耗费的存储空间。 问题规模n的函数。
空间复杂度 space complexity
算法在运行过程中 临时占用存储空间大小 的度量。
冒泡排序
Bubble Sorting
一个图解
具体举例子
图解冒泡排序算法
原始数组 3 9 -1 10 20
从小到大进行排序
第一趟排序：
比较 3 9 不交换
比较 9 和 -1 交换
3 -1 9 10 20
9 和 10
10 和 20
第一趟结束，确立 最大的数 20
第二趟排序：
3 和 -1 交换
3 和 9
9 和 10
第二趟结束， 确立 最大数 10 和 20
第三趟排序：
-1 和 3
3 和 9
第三趟排序结束， 确立最大数 9 10 20
第四趟排序：
第四趟排序结束， 确立最大数 3 9 10 20
小结：
一共进行 数组大小-1 次 的循环
每一趟 排序的次数在 逐渐减少
如果发现 在某趟排序中， 没有发生1次交换，可以提前结束冒泡排序。
package sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
//
int[] arr = {3, 9, -1, 10, -2};
// 有5个元素，需要进行4次比较
/*
第一趟排序，将最大的数排在最后
四次比较
*/
int temp = 0;
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.print("第一趟排序后的数组: ");
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.print("第二趟排序后的数组: ");
System.out.println(Arrays.toString(arr));
// 第三趟排序
for (int j = 0; j < arr.length - 1 - 1 - 1; j++){
// 如果前面的数 大于 后面的数 就交换
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print("第三趟排序后的数组: ");
System.out.println(Arrays.toString(arr));
// 第四趟排序
for (int j = 0; j < arr.length - 1 - 1 -1 -1; j++){
// 如果前面的数 大于 后面的数 就交换
if (arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print("第四趟排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}
第一趟排序后的数组: [3, -1, 9, -2, 10]
第二趟排序后的数组: [-1, 3, -2, 9, 10]
第三趟排序后的数组: [-1, -2, 3, 9, 10]
第四趟排序后的数组: [-2, -1, 3, 9, 10]
整理代码
package sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
//
int[] arr = {3, 9, -1, 10, -2};
// 有5个元素，需要进行4次比较
int temp = 0;
for (int i = 1; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i; j++) {
// 如果前面的数 大于 后面的数 就交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.print("排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}
```java
排序后的数组: [-1, -2, 3, 9, 10]
时间复杂度 应该是 n的平方。
代码优化
```java
package sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
//
// int[] arr = {3, 9, -1, 10, 8};
int[] arr = {1, 2, 3, 4, 5};
// 有5个元素，需要进行4次比较
int temp = 0;
boolean flag = false; // 表示是否进行过交换
for (int i = 1; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i; j++) {
// 如果前面的数 大于 后面的数 就交换
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.printf("第%d次排序后的数组: ", i);
System.out.println(Arrays.toString(arr));
if (flag == false){ // 说明1次交换都没有发送
break;
} else {
flag = false; // 重置flase 进行下次判断
}
}
System.out.print("排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}
封转 + 时间显示
package sort;
import java.text.SimpleDateFormat;
import java.util.Date;
public class BubbleSort {
public static void main(String[] args) {
// 测试冒泡排序
// 速度 O(n^2) 给8w个随机数据测试
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++){
arr[i] = (int)(Math.random() * 800000); // shengcheng[0,80000)区间随机数
}
// System.out.println("排序前：" + Arrays.toString(arr));
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
String data1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间: " + data1Str);
bubbleSort(arr);
// System.out.println("排序后: " + Arrays.toString(arr));
Date data2 = new Date();
SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
String data2Str = simpleDateFormat2.format(data2);
System.out.println("排序后的时间: " + data2Str);
}
// 封装冒泡排序
public static void bubbleSort(int[] arr) {
int temp = 0;
boolean flag = false; // 表示是否进行过交换
for (int i = 1; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i; j++) {
// 如果前面的数 大于 后面的数 就交换
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// System.out.printf("第%d次排序后的数组: ", i);
// System.out.println(Arrays.toString(arr));
if (flag == false) { // 说明1次交换都没有发送
break;
} else {
flag = false; // 重置flase 进行下次判断
}
}
// System.out.print("排序后的数组: ");
// System.out.println(Arrays.toString(arr));
}
}
排序前的时间: 2022-04-07 22:58:20
排序后的时间: 2022-04-07 22:58:33
冒泡总结
n个元素 冒泡
需要进行n-1个循环次数
依次比较相邻两个数，大的往后移动。
改进：
当发现有一趟循环下来，没有进行交互，说明顺序已经排好了。
