《大话数据结构》第9章，排序

一.冒泡排序

冒泡排序：一种交换排序，通过两两比较相邻的关键字，如果顺序相反则交换，知道没有反序为止。

1
2
3
4
5
6
function swap(i, j, arr) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
  return arr
}
  • 最简单的排序
1
2
3
4
5
6
7
8
9
10
11
function bubbleSort0(arr) {
	var i, j, len = arr.length
	for (i = 0; i < len; i++) 
	  for (j = i + 1; j < len; j++) 
	    if (arr[i] > arr[j]) 
	    	swap(i, j, arr)
	  
	return arr
}
bubbleSort0([9, 1, 5, 8, 3, 7, 4, 6, 2])
  • 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
function bubbleSort(arr) {
  var i, j, len = arr.length
  for (i = 0; i < len; i++) 
    for (j = len - 1; j >= i; j--) 
      if (arr[j - 1] > arr[j]) 
        swap(j - 1, j, arr)
  return arr
}
bubbleSort([9, 1, 5, 8, 3, 7, 4, 6, 2])
  • 冒泡排序优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort2(arr) {
	var i, j, len = arr.length
	var flag = true
  for (i = 0; i < len && flag; i++)  {
  	flag = false
    for (j = len - 1; j >= i; j--) 
      if (arr[j - 1] > arr[j]) {
        swap(j - 1, j, arr)
        flag = true
      }
  }
  return arr
}
bubbleSort2([9, 1, 5, 8, 3, 7, 4, 6, 2])

二.简单选择排序

简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。

  • 简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectSort(arr) {
  var i, j, min, len = arr.length
  for (i = 0; i < len; i++) {
    min = i
    for (j = i + 1; j < len; j++) {
      if (arr[min] > arr[j])
        min = j
    }
    if (i != min)
      swap(i, min, arr)
  }
  return arr
}
selectSort([9, 1, 5, 8, 3, 7, 4, 6, 2])

三.直接插入排序

直接插入排序：将一个记录插入到已经排好序的有序表中，得到一个新的，记录数加1的有序表。

  • 直接插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertSort(arr) {
	var i, j, temp, len = arr.length
	for (i = 1; i < len; i++) {
		temp = arr[i]
		j = i - 1
		while (j >= 0 && temp < arr[j]) {
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = temp
	}
	return arr
}
insertSort([9, 1, 5, 8, 3, 7, 4, 6, 2])

四.希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function shellSort(arr){
  var i, j, len = arr.length,
      inc = parseInt(len/2), tmp
  while (inc > 0) {
    for (i = inc; i < len; i++) {
      tmp = arr[i]
      j = i - inc
      while (j >= 0 && tmp < arr[j]) {
        arr[j + inc] = arr[j]
        j = j - inc
      }
      arr[j + inc] = tmp
    }
    inc = parseInt(inc / 2)
  }
  return arr;
}
shellSort([9, 1, 5, 8, 3, 7, 4, 6, 2])

五.堆排序

堆排序：将待排序的序列构造成一个大的顶堆，此时，整个序列的最大值就是堆顶的根节点。将他移走，然后将剩余的n-1个序列重新构造成一个堆，这样会得到n个元素中的次小值。如此反复执行，直至得到一个有序序列。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function heapSort(array) {
  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  function maxHeapify(array, index, heapSize) {
    var iMax,
      iLeft,
      iRight;
    while (true) {
      iMax = index;
      iLeft = 2 * index + 1;
      iRight = 2 * (index + 1);
      if (iLeft < heapSize && array[index] < array[iLeft]) {
        iMax = iLeft;
      }
      if (iRight < heapSize && array[iMax] < array[iRight]) {
        iMax = iRight;
      }
      if (iMax != index) {
        swap(array, iMax, index);
        index = iMax;
      } else {
        break;
      }
    }
  }
  function buildMaxHeap(array) {
    var i,
      iParent = Math.floor(array.length / 2) - 1;
    for (i = iParent; i >= 0; i--) {
      maxHeapify(array, i, array.length);
    }
  }
  function sort(array) {
    buildMaxHeap(array);
    for (var i = array.length - 1; i > 0; i--) {
      swap(array, 0, i);
      maxHeapify(array, 0, i);
    }
    return array;
  }
  return sort(array);
}
heapSort([9, 1, 5, 8, 3, 7, 4, 6, 2])

六.归并排序

归并排序：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并，如此反复，直到得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
function mergeSort(array) {
    var result = array.slice(0);
    // 递归调用合并函数
    function sort(array) {
        var length = array.length,
            mid = Math.floor(length * 0.5),
            left = array.slice(0, mid),
            right = array.slice(mid, length);
        if (length === 1) {
            return array;
        }
        return merge(sort(left), sort(right));
    }
    // 合并 两有序的数组
    function merge(left, right) {
        var result = [];
        while (left.length || right.length) {
            if (left.length && right.length) {
                if (left[0] < right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            } else if (left.length) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        return result;
    }
    return sort(result);
}
mergeSort([9, 1, 5, 8, 3, 7, 4, 6, 2])

七.快速排序

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，达到整个序列有序的目的。

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
30
31
32
function quickSort(array) {
	// 交换元素位置
	function swap(array, i, k) {
		var temp = array[i];
		array[i] = array[k];
		array[k] = temp;
	}
	// 数组分区，左小右大
	function partition(array, left, right) {
		var storeIndex = left;        
		var pivot = array[right]; // 直接选最右边的元素为基准元素
		for (var i = left; i < right; i++) {
			if (array[i] < pivot) {
				swap(array, storeIndex, i);
				storeIndex++; // 交换位置后，storeIndex 自增 1，代表下一个可能要交换的位置
			}
		}
		swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
		return storeIndex;
	}
	function sort(array, left, right) {
		if (left > right) {
			return;
		}
		var storeIndex = partition(array, left, right);
		sort(array, left, storeIndex - 1);
		sort(array, storeIndex + 1, right);
	}
	sort(array, 0, array.length - 1);
	return array;
}
quickSort([9, 1, 5, 8, 3, 7, 4, 6, 2])