关于数组冒泡排序的一个问题,请教一下各位高人.冒泡排序中能否引入变量来减少数组元素交换的次数提高效率?

Question

/*
演示冒泡排序
*/
class  BubbleSortDemo
{
public static void main(String[] args) 
{
{
int[] arr = new int[]{2,34,53,24,15,16,78,15,23,56,2};
bubbleSort(arr);
arrErgodic(arr);
} System.out.println("--------------华丽丽的分割线-------------------"); {
int[] arr = new int[]{2,34,53,24,15,16,78,15,23,56,2};
bubbleSort_2(arr);
arrErgodic(arr);
} System.out.println("--------------华丽丽的分割线-------------------"); {
int[] arr = new int[]{2,34,53,24,15,16,78,15,23,56,2};
bubbleSort_3(arr);
arrErgodic(arr);
}
} /*
定义一个功能函数,用于对int数组进行冒泡排序
1.返回值类型 Void 排序前后指向同一个数组,无返回值.
2.参数列表: 参与排序的数组 int[]
*/
public static void bubbleSort(int[] arr)
{
for (int x=0;x<arr.length-1;x++)//不必取到最后一次拿自己跟自己比较所以-1
{
for (int y=0;y<arr.length-1-x ;y++ )//-1是为了防止越界,-x是为了随着外循环次数的增加,内循环参与比较的元素递减.
{
if(arr[y]>arr[y+1])//注意不要引起越界
{
changeNum(arr,y,y+1);
}
}
} return;
} //冒泡排序另一种写法,功能和原理相同
public static void bubbleSort_2(int[] arr)
{
for (int x=arr.length-1;x>0;x--)//倒着取,同样不许要取到第一个,外循环只是用来控制整体循环次数.
{
for (int y=0;y<x ;y++ )//x本身已经是arr.length-1了,而且x在不断递减,因此效果跟上变函数一样,只是写法不同
{
if(arr[y]>arr[y+1])
{
changeNum(arr,y,y+1);
}
}
} return;
}
//尝试在方法1上看能否加变量进去以减少交换次数  逻辑没想通,暂时失败........!!!!!!!!!!!
public static void bubbleSort_3(int[] arr)
{
for (int x=0;x<arr.length-1;x++)//不必取到最后一次拿自己跟自己比较所以-1
{
int num = arr[0];
int index = 0;
for (int y=0;y<arr.length-1-x ;y++ )//-1是为了防止越界,-x是为了随着外循环次数的增加,内循环参与比较的元素递减.
{
if(arr[y]<arr[y+1])//注意不要引起越界
{
num = arr[y+1];
index = y+1;
}
} changeNum(arr,index,arr.length-1-x);
} return;
} //定义一个功能函数来遍历数组并打印到控制台
public static void arrErgodic(int[] arr)
{
for (int x=0;x<arr.length;x++ )
{
System.out.println("arr["+x+"]\t= "+arr[x]+";");
} return;
}
/*
定义一个功能函数将数组两元素交换位置的功能提取出来单独封装方便调用.
1.返回值类型void,对数组操作,前后指向的都是同一个数组,无需返回值.
2.参数列表:需要进行元素交换的数组 int[].需要交换的两个元素的角标 int.
*/
public static void changeNum(int[] arr, int x, int y)
{
//位置交换 位运算法
arr[x]=arr[x]^arr[y];
arr[y]=arr[x]^arr[y];
arr[x]=arr[x]^arr[y]; /*位置交换 第三方变量法(常规用法)
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
*/ return;
}
}脑子转筋了,bubbleSort_3函数逻辑想不通了,不知道能不能实现通过加入变量记录下每次比较后的结果,到外循环一轮结束后只进行一次数组中的数据交换.请各位高人指教一下,能不能这么做,这个函数怎么调整一下才能够实现冒泡排序.冒泡排序提问

Answer 1

每次比较后不冒一个泡还叫冒泡排序吗，非要引入变量减少次数的话，不如直接用选择排序呢：
public static void selectionSort1(int[] a){//选择排序优化
   int k,temp;
   for(int i=0;i<a.length;i++){
    k=i;
    for(int j=k+1;j<a.length;j++){
     if(a[k]>a[j]){ 
       k=j;
     }
    }
    if(i!=k){
     temp = a[i];
     a[i] = a[k];
     a[k] = temp;
    } 
   }
  }
楼主还是不要纠结了吧，排序算法都有自己的特征，改变太多就不是这个排序方法了