冒泡排序-Java版

  • 作者: 凯哥Java
  • 算法刷题
  • 时间:2020-11-01 16:07
  • 1077人已阅读
简介 冒泡排序的思路:循环数组,比较两个相邻的数据大小,大的放在右变。array[j]>arrar[j+1]:inttemp=array[j];array[j+1]=array[j];array[j]=temp;需要使用到两个for循环:外层循环是循环数组中所有数据,内层循环是进行比较的。所以外层循环的长度是:array.length-1内层循环的长度是:array.leng-1-i./***冒泡

冒泡排序的思路:

循环数组,比较两个相邻的数据大小,大的放在右变。

array[j]>arrar[j+1]:

int temp = array[j];

array[j+1] = array[j];

array[j] = temp;

需要使用到两个for循环:

外层循环是循环数组中所有数据,内层循环是进行比较的。所以外层循环的长度是:array.length-1

内层循环的长度是:array.leng-1-i.


/**
* 冒泡排序
* 思路:
*  循环两个相邻的数进行比较,大的放到右边。
*  依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。重复第一趟步骤,直至全部排序完成。
*  第一趟比较完成后,最后一个数一定是数组中最大的一个数,所以第二趟比较的时候最后一个数不参与比较;
* 第二趟比较完成后,倒数第二个数也一定是数组中第二大的数,所以第三趟比较的时候最后两个数不参与比较;
* 依次类推,每一趟比较次数-1
*
* 所以,需要两个for循环
* 外层for循环用是用来循环整个数组的,所以循环的次数是:array.length-1
* 内循环是用来比较的,而内循环比较的次数是:array.length-1-i.这里为什么需要减去i?
* 那是因为,第一趟之后,最后一个数不会参与比较了,第二趟之后,最后两个数不会参与比较了。所以要减去i.
* 然后在内循环进行比较:
* 比较 array[j]array[j+1]的大小。然后进行互换
*
*/

 代码:

/**
 * 冒泡方法
 * @param array     需要排序的数组
 * @return          返回排序后的数组
 */
public static  void bubbleSortFunction(int []  array){
    for (int i =0;i<array.length-1;i++){
        for(int j = 0 ;j<array.length-1-i;j++){
            //进行比较
            //当j<j+1 这种是倒叙的
           // if(array[j]<array[j+1]){
            //正序
            if(array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1]  = temp;
            }
        }
    }
}

优化版:

设置一个标识,如果没有触发变化,就不循环了。优化后代码:

/**
 * 优化版的
 * @param array
 */
public static void bubbleSortPlusFunction(int [] array){
    Boolean flag = false;
    for(int i =0;i<array.length-1;i++){
        for (int j = 0;j<array.length-1;j++){
            if(array[j]>array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
}

测试:

public static void main(String[] args) {
    int [] array = new int []{1,10,2};
    bubbleSortPlusFunction(array);
   for(int data:array){
       System.out.println(data);
   }
}

运行结果:

d853efde6fef4ab2c4527db2d61d9cb2.png

Top Top