优化常见的java排序算法
作者：保护眼睛 发布时间：2022-03-25 05:11:54
标签：java,优化,排序算法
冒泡排序
冒泡排序的思想：
每次让当前的元素和它的下一个元素比较大小、如果前一个的元素大于后一个元素的话，交换两个元素。
这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素。
那么下次扫描的长度比上次少一个、因为数组的最后一个元素已经是最大的了、即最后一个元素已经有序了。
优化一: 优化的思路就是每一次扫描遍历一次数组、如果某次的扫描之后没有发生数组元素的交换的话、那么说明数组的元素已经是有序的了，就可以直接跳出循环、没有继续扫描的必要了。
优化二：如果数组的尾部已经局部有序的话、那么在经历一次扫描之后的话、就不需要在对尾部局部有序的部分进行扫描了。具体的做法就是记录上一次交换的位置，然后让下一次的扫描到上一次的记录的位置就好了、因为记录的位置后的元素已经有序了。
原始的写法
//常规的写法
public static void bubbleSort1(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
优化一
//优化一
public static void bubbleSort2(int[] array) {
boolean flag = true;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
flag = false;
}
}
if (flag)
break;
}
}
优化二
//优化二
public static void bubbleSort3(int[] array) {
int end = array.length-1;
for (int i = end; i > 0 ; i--) {
int lastIndex = 1;
for (int j = 0; j < end; j++) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
lastIndex = j + 1;
}
}
end = lastIndex;
}
}
选择排序
选择排序的思想也是类似与冒泡排序的思想。再一次扫描之后找打数组当中最大的元素、将最大的元素放在数组的末尾。第二次的扫描数组的时候比上次扫描的长度减一
当然也可以换种思路来实现选择排序—每次扫描数组、然后找出最小的元素、将最小的元素放在数组的首位、下次扫描的时候不在扫描数组的首位、将第二小的元素放在数组第二个位置即可。
方法一
public static void selectSort1(int[] array) {
for (int end = array.length - 1; end > 0; end--) {
int maxIndex = 0;
for (int start = 0; start <= end; start++) {
if (array[maxIndex] < array[start]) {
maxIndex = start;
}
}
int tmp = array[end];
array[end] = array[maxIndex];
array[maxIndex] = tmp;
}
}
方法二
public static void selectSort2(int[] array) {
for (int start = 0; start < array.length; start++) {
int minIndex = start;
for (int end = start; end < array.length; end++) {
if (array[end] < array[minIndex]) {
minIndex = end;
}
}
int tmp = array[minIndex];
array[minIndex] = array[start];
array[start] = tmp;
}
}
堆排序
堆排可以看作是对选择排序的一种优化、将数组原地建成大堆、将最大的元素放在数组的最后一个位置、adjust使数组继续保持大根堆、下一次的交换是和数组的倒数第二个元素进行交换。思路和前面两种排序的算法的思路一致、也是找最值、和数组的首或尾交换、下次交换的时候忽略已经交换的元素。
当然也可以建立一个小堆。堆顶已经是最小的了，那么只需要比较堆顶的左孩子和右孩子的大小即可，左孩子大于右孩子的话、交换、让右孩子adjust保持小堆（因为交换后的右孩子可能不满足小堆）即可。
建大堆来实现堆排
public static void heapSort1(int[] array) {
//建大堆
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown(array, p, array.length);
}
//交换
int end = array.length - 1;
while (end > 0) {
int tmp = array[0];
array[0] = array[end];
array[end] = tmp;
adjustDown(array, 0, end);
end--;
}
}
public static void adjustDown(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
建小堆来实现堆排
public static void adjustDown1(int[] array, int p, int len) {
int child = p * 2 + 1;
while (child < len) {
if (child + 1 < len && array[child] > array[child + 1]) {
child++;
}
if (array[child] < array[p]) {
int tmp = array[child];
array[child] = array[p];
array[p] = tmp;
p = child;
child = p * 2 + 1;
} else {
break;
}
}
}
public static void heapSort2(int[] array) {
//建小堆
for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
adjustDown1(array, p, array.length);
}
//交换
int startIndex = 1;
while (startIndex + 1 < array.length) {
if (array[startIndex] > array[startIndex + 1]) {
int tmp = array[startIndex];
array[startIndex] = array[startIndex + 1];
array[startIndex + 1] = tmp;
adjustDown1(array,startIndex+1,array.length);
}
startIndex++;
}
}
插入排序
插入排序的思想就是类似于打牌的时候，左手拿的排就是有序的、右手拿牌然后将牌与前面的牌进行比较、然后插入到合适位置。
优化一：
优化一的思路就是将比较变为移动，每次拿到元素的时候就要和前面的元素进行比较、数组的逆序对比较多的话、那么每次都要比较和交换、所以我们可以先记录下当前的元素的值、将该元素前面大于该元素的数字都后移一位、然后插入、这样的话比较的和交换的次数就减少了。
优化二:
要在前面的有序的元素中找到当前元素要插入的位置、那么是不是可以使用二分查找来实现呢？所以我们可以使用二分查找来继续优化一下。
实现
public static void insertSort1(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = start;
while (cur > 0 && array[cur] < array[cur - 1]) {
int tmp = array[cur];
array[cur] = array[cur - 1];
array[cur - 1] = tmp;
cur--;
}
}
}
优化一
public static void insertSort2(int[] array){
for (int start = 1; start < array.length; start++) {
int cur = start;
int tmp = array[start];
while (cur>0 && tmp < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
}
优化二
public static void insertSort3(int[] array) {
for (int start = 1; start < array.length; start++) {
int cur = array[start];
int insertIndex = searchIndex(array, start);
for (int i = start; i > insertIndex; i--) {
array[i] = array[i - 1];
}
array[insertIndex] = cur;
}
}
public static int searchIndex(int[] array, int index) {
int start = 0;
int end = index;
while (start < end) {
int mid = (start + end) >> 1;
if (array[index] < array[mid]) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
归并排序
归并排序的思想就是—不断的将当前的序列平均分为2个子序列、直到子序列中的元素的个数为1的时候、然后不断地将2个子序列合并成一个有序的序列。
优化:
可以看到每次归并的时候、申请的额外的数组的大小为左子序列的长度+右子序列的长度（end - start + 1)、归并之后将额外的数组的值赋值到原数组的对应的位置上。
那么我们可以做出优化、可以直接在原数组上进行操作、每次将左子序列的值拷贝出来、和右子序列的值比较、直接覆盖原来的值即可。这样每次申请的额外空间就比原来申请的空间减少一倍。
递归实现归并排序
public static void mergerSortRec(int[] array) {
mergerRec(array, 0, array.length - 1);
}
public static void mergerRec(int[] array, int start, int end) {
if (start >= end) return;
int mid = (start + end) >> 1;
mergerRec(array, start, mid);
mergerRec(array, mid + 1, end);
merger(array, start, mid, end);
}
private static void merger(int[] array, int start, int mid, int end) {
int[] tmpArray = new int[end - start + 1];
int tmpArrayIndex = 0;
int leftStart = start;
int leftEnd = mid;
int rightStart = mid + 1;
int rightEnd = end;
while (leftStart <= leftEnd && rightStart <= rightEnd) {
if (array[leftStart] < array[rightStart]) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
} else {
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
}
while (leftStart <= leftEnd) {
tmpArray[tmpArrayIndex++] = array[leftStart++];
}
while (rightStart <= rightEnd) {
tmpArray[tmpArrayIndex++] = array[rightStart++];
}
for (int i = 0; i < tmpArray.length; i++) {
array[start + i] = tmpArray[i];
}
}
优化
public static void mergerSort(int[] array, int start, int end) {
if (end - start < 2) return;
int mid = (start + end) >> 1;
mergerSort(array, start, mid);
mergerSort(array, mid, end);
merger(array, start, mid, end);
}
private static void merger(int[] array, int start, int mid, int end) {
int[] tmpLeftArray = new int[(end - start + 1) >> 1];
int ls = 0;
int le = mid - start;
int rs = mid;
int re = end;
int arrIndex = start;
for (int i = ls; i < le; i++) {
tmpLeftArray[i] = array[start + i];
}
while (ls < le) {
if (rs < re && array[rs] < tmpLeftArray[ls]) {
array[arrIndex++] = array[rs++];
} else {
array[arrIndex++] = tmpLeftArray[ls++];
}
}
}
来看O(n)的排序
public class ThreadSortDemo {
public static void main(String[] args) {
int[] array = {2, 23, 45, 5, 100, 0, 9};
for (int i = 0; i < array.length; i++) {
new ThreadSort(array[i]).start();
}
}
}
class ThreadSort extends Thread {
private int val;
ThreadSort(int val) {
this.val = val;
}
@Override
public void run() {
try {
Thread.sleep(val);
System.out.print(val + " ");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
当然除了基于比较的排序、还有基于非比较的排序。
计数排序：核心思想就是统计每个整数在序列中出现的次数、进而推导出每个整数在有序序列中的索引。具体的做法就是先找出序列中最大的元素、开辟出最大元素+1的数组空间、统计每个元素出现的次数counts[array[i]]++、然后遍历coutns数组、找出不为0的元素、输出对应的下标即可、也可以将下标重新放回到array数组中，也就是相当于array数组已经排好序了。
基数排序: 将所有元素统一为同样的数位长度， 数位较短的数前面补零。然后， 从最低位开始， 依次进行一次排序，这样从最低位排序一直到最高位排序完成以后, 原数组就变成一个有序序列。
桶排序：创建一定数量的桶、可以使用数组或者链表作为桶、按照一定的规则、将序列中的元素均匀的分配到对应的桶中、然后对每个桶中的元素进行单独的排序、最后将所有非空的桶的元素合并成有序序列。
来源：https://blog.csdn.net/qq_45859087/article/details/118298409
0
投稿猜你喜欢
1.在实体类中添加@TableId注解：2.在navicat中设置id自动增长：3.测试一下，当我们再次插入的时候，就会看到id4.对注解中- 一、前期准备提示：如果友友你没有看过系列一的文章点击这个链接：王者荣耀中一个英雄是怎么被产生的？（一）我们现在功能比较多，所有为了让程序运行
- 一、内部类的概念在 Java 中，可以将一个类定义在另一个类或者一个方法的内部，前者称为内部类，后者称为外部类。内部类也是封装的一种体现。p
- 首先写个单例：public class SingleDemo { private static SingleDemo s =
- 经典的排序算法有八种，分别为：冒泡排序选择排序插入排序归并排序希尔排序快速排序堆排序基数排序其中冒泡排序、选择排序、插入排序称为三大基本排序
- 首先说明这是我一个不熟悉idea和SSM框架的新手小白遇到的坑，适合用idea搭建SSM框架的小伙伴看一看，老鸟就不用看了。以下为详细步骤（
- Java 最初版本只为常用的数据结构提供了很少的一组类：Vector、Stack、Hashtable、BitSet 与 Enumeratio
- spring Boot的学习持续进行中。前面两篇博客我们介绍了如何使用Spring Boot容器搭建Web项目以及怎样为我们的Project
- 打注解@SpringBootTest的时候不会出现提示但是又导入了 <dependency> &nb
- 1. 启动入口本系列RocketMQ4.8注释github地址，希望对大家有所帮助，要是觉得可以的话麻烦给点一下Star哈前面我们已经分析完
- 导语相信大家无论是做前端还是做后端的，都被接口接口文档所折磨过，前端抱怨接口文档和后端给的不一致，后端抱怨写接口文档很麻烦，所以Swagge
- 应用场景有些时候项目中会用到很多路径，并且很可能多个路径在同一个根目录下，那为了方便配置的修改，达到只修改根目录即可达到一改全改的效果，此时
- 前言该篇介绍的内容如题，就是利用redis实现接口的限流（ 某时间范围内 最大的访问次数 ） 。正文 惯例，
- 拆分实现流程请看下面这张图首先我们得对线程池进行一个功能拆分Thread Pool 就是我们的线程池，t1，t2，t3代表三个线程Block
- 前言最近一直被无尽的业务需求淹没，没时间喘息，终于接到一个能让我突破代码舒适区的活儿，解决它的过程非常曲折，一度让我怀疑人生，不过收获也很大
- 概念final 具有“不可改变的”的含义，可以修饰 非抽象类、非抽象成员方法和变量。用 final 修饰的类不能被继承，没有子类。用 fin
- EhCache 是一个纯Java的进程内缓存框架，具有快速、精干等特点，是Hibernate中默认的CacheProvider。ehcach
- 线程池主要解决两个问题：一是当执行大量异步任务时线程池能够提供较好的性能。在不使用线程池时，每当需要执行异步任务时直接new一个线程来运行，
- 目录1. 什么是XSS攻击？2. 如何防范？2.1 什么时候注入请求参数3. 具体处理细节1. 什么是XSS攻击？ &
- 微服务之间token传递问题假设现在有A服务,B服务,外部使用RESTApi请求调用A服务，在请求头上有token字段，A服务使用完后，B服
