一、分类
比较类排序
通过比较决定次序，时间复杂度不能突破O（nlogn）
非比较类排序
不通过比较决定次序，时间复杂度能突破O（nlogn）
二、算法的时间和空间复杂度
算法稳定性
经过排序之后，原本值相同的两个数的位置不会发生变化
算法的 时间复杂度
算法中语句执行的次数，即语句频度或时间频度,记作
$$
T(n)
$$
f(n)是某个辅助函数，n=>无穷，T（n）/f(n)极限值为不为0的常数，则f(n)是T(n)的同数量级函数记作
$$
T(n)=O（f(n)）(时间渐进复杂度，即时间复杂度)
$$
常数项可以忽略
低次项可以忽略
对于偶数方项，系数可以忽略，对于奇数方项，系数不可以忽略，会分开，比例是系数比
算法的时间复杂度
避免算法的 时间复杂度指数爆炸
常见的时间复杂度
常数阶O(1)
无论多少行，没有循环等复杂结构
对数阶
$$
T(n)=\log_2（具体情况而定 ）{n}
$$
int i=1;
while(i<n){
i=i*2
}
//n=1024 的时候，执行了2de10次方，2de10次方=1024 10=log2 1024
线性阶 –单层的for循环
$$
O(n)
$$for (int i = 0; i < maopao.length; i++) { System.out.println(maopao); } //时间频度T（n）=n+1 ==》O(n)线性对数阶 –将时间复杂度为log2（具体情况而定 ）{n}的代码块循环 了n遍
$$
O（n\log_2{n})
$$for (int i = 1; i < maopao.length; i++) { while(i<n){ i=i*2 } }平方阶 –双层for循环
$$
O(n;^2)
$$int n = 100; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println(j + i); } }
平均时间复杂度和最坏时间复杂度
算法的空间复杂度 –算法所耗费的存储空间
三、冒泡排序
规则
n个元素只需要就行n-1趟排序。
每一趟排序次数逐渐减少
优化：如果某趟排序中没有发生一次交换，可以提前结束排序
package order.maopao;
import java.util.Arrays;
public class Maopao {
public static void main(String[] args) {
int[] maopao = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 9, 9, 9};
bubbleSort(maopao);
System.out.println(Arrays.toString(maopao));
}
//冒泡排序
public static void bubbleSort(int[] maopao) {
boolean flag = false;
//第一层循环，控制的是比较的 趟数 即数组长度减一次 n-1
for (int i = 1; i < maopao.length; i++) {
//长度是 9 一趟比较最多比较到 长度-趟数的前一位（第一趟比较j的下标倒数第二个就行了）（即第一趟比较的时候）
for (int j = 0; j < maopao.length - i; j++) {
if (maopao[j] > maopao[j + 1]) {
int temp = maopao[j];
maopao[j] = maopao[j + 1];
maopao[j + 1] = temp;
flag = true;
}
}
System.out.println("第" + i + "趟的数组" + Arrays.toString(maopao));
if (!flag) {
//在一次排序中，一次 交换 都没有发生
break;
} else {
//重置flag!!!!!!!，进行下次的判断
flag = false;
}
}
}
}
四、选择排序
一种内部排序法，从欲排序的数据中，按照指定的规则选出某元素，再依照规定交换位置之后达到排序的目的。
//选择排序
public static void selectSort(int [] array){
int minindex=0;//最小值的下标
for (int i = 0; i < array.length-1; i++) {
//执行length-1趟的比较
int min=array[i];//假定最小值是第i个元素
for (int j = i+1; j < array.length; j++) {
//让假定的那个最小值 依次去和 [i+1,length-1(最后一个元素)]去比较，若遇见更小的，就将那个更小的值的角标和值记下来
if (min>array[j]){
min=array[j];//记下最小值
minindex=j;//记下最小值的角标
}
}
//内层循环完毕（一趟比较），取得最小值及其角标，将最小值与假定的那个最小值交换位置
array[minindex]=array[i];
array[i]=min;
}
System.out.println(array);
}
五、插入排序
概念：属于内部排序法，对于欲排序的元素以插入的方式找寻该元素的位置
基本思想：把表分为一个有序表和无序表，刚开始的时候有序表只有一个元素，之后依次从无序表里面取出一个元素与有序表的排序码进行比较，将其插入到有序表的适当位置。
图解
//插入排序 public static void insertSort(int[] array) { int insertValue = 0;//要插入的值 int insertIndex =0;//要插入的坐标 for (int i = 1; i < array.length; i++) { insertValue = array[i]; insertIndex = i - 1; //insertIndex>=0防止越界 //insertValue<array[insertIndex] while (insertIndex >= 0 && insertValue < array[insertIndex]) { array[insertIndex + 1] = array[insertIndex];//插入位置的值向后移一位 insertIndex--;// 插入值小于插入位置（插入值坐标前一位）的值， 插入位置回退1 //{101,34,119,1} 34<101 -->101的值移到34的位置上面,插入的位置减一 } //退出while循环，说明插入的位置找到了 即insertIndex + 1 array[insertIndex + 1] = insertValue; } }
小问题：当插入的数较小的时候，后移的次数明显增多
六、希尔排序（更高效的插入排序）
思想：
将记录按增量分组，对每组使用直接插入排序算法排序，套娃到增量为1就🆗了。
交换法
//Shell排序 交换法
public static void shellSort(int[] array) {
// int [] arr={8,9,1,7,2,3,5,4,6,0};
int temp = 0;
int count = 0;
//逐步推导
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {//i=5,2,1
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长之后的那个元素，说明交换
if (array[j] > array[j + gap]) {
temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
count++;
System.out.println("希尔排序第" + count + "轮:" + Arrays.toString(array));
}
}
移动法 真牛逼八百万随机数据的排序 3.9秒就欧克了
//Shell排序 交换法优化 --> 移位法
public static void shellSortNew(int[] array) {
for (int gap = array.length / 2; gap > 0; gap /= 2) {
//从第gap个元素开始逐个对其所在的组 进行直接插入
// int i;
for (int m = gap; m < array.length; m++) {
int j = m;//待插入的位置
int temp = array[j];//记录要插入的值
if (array[j] < array[j - gap]) {
//当前元素比减去步长的那个元素小
while (j - gap >= 0 && temp < array[j - gap]) {
//移动 将更大的那个数移到步长
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
}
}
七、快速排序（对冒泡的改进）
