冒泡排序以及一些优化
冒泡排序以及一些优化
冒泡排序就不必说了，大家都比较熟悉了。本篇的目的就是简单将冒泡排序的算法记录下来，另外还是学习笔记啦，学习这种东西还得记录下来。主要还是有些升级的地方。学习需要保持谦虚。
这里呢，一共要给出三种冒泡的思维
主要思维还是外层控制总体的比赛轮数，内层控制交换次数。
我们的每一轮实现的结果就是将一个最大的的排到最后。每一轮进行额细节就是内层的交换，而内层的交换比较就是实现每轮将最大的元素移到后面的这样的一个过程。
1:常规方案
常规方案就是我们上面说的这个核心思想。我们主要就是实现这么一个过程
1: 外层控制总的比赛的轮数，每轮都会比较出来一个最大的放大后面，那么如果有n个元素，那么就需要比较n-1次，因为比较玩n-1次以后就只剩首个元素了，那么它自然就是最小的排在前面了。
2：然后每轮比较的次数呢，那自然首先元素要肯定比较n-1次才可以筛选出最大的，然后呢，我们要考虑，每一轮我们都会排出一个最大的出来，所以这个比较的元素随着每轮都会减少，那就是n-1-j,j代表轮数。
于是那就是这样的代码
package arithmetic;
/**冒泡排序初步未优化
* @author 兰舟千帆
* @version 1.0
* @date 2022/10/11 8:28
*/
public class Bubble01 {
public static void main(String[] args) {
int arr[] = {22,33,1,4,2,5,7,8,6,10,9};
bubble(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void bubble(int [] arr)
{
for (int i =0;i<arr.length-1;i++)//外层循环控制交换比较的总轮数
{
for(int j =0;j<arr.length-i-1;j++)//内层循环控制交换每轮交换的次数
{
if(arr[j]>arr[j+1])
{
swap(arr,j,j+1);
}
}
}
}
// 定义交换的操作
public static void swap(int[] a,int i,int j)
{
int middle = a[i];
a[i] = a[j];
a[j]=middle;
}
}2:优化方案
但是我们还需要考虑到什么？
给出这样一个数组
int arr[] = {22,33,1,4,2,5,7,8,6,9,10};观察一下，如果本来就存在有序的数字。类似上面给出的，9,10已经排好顺序了。那么我们还需要按照原来的循环轮数和次数去进行冒泡排序吗？
也就是说，在你的循环体中，又可能某轮已经排序好了，但是你还在继续循环，而接下来的循环一轮一轮的根本没有发生交换，也就是说后面的循环不必要。
所以按照这个逻辑我们如何优化
！ 我们可以定义一个变量用来确认每一轮是否发生交换，如果该轮没有元素发生交换，那么我们就不进行循环了，你看是不是很好理解。
所以我们给出这样的代码。可以顺着去理解。
package arithmetic;
/**
* 冒泡排序第一次优化
* @author 兰舟千帆
* @version 2.0
* @date 2022/10/11 9:57
*/
public class Bubble02 {
public static void main(String[] args) {
int arr[] = {22,33,1,4,2,5,7,8,6,9,10};
bubble(arr);
for (int i : arr) {
System.out.println(i);
}
//
}
// 定义一个冒泡的方法
public static void bubble(int arr[])
{
for (int i =0;i<arr.length-1;i++)
{
// 用swap标记是否发生了交换
boolean swap = false; //初始化值
for (int j =0;j<arr.length-1-i;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr,j,j+1);
swap = true;//每轮交换都会记录一下这里发生了交换，如果有一轮没有发生交换的话，这里就不会进行标记交换值
}
}
// 每一轮交换完以后，然后就进行判断，判断该轮是否发生交换，如果没有发生交换，说明已经排好了，就没必要继续进行循环。
if (!swap)
break;
}
}
// 定义一个进行排序交换的方法
public static void swap(int a[],int i,int j)
{
int middle = a[i];
a[i] = a[j];
a[j] = middle;
}
}3:优化方案
其实还有一种优化方案。我们可以直接去控制每轮比较的次数，对于每轮交换，我们记录好最后一次交换位置元素的索引，然后将这个最后元素的索引值作为下次比较的次数。
相比方案二，其实方案二控制了不必要进行循环的轮数，从这个点出发，而本方案从比较元素的次数交换去思考，这样也可以进行优化。
于是我们给出这样的方案
package arithmetic;
/**
* 冒泡排序的终极优化
*
* @author 兰舟千帆
* @version 3.0
* @date 2022/10/11 10:47
*/
//记录每轮最后一次交换的索引用于控制比较次数较少不必要的循环，这里精确控制应该比较的次数,
public class Bubble03 {
public static void main(String[] args) {
int arr[] = {22, 33, 1, 4, 2, 5, 7, 8, 6, 9, 10};
bubble(arr);
for (int i : arr) {
System.out.println(i);
}
}
public static void bubble(int[] arr) {
int n = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
int last =0;//最后一次交换索引的位置
for (int j = 0; j < n; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
// last =j;//记录最后一次索引的位置
}
last =j;//放到这里
}
n =last;
if (n==0)
break;
}
}
public static void swap(int a[], int i, int j) {
int middle = a[i];
a[i] = a[j];
a[j] = middle;
}
}最重要的就是思维逻辑了，简单记录一下。