冒泡排序和优化

冒泡排序作为一种交换排序方法，可以实现降序和升序。

优化：去除排序完成后的,轮数空转时间（bubblingSortx方法）

/**

 * 冒泡算法，用于排序:

 9 8 7 6 5 4 3 2 1

 比较轮数，每一轮比较次数，每一次将相邻的两个数进行比较。

 第一轮:

 第1次：8 9 7 6 5 4 3 2 1

 2：8 7 9 6 5 4 3 2 1

 3：8 7 6 9 5 4 3 2 1

 4: 8 7 6 5 9 4 3 2 1

 5: 8 7 6 5 4 9 3 2 1 

 6：8 7 6 5 4 3 9 2 1

 7：8 7 6 5 4 3 2 9 1

 8: 8 7 6 5 4 3 2 1 9 

 ①.1轮比较，获得最大数(位置固定)。

 ②.N个数，比较N-1轮(因最小的数,最后一次的上一次已确定,无需再比较) 

 ③.每轮比较次数，第i轮比较，n-i

 ④.思路：从开头进行排序，依次对相邻的两个元素进行比较，大的值后移(此值下次作为比较的前元素)，每次确定一个比较的最大值移到最后，下一次比较的长度将减1.

 ⑤.规则：N个元素进行排序，总共N-1轮，第一轮比较N-1次；第二轮,比较N-2次；第i轮比较N-i次。

 注:因计算机计数从0开始,所以轮数和次数都减1，也可从1开始。 "小于"其实已经减1

 双层循环，外循环控制轮数，内循环控制每轮的次数

 * */

代码如下(可删除，count1st和count两个多余日志参数)：

package com.ts.w;

 * 冒泡排序

 * @author tskk

 * @version 2015-6-30 11:01:54

 * */

public class BubblingSort {

 public static void main(String[] args) {

 System.out.println("***排序最坏情况***");

 int [] preArray = {9,8,7,6,5,4,3,2,1};

 System.out.println("预比较数为:"+"9 8 7 6 5 4 3 2 1");

 bubblingSort(preArray);

 System.out.println();

 int [] preArray1 = {9,8,7,6,5,4,3,2,1};

 System.out.println("预比较数为1:"+"9 8 7 6 5 4 3 2 1");

 bubblingSortx(preArray1);

 System.out.println();

 System.out.println("***排序非最坏情况***");

 int [] preArray2 = {3,2,1,4,5,6,7,8,9};

 System.out.println("预比较数为2:"+"3 2 1 4 5 6 7 8 9");

 bubblingSort(preArray2);

 System.out.println();

 int [] preArray3 = {3,2,1,4,5,6,7,8,9};

 System.out.println("预比较数为3:"+"3 2 1 4 5 6 7 8 9");

 bubblingSortx(preArray3);

 public static int[] bubblingSort(int [] num){

 if(num == null){

 return null;

 int numLen = num.length;

 int temp = 0;

 int count = 0;

 int count1st = 0;

 for(int i = 0; i numLen - 1; i++){//比较轮数

 for(int j = 0;j numLen - i - 1; j++){

 if(num[j] num[j + 1]){//此处调整为小于,修改后,可做降序排序

 temp = num[j];

 num[j] = num[j + 1];

 num[j + 1] = temp;

 count++;

 count1st++;

 System.out.println("bubblingSort比较轮数为:"+count1st);

 System.out.println("bubblingSort比较次数为:"+count);

 System.out.print("bubblingSort比较结果为:");

 for(int i = 0; i numLen; i++){

 System.out.print(" "+num[i]);

 return num;

 * 优化：去除排序完成后的,轮数空转时间

 * */

 public static int[] bubblingSortx(int [] num){

 if(num == null){

 return null;

 int numLen = num.length;

 int temp = 0;

 int count = 0;

 int count1st = 0;

 int count2nd = 0;

 for(int i = 0; i numLen - 1; i++){//比较轮数

 count2nd = 0;//每轮从0开始

 for(int j = 0;j numLen - i - 1; j++){

 if(num[j] num[j + 1]){//此处调整为小于,修改后,可做降序排序

 temp = num[j];

 num[j] = num[j + 1];

 num[j + 1] = temp;

 count++;

 count2nd++;//如果,某轮,没有交换发生(count2nd=0),说明:此时,排序已完成

 count1st++;

 if(count2nd == 0){

 break;

 System.out.println("bubblingSortx比较轮数为:"+count1st);

 System.out.println("bubblingSortx比较次数为:"+count);

 System.out.print("bubblingSortx比较结果为:");

 for(int i = 0; i numLen; i++){

 System.out.print(" "+num[i]);

 return num;

输出结果为：

***排序最坏情况***

预比较数为:9 8 7 6 5 4 3 2 1

bubblingSort比较轮数为:8

bubblingSort比较次数为:36

bubblingSort比较结果为: 1 2 3 4 5 6 7 8 9

预比较数为1:9 8 7 6 5 4 3 2 1

bubblingSortx比较轮数为:8

bubblingSortx比较次数为:36

bubblingSortx比较结果为: 1 2 3 4 5 6 7 8 9

***排序非最坏情况***

预比较数为2:3 2 1 4 5 6 7 8 9

bubblingSort比较轮数为:8

bubblingSort比较次数为:3

bubblingSort比较结果为: 1 2 3 4 5 6 7 8 9

预比较数为3:3 2 1 4 5 6 7 8 9

bubblingSortx比较轮数为:3

bubblingSortx比较次数为:3

bubblingSortx比较结果为: 1 2 3 4 5 6 7 8 9

注：一般排序并非，最坏排序，所有，以上以节省5次空转。

优化测试演示：冒泡优化测试(1百万元素排序)

算法——冒泡排序及实现 终于我们迎来了算法的章节，是最激动人心的章节， 更多可能得自己去线下模拟这样一些过程，对于考研的同学堆排序、快速排序、归并排序是重难点，要能动手模拟过程以及复杂度等，通常用选择题的形式考察不同算法之间的对比，一些常用的排序算法的关键代码，要达到编写的程度，要能达到选择最优算法的能力。大家一起加油，将数据结构斩于马下。笔者在这也只会讲一些常用的排序算法。在代码的实现部分，可以选择自己喜欢的语言。