我的回答

冒泡排序

冒泡排序思想

  • 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。

  • 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

    算法描述

  • 比较相邻的元素，如果前一个比后一个大，交换之。

  • 第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
  • 第二趟将第二大的数移动至倒数第二位
    ……
    因此需要n-1趟；
  1. function bubbleSort(arr) {
  2.   if (!arr || !arr.length) return
  3.     for (let i = 0; i < arr.length - 1; i++) {
  4.     for (let j = 0; j < arr.length - i -1; j++) {
  5.       if (arr[i] > arr[j]) {
  6.         let temp = arr[j]
  7.         arr[j] = arr[i]
  8.         arr[i] = temp
  9.       }
  10.     }
  11.   }
  12. }

优化点

  1. 第一层循环的长度的最有一位可以不用考虑(arr.length - 1), 因为最后一位默认是最大值

  2. 第二层循环的长度可以不用考虑当前i后面的, 以为他们已经被排好序了(arr.length - i- 1)

    选择排序

    思想

    每一次遍历待排序的序列，记录最小（大）值的下标，和待排序第一个元素进行比较，如果小（大）与待排序第一个元素，交换

    实现

    1. function selectSort(arr) {
    2.  for (let i = 0, k = 0; i < arr.length; i++, k = i) {
    3.    for (let j = i + 1; j < arr.length; j++) {
    4.    if (arr[k] > arr[j]) { // 从小到大
    5.      k = j
    6.    }
    7.  }
    8.  if (i != k) {
    9.    let temp = arr[i]
    10.    arr[i] = arr[k]
    11.    arr[k] = temp
    12.  }
    13. }
    14. }

    参考回答

    冒泡排序

    冒泡排序是一个简单的排序算法。它重复地走访过要排序地数列，一次比较两个元素，如果它们的排序错误就把它们交换过来。
    走访数列的工作是重复的进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端

    思路

    外层循环

  3. 比较两个相邻的元素，如果前一个要比后一个大，就交换两者的位置。

  4. 对每个对相邻做同样的工作，从开始第一对到结尾的最后一对，这样在最后应该是会是最大的数字
  5. 重复以上步骤，除了最后一个
  6. 重复 1~3，直到排序完成

    复杂度 时间复杂度

  • 最好的情况：数组已经是排好序的了 O(n)
  • 最差的情况：数组是一个反向数组 O(n^2)
  • 平均的情况：O(n^2) 空间复杂度
  • O(1)

    实现

    ```javascript arr2 = [1, 5, 3, 8, 6, 9, 11]; function bubbleSort(arr) { var len = arr.length; for (let i = 0; i < len; i++) { for (let j = 0; j < len - 1 - i; j++) {
    1. if (arr[j] > arr[j + 1]) {
    2.   var temp = arr[j + 1];
    3.   arr[j + 1] = arr[j];
    4.   arr[j] = temp;
    5. }
    } } return arr; }

console.log(bubbleSort(arr2));

  1. <a name="UJig0"></a>
  2. #### 冒泡排序优化
  4. - 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值
  5. - 如果考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大值和最小值)，这样的话可以使排序趟数减少了一半。
  7. ```javascript
  8. function bubbleSort2(arr) {
  9.   var low = 0;
  10.   var high = arr.length - 1; //设置变量的初始值
  11.   var tmp, j;
  12.   console.time("2.改进后冒泡排序耗时");
  13.   while (low < high) {
  14.     for (
  15.       j = low;
  16.       j < high;
  17.       ++j //正向冒泡,找到最大者
  18.     )
  19.       if (arr[j] > arr[j + 1]) {
  20.         tmp = arr[j];
  21.         arr[j] = arr[j + 1];
  22.         arr[j + 1] = tmp;
  23.       }
  24.     --high; //修改high值, 前移一位
  25.     for (
  26.       j = high;
  27.       j > low;
  28.       --j //反向冒泡,找到最小者
  29.     )
  30.       if (arr[j] < arr[j - 1]) {
  31.         tmp = arr[j];
  32.         arr[j] = arr[j - 1];
  33.         arr[j - 1] = tmp;
  34.       }
  35.     ++low; //修改low值,后移一位
  36.   }
  37.   console.timeEnd("2.改进后冒泡排序耗时");
  38.   return arr2;
  39. }
  40. console.log(bubbleSort2(arr2));

选择排序

选择排序是表现最稳定的排序，无论数据量，情况是怎么样的，它的复杂度都是 O(n^2),空间复杂度为 O(1)

原理

首先在末排序的序列中找到最小(最大)的元素。然后放到已排序的最前面(最后面)，以此类推。

代码实现思路

  1. 无序区为排序数组，有序区为空
  2. 第 i 趟排序开始时，当前有序区和无序区分别为 arr[1…i-1]和 arr[i…n].该趟排序从当前无序区中 - 选出关键字最小的记录 arr[k]
  3. 将它与无序区的第一个记录 a 交换，使得 arr[1…i]和 arr[i+1…n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区

    实现

    ```javascript function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) {
    1.  minIndex = j;
    } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }

console.log(selectionSort(arr2)); ```