淺析java雙向冒泡排序算法

2019-11-26 15:18:29

字體：大中小

來源：轉載

供稿：網友

以整數升序排序為例來簡單說明一下雙向冒泡排序的過程：首先從前往后把最大數移到最后，然后反過來從后往前把最小的一個數移動到數組最前面，這一過程就是第一輪，然后重復這一過程，最終就會把整個數組從小到大排列好。雙向冒泡排序要稍微優于傳統的冒泡排序，因為雙向排序時數組的兩頭都排序好了，我們只需要處理數組的中間部分即可，而單向即傳統的冒泡排序只有尾部的元素是排好序的，這時每輪處理都需要從頭一直處理到已經排好序元素的前面一個元素。雖然它在效率上有了點改進，但它也不能大幅度提高其排序的效率，這是由冒泡排序的基本過程所決定了的。在此基礎上改進了一下，下面的代碼可以實現對奇數偶數分別排序

雙向冒泡排序源代碼：

復制代碼代碼如下:

package com.zc.manythread;
import java.util.Random;
/**
 * 雙向冒泡排序
 * @author 偶my耶
 *
 */
public class BBSort  {
    //雙向冒泡算法，極大的減少了循環排序的次數
    public int[] sort(int[] a)throws Exception{
        int j;
        int limit=a.length;
        int st=-1;
        while(st<limit){
             //必須要給st和limit賦值，否則若數組一開始就有序
            st++;
            limit--;
            boolean swapped=false;
            //第一次循環將最大的值放到末尾
            for (j = st    ; j < limit; j++) {
                 if (a[j]>a[j+1]) {
                    int T=a[j];
                    a[j]=a[j+1];
                    a[j+1]=T;
                    swapped=true;
                }
            }
            if (!swapped) {
                return a;
            }else {
                swapped=false;
                //第二次循環將最小的值放到了開頭
                for (j = limit; --j>=st;) {
                    if(a[j]>a[j+1]){
                        int T=a[j];
                        a[j]=a[j+1];
                        a[j+1]=T;
                        swapped=true;
                    }
                }
                if (!swapped) {
                    return a;
                }
            }
        }
        return a;
    }
    private static int[]  createDate(int count) {
        /**
         * 無重復數組
         */
        int[] data=new int[count];
          Random rand = new Random();
          boolean[] bool = new boolean[100];
          int num = 0;
          for (int i = 0; i < count; i++) {
           do {
            // 如果產生的數相同繼續循環
            num = rand.nextInt(100);
           } while (bool[num]);
           bool[num] = true;
        /*   list.add(num);*///list 列表
           data[i]=num;
          }
          return data;
    }
public static void main(String[] args) {
    final int count=10;
    int[] data=createDate(count);
    for(int n : data){
           System.out.print(n+"/t");
        }
    System.out.println();
    BSrot bsrot=new BSrot(data);
    try {
    int[] a=bsrot.sort(data);
    for(int n : a){
           System.out.print(n+"/t");
        }
    } catch (Exception e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}
}