Java 四大排序
二、选择排序
（1）简单选择排序
排序过程描述
1.拿到一个数 依次与之后的每一个数进行比较 将最小的放在 原来第一的位置
2.拿到第二个数 与之后的进行比较 最小的放在第二的位置
3.第三个数
以此类推 直到最后一个数 排序结束
算法过程描述
1.循环遍历数组i
2.内嵌遍历i之后的数组
3.i 与 j进行大小比较 小的放前
代码实现
public static void selectSort(int[] array){long start = System.nanoTime();int tmp = 0;int key =array.length;for(int i=0;i<key;i++){for(int j=i+1;j<key;j++){if(array[i]>array[j]){ //如果前面的大于后面的tmp=array[i];array[i]=array[j];array[j]=tmp;}}}long end = System.nanoTime();System.out.println("简单选择排序时间"+(end-start)+"纳秒");
}
总结：
1.时间复杂度 O(N²) 嵌套循环遍历两次
2.空间复杂度 O（1）
3.稳定性 不稳定
（2）堆排序
堆排序作为简单排序优化
将一个待排序的数组 看成一个 完全二叉树 利用二叉树的特性进行排序
表示任意一个结点 i 父节点 i==0?null:(i-1)/2
左孩子 2i+1
右节点 2i+2
排序过程描述
1.将array[] 抽象为一根堆结构
调整结构变为 整体大根堆 每一个节点 大于子节点
2.调整整棵树为大根堆
(1)从这个大树的最后一个小树开始 一次向上调整 树结构
3.第一次拿到i=(array.length-1-1)/2 表示最后一个小树的父节点也就是 父节点为2的位置
（1）调整进入这个小树 将父节点存入 tmp 中 从左子节点 5 开始与右孩子进行比较拿到其中最大的下标
因为子节点只有一个无须比较 只需要父节点进行比较
（2）因为结束的条件是 i<=end 所以这个树的子节点还有树也会依次进入 直到将父节点排为这棵小树的最大值
4.调整完大根堆之后
（1）那么此时这棵树的顶元素此时为最大值 与最后一个元素交换 然后再调整数将倒数第二大拿到顶 ，执行完毕排好顺序
排序算法描述
1.从树的最后一颗小树开始拿元素
for(int i = (key-1-1)/2;i>=0;i–){
adjust(array,i,key-1); //adjust调整的为响应的树i树顶
}//整棵树变为 大根堆 时间复杂度 Nlog2(n)
2.adjust 函数
调整这个树开始向下的所有树的结构 保证都为大根堆
3.每一次将树顶元素移到最后都要调整其余树的结构为大根堆
代码实现
public static void heapSort(int[] array){long start = System.nanoTime();int key=array.length;for(int i = (key-1-1)/2;i>=0;i--){adjust(array,i,key-1);}//整棵树变为 大根堆 时间复杂度 Nlog2(n)//调换 最后的位置for (int j = 0; j <=key-1 ; j++) {int tmp = array[0];array[0]=array[array.length-1-j];array[array.length-1-j] = tmp;adjust(array,0,array.length-1-j-1); //先交换 在调整 所以 -1 不用调换最后一个树}long end = System.nanoTime();System.out.println("堆排序的时间"+(end-start)+"纳秒");
}
public static void adjust(int[] array,int start,int end){int tmp = array[start];for(int i=2*start+1;i<=end;i=2*i+1){if((i<end)&&(array[i]<array[i+1])){ //比较两个兄弟节点 大小 拿到最大的角标i++; //i++保存最大值下标}if(array[i]>tmp){array[start] = array[i];start=i; //【核心】让这从颗树开始所有子数都进入被调整}else if(array[i]<tmp){// array[start]=tmp; break之后 有 重复执行所以去掉break;}}array[start]=tmp; //走完 for 有一个交换完的 位置是空的 用tmp填
}
总结
1.时间上 排100000个数所需要时间
有序
堆排序的时间12599995纳秒
无序
堆排序的时间14118216纳秒
2.空间复杂度 O（1） 因为申请了一个 tmp的空间
3.稳定性 不稳定