冒泡排序太长？

Question

下面是我执行冒泡排序的代码：

public static void bubbleSortByLength() {
    boolean flag = true;
    String temp;
    for (int i = numNames - 1; i > 0; i--) {
        flag = false;
        for (int j = 0; j < i - 1; j++) {
            if (names[j].length() > names[j + 1].length()) {
                temp = names[j];
                names[j] = names[j + 1];
                names[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag)
            return;
    }
}

与我见过的其他冒泡排序迭代相比，它相当慢。有人知道我怎么能让它更快吗？

Answer 1

我建议的第一件事是创建自定义Comparator来作为排序实现的基础。给定您的String长度的主要标准，我将使用如下内容

static class StringLengthComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        if (o1.length() == o2.length()) {
            return o1.compareTo(o2);
        }
        return Integer.compare(o1.length(), o2.length());
    }
}

我建议的下一件事是基于更好的排序算法来实现一些东西。Quicksort和Mergesort通常是O(nlog n)的(尽管Quicksort通常在排序的输入上有病态情况，这会导致O(n^2)行为)。接下来，为了更容易阅读，我建议您将swap提取到一个方法中。喜欢,

static void swap(String[] arr, int a, int b) {
    if (a == b) {
        return;
    }
    String t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

然后，您可以使用上面的Comparator和swap方法实现冒泡排序

public static void bubbleSortByLength(String[] names) {
    int numNames = names.length;
    StringLengthComparator c = new StringLengthComparator();
    for (int i = 0; i < numNames - 1; i++) {
        boolean swappedFlag = false;
        for (int j = 1; j < numNames - i; j++) {
            if (c.compare(names[j - 1], names[j]) > 0) {
                swappedFlag = true;
                swap(names, j - 1, j);
            }
        }
        if (!swappedFlag) {
            break;
        }
    }
}

Answer 2

**高级快速冒泡排序**

        /*Advanced BUBBLE SORT with ONE PASS*/
/*Authored by :: Brooks Tare  AAU*/

public class Bubble {

    public int[] bubble(int b[]){ 
    int temp=0; 

    for(int i=0;i<b.length-1;i++){

            if(b[i]>b[i+1] ){
                ///swap(b[i],b[i+1]);

                temp=b[i];
                b[i]=b[i+1];
                b[i+1]=temp;

    /*Checking if there is any number(s) greater than 
      the current number. If there is swap them.*/
                while(i>0){


                    if(b[i]<b[i-1]){
                    ///swap(b[i]<b[i-1])
                        int temp1;
                        temp1=b[i];
                        b[i]=b[i-1];
                        b[i-1]=temp1;
                        i--;
                    }
                    else if(b[i]>b[i-1]){i--;}
                }
            }
            else{continue;}

        }



        return b;
    }
///the following is a function to display the Array 
        public void see(int []a){
            for(int j=0;j<a.length;j++){
                System.out.print(a[j]+",");
            }
        }



    public static void main(String []args){
        ///You can change the Array to your preference.. u can even make it dynamic 

        int b[]={5,1,4,2,0}; 
        int v[]=new int[100]; 
        Bubble br=new Bubble();
        v=br.bubble(b);
        br.see(v);

        }
    }