小灰算法-数组排序

排序算法

不知道自己在干嘛，总之看这个很累，看完了，再看 Array.prototy.sort() 源码实现。还是一言难尽呐！不过，不管怎么样，既然看都看了，笔记还是写写。

冒泡排序（bubble sort）

冒泡排序是一种基础的交换排序。

1
var arr = [9,2,3,6,14,22]

基础冒泡

相邻元素两两比较，相邻元素左边大于右边交换位置；否则位置不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(arr) {
  var num = 0;
  for (var i=0; i < arr.length - 1; i++) {
    for (var j=0; j < arr.length - 1 - i; j++) {
      num ++
      if (arr[j] > arr[j+1]) {
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }

  console.log(num) // 共 9 次
}

冒泡优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSortV2(arr) {
  var num = 0;
  for (var i=0; i<arr.length-1; i++) {
    var isSorted = true;
    for (var j=0; j<arr.length-1-i; j++) {
      num ++
      if (arr[j] > arr[j+1]) {
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
        isSorted = false
      }
    }
    if(isSorted) break;
  }
  console.log(num)
}

其实这个方法执行下的结果并不正确，我再三跟书的案例确认下。代码一毛一样，那么下面要怎么着。这个方法执行的前提是数组前后两部分，后一部分有序，前半部分无序而且前半部分阳大的数小于后半部分最小数。如：[3,2,4,1,2,5,6,7,8]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function bubbleSortV3(arr) {
  var num = 0;
  for (var i=0; i<arr.length-1; i++) {
    var isSorted = true;
    var sortBorder = arr.length - 1;
    
    for(var j=0; j<sortBorder; j++) {
      num ++
      if (arr[j] > arr[j+1]) {
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp;
        isSorted = false;
        sortBorder = j;
      }
    }

    if(isSorted) break;
  }
  console.log(num) // 共 11 次
}

鸡尾酒排序

与冒泡相同，都是通过交换排序的。冒泡从左到右比较元素，进行单向位置交换。鸡尾酒元素比较和交换是双向。
鸡尾酒排序书中举了个特殊的例子 [8,2,3,4,5,6,7,1]，其大意是，只有问部分无序，确要比较 7 轮 。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function cocktail(arr) {
  var isSorted = true;
  var temp = 0;
  for (var i=0; i < parseInt(arr.length/2); i++) {
    // 由左到右交换，最大数排在最后面
    for (var j = 0; j < arr.length - 1 - i; i++) {
      if (arr[j] > arr[j+1]) {
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp;
        isSorted = false;
      }
    }
    if (isSorted) break;
    
    isSorted = true;
    temp = 0;
    // 由右向左交换，最小数排在最前面
    for (var k=arr.length-i-1; k > i; k--) {
      if (arr[k] < arr[k-1]) {
        temp = arr[k]
        arr[k] = arr[k-1]
        arr[k-1] = temp;
        isSorted = false;
      }
    }
    if (isSorted) break;
  } 
}

快速排序

基础快速排序

基准元素选择

单边循环