还有另一种方法来优化这种冒泡排序？

Question

我有这种代码使用冒泡排序算法排序数值数组。

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9]; 

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); 
} 

bubbleSort(a); 
alert(a); 

你可以在这里看到：http://jsfiddle.net/x7VpJ/

那么，它完美的作品，你可以检查，但我想知道是否有另一种方式来优化这种做用实际的方法更少的循环。我的意思是，用换成变量。 也许省略了排序的项目...一些想法？

在此先感谢。

Answer 1

这里是我一直在寻找的解决方案：

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9, 1, 32423, 3455, 23, 4234,23]; 

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

bubbleSort(a); 
alert(a); 

http://jsfiddle.net/x7VpJ/1/

感谢所有的反应。

Answer 2

这是JS中不同排序算法的列表。我做了一个比较排序时间和从我注意到“快速”似乎是最佳选择的页面。

冒泡排序：

var arrBubble= new Array(); 
var tmpBubble; 
function srtBubble(){ 
    tmpDate=new Date(); 
    timBegin=tmpDate.getTime(); 

    var blnBubbleSwitch; 
    do { 
     blnBubbleSwitch=false; 
     for(var i=0;i<arrBubble.length-1;i++){ 
      if(arrBubble[i]>arrBubble[i+1]) 
      { 
       tmpBubble=arrBubble[i]; 
       arrBubble[i]=arrBubble[i+1]; 
       arrBubble[i+1]=tmpBubble; 
       blnBubbleSwitch=true; 
      } 
     } 
    } while(blnBubbleSwitch); 
} 

插入：

var arrinsertion= new Array(); 
var tmpinsertion; 
function srtinsertionion(){ 
    var j; 
    blninsertionSwitch=false; 
    for(var i=0;i<arrinsertion.length;i++){ 
     tmpinsertion=arrinsertion[i]; 
     j=i; 
     while((j>=0)&&arrinsertion[j-1]>tmpinsertion) 
     { 
      arrinsertion[j]=arrinsertion[j-1]; 
      j--; 
      //blninsertionSwitch=true; 
     } 
     arrinsertion[j]=tmpinsertion; 
    } 
} 

外壳：

function srtShell(){ 
var arrShell= new Array(); 
    for (var h = arrShell.length; h = parseInt(h/2);) { 
     for (var i = h; i < arrShell.length; i++) { 
      var k = arrShell[i]; 
      for (var j = i; j >= h && k < arrShell[j - h]; j -= h) 
       arrShell[j] = arrShell[j - h]; 
      arrShell[j] = k; 
     } 
    } 
} 

快速：

function srtQuick() 
{ 
    var arrQuick= new Array(); 
    qsort(arrQuick, 0, arrQuick.length); 
} 
function qsort(array, begin, end) 
{ 
    if(end-1>begin) { 
     var pivot=begin+Math.floor(Math.random()*(end-begin)); 

     pivot=partition(array, begin, end, pivot); 

     qsort(array, begin, pivot); 
     qsort(array, pivot+1, end); 
    } 
} 
Array.prototype.swap=function(a, b) 
{ 
    var tmp=this[a]; 
    this[a]=this[b]; 
    this[b]=tmp; 
} 
function partition(array, begin, end, pivot) 
{ 
    var piv=array[pivot]; 
    array.swap(pivot, end-1); 
    var store=begin; 
    var ix; 
    for(ix=begin; ix<end-1; ++ix) { 
     if(array[ix]<=piv) { 
      array.swap(store, ix); 
      ++store; 
     } 
    } 
    array.swap(end-1, store); 

    return store; 
} 

合并：

function merge_inplace(array, begin, begin_right, end) 
{ 
    var arrMerge= new Array(); 
    for(;begin<begin_right; ++begin) { 
     if(array[begin]>array[begin_right]) { 
      var v=array[begin]; 
      array[begin]=array[begin_right]; 
      insertion(array, begin_right, end, v); 
     } 
    } 
} 

function insertion(array, begin, end, v) 
{ 
    while(begin+1<end && array[begin+1]<v) { 
     array.swap(begin, begin+1); 
     ++begin; 
    } 
    array[begin]=v; 
} 

function msort(array, begin, end) 
{ 
    var size=end-begin; 
    if(size<2) return; 

    var begin_right=begin+Math.floor(size/2); 

    msort(array, begin, begin_right); 
    msort(array, begin_right, end); 
    merge_inplace(array, begin, begin_right, end); 
} 

function srtMerge() 
{ 
    msort(arrMerge, 0, arrMerge.length); 
} 

内置JS排序：

function srtJSSort() 
{ 
    var arrJSSort= new Array(); 
    arrJSSort.sort(function(a,b){return a-b}); 
} 

当然，我会建议使用功能之外的阵列，这样你就可以将数据排序后继续使用它。

Answer 3

如果我坚持原来的问题（我不会建议完全不同的算法...）。

是的，还有一个改进 - 双向气泡排序，称为shaker sort。它消除了龟和兔子的问题。在单向的气泡分类中，轻微的气泡快速移动到阵列的末端（兔子），而重气泡非常缓慢地朝着开始移动。但如果以双向方式排序，两种类型的气泡排序都相当快（仍然在O（n^2）中，但通常比传统气泡排序更快）。