算法-排序

一月 06, 2019

冒泡算法

时间复杂度 $$ O(n^2) $$

首先我们可以看下冒泡排序的一个过程，以视频为例：

即冒泡排序是：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从 A 到 Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。

所以知道了冒泡排序的原理和排序流程，我们很容易就写出冒泡排序的算法：

function sort(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = 1; j < arr.length - i; j++) {
      if (arr[j] < arr[j - 1]) {
        var temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
  }
  return arr;
}

console.log(sort([1, 123, 2, 3, 12, 3, 123, 12, 3]));
// [ 1, 2, 3, 3, 3, 12, 12, 123, 123 ]

思考：如果上面代码中，里面一层循环在某次扫描中没有执行交换，则说明此时数组已经全部有序列，无需再扫描了。因此，增加一个标记，每次发生交换，就标记，如果某次循环完没有标记，则说明已经完成排序。

function sort(arr) {
  for (var i = 0; i < arr.length; i++) {
    var hasSwaped = false;
    for (var j = 1; j < arr.length - i; j++) {
      if (arr[j] < arr[j - 1]) {
        var temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
        hasSwaped = true;
      }
    }
    if (!hasSwaped) {
        return arr;
    }
  }
  return arr;
}

选择排序

时间复杂度 $$ O(n^2) $$

首先观看选择排序的算法过程：

即选择排序是：它依次地走访过要排序的元素列，找到其中最小的元素，放到左列数组里，然后放进左列数组的元素与右侧最小元素对换位置及值。

function sort(arr) {
  for (var i = 0; i < arr.length; i++) {
    var min = arr[i];
    var minIndex = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j];
        minIndex = j;
      }
    }
    var temp = arr[i];
    arr[i] = min;
    arr[minIndex] = temp;
  }
  return arr;
}

console.log(sort([1, 123, 2, 3, 12, 3, 123, 12, 3]));
// [ 1, 2, 3, 3, 3, 12, 12, 123, 123 ]