js的几种排序方法

大家在数据结构中都学习到各种排序的方法，下面是关于js排序的几种方法，跟C语言数据结构中讲的大同小异，希望能够对大家的工作和学习有所帮助

1、直接插入排序基本思想
      假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

      算法描述
function InsertSort(arr) { //插入排序->直接插入法排序
    var st = new Date();
    var temp, j;
    for(var i=1; i<arr.length; i++) {
     if((arr[i]) < (arr[i-1])) {
      temp = arr[i];
      j = i-1;
      do {
       arr[j+1] = arr[j];
       j--;
      }
      while (j>-1 && (temp) < (arr[j]));
      arr[j+1] = temp;
     }//endif
    }
    status = (new Date() - st) + ' ms';
    return arr;
}

2、希尔排序基本思想
　    先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
    　该方法实质上是一种分组插入方法。

      算法描述


function ShellSort(arr) { //插入排序->希儿排序
    var st = new Date();
    var increment = arr.length;
    do {
     increment = (increment/3|0) + 1;
     arr = ShellPass(arr, increment);
    }
    while (increment > 1)

    status = (new Date() - st) + ' ms';
    return arr;
}
function ShellPass(arr, d) { //希儿排序分段执行函数
    var temp, j;
    for(var i=d; i<arr.length; i++) {
     if((arr[i]) < (arr[i-d])) {
      temp = arr[i]; j = i-d;
      do {
       arr[j+d] = arr[j];
       j = j-d;
      }
      while (j>-1 && (temp) < (arr[j]));
      arr[j+d] = temp;
     }//endif
    }
    return arr;
}


3、冒泡排序基本思想
      将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。


      算法描述
function BubbleSort(arr) { //交换排序->冒泡排序
    var st = new Date();
    var temp;
    var exchange;
    for(var i=0; i<arr.length; i++) {
     exchange = false;
     for(var j=arr.length-2; j>=i; j--) {
      if((arr[j+1]) < (arr[j])) {
       temp = arr[j+1];
       arr[j+1] = arr[j];
       arr[j] = temp;
       exchange = true;
      }
     }
     if(!exchange) break;
    }
    status = (new Date() - st) + ' ms';
    return arr;
}


4、快速排序基本思想
      将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
      在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

      算法描述
function QuickSort(arr) { //交换排序->快速排序
    if (arguments.length>1) {
     var low = arguments[1];
     var high = arguments[2];
    } else {
     var low = 0;
     var high = arr.length-1;
    }
    if(low < high){
     // function Partition
     var i = low;
     var j = high;
     var pivot = arr[i];
     while(i<j) {
      while(i<j && arr[j]>=pivot)
       j--;
      if(i<j)
       arr[i++] = arr[j];
      while(i<j && arr[i]<=pivot)
       i++;
      if(i<j)
       arr[j--] = arr[i];
     }//endwhile
     arr[i] = pivot;
     // end function
     var pivotpos = i; //Partition(arr，low，high);
     QuickSort(arr, low, pivotpos-1);
     QuickSort(arr, pivotpos+1, high);
    } else
     return;
     return arr;
}

5、直接选择排序基本思想
    　n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
      在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
③第i趟排序
　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
      这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

      算法描述
function SelectSort(arr) { //选择排序->直接选择排序
    var st = new Date();
    var temp;
    for(var i=0; i<arr.length; i++) {
     var k = i;
     for(var j=i+1; j<arr.length; j++) {
      if((arr[j]) < (arr[k]))
       k = j;
     }
     if (k != i){
      temp = arr[i];
      arr[i] = arr[k];
      arr[k] = temp;
     }
    }
    status = (new Date() - st) + ' ms';
    return arr;
}