常见排序算法的JS实现

常见的排序算法

常见排序算法的时间复杂度和空间复杂度

1.算法的效率

算法的效率主要由时间复杂率和空间复杂率来评估：

• 时间复杂度：程序运行所需的时间，可以看出程序对处理器的实用程度
• 空间复杂度：程序执行过程中所需的存储空间，可以看出程序对计算机内存的使用程度
  #####

1. 冒泡排序，原理：

• 一次比较相邻的两个数， 如果前边的大就交换位置，这样一轮下来，最后一个是最大的。
• 对除了最后一个数重复第一步，直到只剩一个数
  
  
  

  展开查看代码

  
  

  
  System.out.println(“Hello to see U!”);
  

  
  
  
  代码实现：

  function bubbleSort(myArray){
      var len = myArray.length;
      for (let i = 0; i < len-1; i++) {
          for(let j = 0, stop = len - i - 1; j < stop; j++) {
              if(myArray[j] > myArray[j+1]) {
                  let temp = myArray[j];
                  myArray[j] = myArray[j+1];
                  myArray[j+1] = temp;
              }
          }
      }
      return myArray;
  }
  var s = [5,6,7,34,45,23,12,34,14,56];
  for (let i = 0; i < 10; i++) {
      s = s.concat(s); // 产生一个长度为2的九次方*10的数组
  }
  var start = Date.now();
  bubbleSort(s);
  var end = Date.now();
  console.log("排序后的数组：" + s);
  console.log("所用时间：" + (end - start));

2. 选择排序， 原理：

• 找出最小的数很第一个交换位置
• 在剩下的数中，找出第二小的数，放在第二个位置
• 依次类推
  代码实现：

  function selectSort(myArray) {
      var len = myArray.length;
      for (let i = 0; i < len - 1; i++) {
          for(let j = i+1; j < len; j++) {
              if(myArray[j] < myArray[i]) {
                  temp = myArray[i];
                  myArray[i] = myArray[j];
                  myArray[j] = temp;
              }
          }
      }
  }
  var s = [5,6,7,34,45,23,12,34,14,56];
  for (let i = 0; i < 10; i++) {
      s = s.concat(s); // 产生一个长度为2的九次方*10的数组
  }
  var start = Date.now();
  selectSort(s);
  var end = Date.now();
  console.log("排序后的数组：" + s);
  console.log("所用时间：" + (end - start));

看到这里是不是觉得这个测试用例好蠢 我们改进一下：

function testTime(sortFunc) {
    var s = [5,6,7,34,45,23,12,34,14,56];
    for (let i = 0; i < 10; i++) {
        s = s.concat(s); // 产生一个长度为2的九次方*10的数组
    }
    var start = Date.now();
    sortFunc(s);
    var end = Date.now();
    console.log("排序后的数组：" + s);
    console.log("所用时间：" + (end - start));
}

之后写好一个方法，然后调用testTime()将排序方法传进去即可

插入排序 原理：

• 把数组分为已排序和未排序两部分。（第一步可以第一个数为已排序，其余为未排序）
• 从未排序中抽出第一个数，和已排序部分进行比较，插入到合适的位置
  代码实现：

  function insertionSort(myArray) {
      var len = myArray.length;
      for (let i = 1; i < len; i++) {
          let k;
          for (let j = 0; j < i; j++) {
              if(myArray[i] < myArray[j]) {
                  myArray[j+1] = myArray[j];
              }
          }
          myArray[j] = myArray[i];s   
      }
      return myArray;
  }

赏

谢谢你请我吃糖果