JavaScript BubbleSort, how to improve its efficien

问题:

Have a bubblesort routine similar to this. I need to make it more efficient by stopping the loop when the array is sorted or if the array is already sorted.

function sortNumbers(listbox) {
  var x, y, holder;
  // The Bubble Sort method.
  for(x = 0; x < ranarray.length; x++) {
    for(y = 0; y < (ranarray.length-1); y++) {
      if(ranarray[y] > ranarray[y+1]) {
        holder = ranarray[y+1];
        ranarray[y+1] = ranarray[y];
        ranarray[y] = holder;
      }
    }
  }

回答1:

Before enter the inner loop, create a boolean to check if a swap occured inside the inner loop. When the there is no swap the array is sorted.

function sortNumbers(listbox) { 
  var x, y, holder; 
  // The Bubble Sort method. 
  for(x = 0; x < ranarray.length; x++) { 
    var swapOccured = false;
    for(y = 0; y < (ranarray.length-1); y++) { 
      if(ranarray[y] > ranarray[y+1]) { 
        holder = ranarray[y+1]; 
        ranarray[y+1] = ranarray[y]; 
        ranarray[y] = holder; 
        swapOccured = true;
      } 
    }
    if (!swapOccured) break; 
  } 

回答2:

var a = [1, 203, 3, 746, 200];

function bubbleSort(a)
{
    var swapped;
    do {
        swapped = false;
        for (var i=0; i < a.length-1; i++) {
            if (a[i] > a[i+1]) {
                var temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swapped = true;
            }
        }
    } while (swapped);

    for(i=0;i<a.length;i++)
    {
        document.write(a[i]+"\t");
    }
}

bubbleSort(a);

回答3:

Check if a swap occurs in the inner loop. When there is no swap during one run, the list is sorted.

Also, you can use the x value to determine the last item that you need to look at in the inner loop. After x runs the last x items are always in the right place.

function sortNumbers(listbox) {
  var done = false;
  for (var x = 1; !done; x++) {
    done = true;
    for (var y = 0; y < ranarray.length - x; y++) {
      if (ranarray[y] > ranarray[y + 1]) {
        var holder = ranarray[y + 1];
        ranarray[y + 1] = ranarray[y];
        ranarray[y] = holder;
        done = false;
      }
    }
  }
}

回答4:

You can use XOR to bit shift positions in the array;

var arr, len, len2;
    arr = [0, 5, 7, 8, 9, 1, 2, 3, 6, 4];

len = arr.length;

// for loops
for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1; j++) {
        if (arr[i] <= arr[j]) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[j] ^ arr[i];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}

// negative while
while (--len) {
    len2 = len;
    while (len2--) {
        if (arr[len] < arr[len2]) {
            arr[len] = arr[len] ^ arr[len2];
            arr[len2] = arr[len2] ^ arr[len];
            arr[len] = arr[len] ^ arr[len2];
        }
    }
}

jsperf: http://jsperf.com/sort-tive/4

回答5:

Advanced Bubble sort which is more Efficient,more Faster with just one for loop.

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

public class Bubble {

    public int[] bubble(int b[]){ 
    int temp,temp1; 

    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])

                        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,3}; 
        int v[]=new int[100]; 
        Bubble br=new Bubble();
        v=br.bubble(b);
        br.see(v);

    }
}