首页 > 代码库 > 算法:常用排序算法

算法:常用排序算法

最近整理了常用的排序算法,整理好,留下自己的思考过程。

1、冒泡排序:

(1)平均时间复杂度:O(n2)

(2)最好时间复杂度:O(n)

(3)最坏时间复杂度:O(n2)

(5)空间复杂度:O(1)

(5)稳定性:稳定

(6)JavaScript实现:

function bubble ( arr ) {
    var len = arr.length;
    var tmp;
    //  外层循环负责控制排序的趟数
    for(var i = 0; i < len - 1; i++){
       // 内层循环负责进行一趟排序
       for(var j = 0; j < len - 1 - i; j++){
          if(arr[j + 1] < arr[j]){
              tmp = arr[j];
              arr[j] = arr[j + 1];
              arr[j + 1] = tmp;
          };
       };
    };
    return arr;
};

2、选择排序:

(1)平均时间复杂度:O(n2)

(2)最好时间复杂度:O(n2)

(3)最坏时间复杂度:O(n2)

(4)空间复杂度:O(1)

(5)稳定性:不稳定

(6)JavaScript实现:

function select( arr ) {
   var len = arr.length;
   // 外层循环需要进行len - 1趟排序
   for(var i = 0; i < len - 1; i++){
      var index = i;
      var min = arr[i];
      var tmp;
      // 内层循环从未排序的数组元素中比较出最小的一个
      for(var j = i + 1; j < len; j++){
         if(min > arr[j]){
            index = j;
            min = arr[j];
         };
      };
      // 将其放在排序后的数组元素的最后
      tmp = arr[i];
      arr[i] = min;
      arr[index] = tmp;
   };
};

3、插入排序:

(1)平均时间复杂度:O(n2)

(2)最好时间复杂度:O(n)

(3)平均时间复杂度:O(n2)

(4)空间复杂度:O(1)

(5)稳定性:稳定

(6)JavaScript实现:

function insert ( arr ) { 
   var len = arr.length;
   var tmp;
   for(var i = 1; i < len; i++){
      // 取出当前的数组元素
      tmp = arr[i];
      for(var j = i - 1; j >= 0; j--){
         if (arr[j] > tmp) {
            arr[j+1] = arr[j];
         }
      };
      // 插入取出的数组元素
      arr[j+1] = tmp;
   };
   return arr;
}

 

算法:常用排序算法