八大排序+两大查找的JS实现

发表于   |     |   阅读次数

摘要：关于排序和查找算法，以前我不是很重视，因为在做前端的时候很少会涉及到这些算法。但是后来发现其实排序和查找是算法的基础，所以这几天也整理了一下八大排序算法和两大查找算法的JavaScript实现。

分类

排序分为内部排序和外部排序，这里我们只介绍内部排序。

八大排序算法

  1. 插入排序
    • 直接插入排序
    • 希尔排序
  2. 选择排序
    • 直接选择排序
    • 堆排序
  3. 交换排序
    • 冒泡排序
    • 快速排序
  4. 归并排序
  5. 基数排序

两大查找算法

  1. 折半查找法
  2. 二叉查找树查找法

八大排序算法

插入排序

直接插入排序

思想：直接插入排序，就是在要排序的数组中，假设前面（n-1）位已经排好序了，然后把第n个数插入到前面的有序区中，也就实现了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
//直接插入排序
function dinsert(list){
	//key用来保存当前正在比较的值
	var len = list.length,key = null;

	//i表示要执行轮次，即数组长度-1，第一次把第一个数当成有序区
	for(var i = 1;i < len;i++){
		key = list[i];
		//j表示有序区中的跟当前值比较的数
		for(var j = i-1;j >= 0;j--){
			if(list[j] > key){
				//list[j]比key大的，就把list[j]后移一位
				list[j+1] = list[j];
				if(j == 0){
					list[j] = key;
				}
			}else{
				break;
			}
		}
		list[j+1] = key;
	}
	return list;
}

希尔排序

思想：希尔排序其实就是直接插入排序的一个优化算法，首先按某个增量d（n/2，n为要排序数组的个数），每组记录的下标相差d，对每组中的所有元素进行直接插入排序，然后再选择一个较小的增量d/2，再进行分组，每组进行直接插入排序，直到增量为1的时候，对整个数组进行直接插入排序后，排序完成。

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
/*
* 一趟希尔排序
*/
function shellInsert(list,dk) {
	var i,j,len=list.length,key=null;
	for(i = 0;i < len - dk;i++) {
		// 将i+dk插入有序序列
		if(list[i+dk] < list[i]) {
			key = list[i+dk];
			j = i + dk;
			do{
				// 记录后移
				j -=dk;
				list[j+dk] = list[j];
			}while(j-dk > 0 && key < list[j-dk]);
			list[j] = key;
		}
	}
}
function shell2(list) {
	var group = null;
	// group为增量，直到1的时候排序结束
	for(group = Math.floor(list.length/2);group > 0; group = Math.floor(group/2)) {
		shellInsert(list,group);
	}
	return list;
}

选择排序

直接选择排序

思想：在要排序的数组中，选择最小的数与第一位交换，然后在剩下的数中找出最小的数与第二位交换，如此循环到倒数第二个数与倒数第一个数比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
function choose(list) {
	var len = list.length,temp = null;
	for (var i = 0; i < len; i++){
		for(var j = i + 1;j < len;j++){
			if(list[i] > list[j]) {
				temp = list[i];
				list[i] = list[j];
				list[j] = temp;
			}
		}
	}
	return list;
}

堆排序

思想：堆排序是一种树形选择排序，是直接选择排序的有效改进。
堆的定义：堆是一棵完全二叉树，并且n个有序序列（h1,h2,h3…,hn），其中（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=h2i+1），（i=1,2,3…,n/2）时称为堆，当堆顶的为最大项时为大顶堆，堆顶为最小项时为小顶堆。
在堆排序中，我们首先要建立大顶堆，然后把堆顶与最后一个元素交换，然后再对前面n-1个数进行调整，使之成为大顶堆，依此类推，知道只有两个节点交换的堆。所以，在堆排序中，会用到两个函数，一个是建堆函数，一个是调用建堆函数实现排序的函数。

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
47
48
49
50
51
52
/*
* 交换函数
*/
function swap(list,i,j) {
	var temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

/*
* 建堆函数
*/
function buildMaxHeap(list,lastIndex) {
	for(var i = Math.floor((lastIndex-1)/2);i >= 0;i--) {
		// i为lastIndex的父节点
		// k保存当前正在判断的节点
		var k = i;
		// 当k存在左节点时，即k存在子节点
		while(2*k+1 <= lastIndex) {
			// 暂时保存左节点的值到biggerIndex即最大值
			var biggerIndex = 2*k+1;
			if(biggerIndex < lastIndex) {
				// 当左节点不是最后的节点的时候
				// 判断左右节点哪个大，把大的序号保存到biggerIndex
				if(list[biggerIndex] < list[biggerIndex+1]) {
					biggerIndex++;
				}
			}
			if(list[k] < list[biggerIndex]) {
				// 比较父节点与左右节点最大值，把大值交换到父节点
				// 交换后把k修改为biggerIndex，继续循环判断子节点
				swap(list,k,biggerIndex);
				k = biggerIndex;
			}else {
				break;
			}
		}
	}
}

/*
* 堆排序函数
*/
function heapSort(list){
	var len = list.length;
	for(var i = 0;i < len-1;i++) {
		// 建堆，每次减去最后的数进行建堆
		buildMaxHeap(list,len-1-i);
		swap(list,0,len-1-i);
	}
	return list;
}

交换排序

冒泡排序

思路：对于待排数组list[n]
1.list[0]与list[1]比较，把大的放到list[1]，然后list[1]与list[2]比较，把大的放到list[2]，依此类推，直到把最大的数放到list[n];
2.与第一步同理，直到把最大的数放到list[n-1];
3.最后直到list[0]与list[1]比较交换完成排序;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbling(list) {
	var len = list.length,temp;
	// i表示本次冒泡参与的个数
	for (var i = len - 1; i >= 0; i--) {
		// j表示交换的次数
		for (var j = 0;j < i;j++) {
			if(list[j] > list[j+1]) {
				temp = list[j];
				list[j] = list[j+1];
				list[j+1] = temp;
			}
		};
	};
	return list;
}

快速排序

思路：选取一个基准，通常是第一个数或者最后一个数，通过一趟扫描把待排序列分成两部分，左边的比基准小，右边的比基准大，此时基准就位于正中间，也就是正确的位置，然后再用同样的方法递归左右两部分。

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
function quick(list) {
	// begin表示第一个数的序号，end表示最后一个数的序号
	function sort(begin,end) {
		var i = begin,
			j = end,
			// flag表示基准
			flag = list[begin];
		if(begin < end){
			while(i < j) {
				// 从后开始向前扫描，找到比基准小的数，放到list[i]
				for (;i < j;j--) {
					if(list[j] < flag) {
						list[i++] = list[j];
						break;
					}
				}
				// 再从前向后扫描，找到比基准大的数，放到list[j]
				for(;i < j;i++) {
					if(list[i] > flag) {
						list[j--] = list[i];
						break;
					}
				}
			}
			// 最后i，j相同，所指向的位置就是flag的正确位置
			list[i] = flag;
			sort(0,i-1);
			sort(i+1,end);
		}
	}
	sort(0,list.length-1);
	return list;
}

快排的优化方案：当同时找到比基准小的位置和比基准大的位置，再进行交换，三数取中，找出三个数中处于中间的数，效率会更高一点。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
* 交换函数
*/
function swap(list,i,j) {
	var temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

/*
* 三数取中,把中间的数放到start中
*/
function chooseMiddle(list,start,middle,end) {
	// 最后为中，小，大；
	if(list == null && list.length == 0) {
		console.log("list error");
		return 0;
	}
	var middleNum = list[start];
	if(list[middle] > list[end]) {
		swap(list,middle,end);
	}
	if(list[start] > list[end]) {
		swap(list,start,end);
	}
	if(list[middle] > list[start]) {
		swap(list,start,middle);
	}
}

function quick2(list,start,end) {
	var mid = Math.floor(((end-start+1)/2)+start);
	chooseMiddle(list,start,mid,end);
	var flag = list[start],
		i = start,
		j = end+1;
	if(start < end){
		while(i < j) {
			// 从前向后找，找到比基准大的数
			while(i < end && list[++i] <= flag);
			// 从后向前找，找到比基准小的数
			while(j > start && list[--j] >= flag);
			// 交换两个数
			if(i < j) {
				swap(list,i,j);
			}else {
				break;
			}
		}
		swap(list,start,j);
		quick2(list,start,j);
		quick2(list,j+1,end);
	}
	
}
function quickSort2(list) {
	quick2(list,0,list.length-1);
	return list;
}

归并排序

思路：将两个或两个以上的有序表合并成一个新的有序表，即把待排序列分成若干个子序列，每个子序列都是有序的，然后再把有序的子序列合并成整体有序序列。

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 merge(left,right){
	var result = [];
	while(left.length > 0 && right.length > 0) {
		if (left[0] < right[0]) {
			result.push(left.shift());
		}else{
			result.push(right.shift());
		}
		
	}
	result = result.concat(left,right);
	return result;
}

/*
* 对数组进行拆分
*/
function mergeSort(list){
	// 当数组只有一个元素的时候就返回该数组
	if(list.length == 1) {
		return list;
	}
	// 否则把数组分成左右两部分
	var middle = Math.floor(list.length/2);
	var left = list.slice(0,middle),
		right = list.slice(middle);
	// 对左右两边进行拆分后进行归并排序
	return merge(mergeSort(left),mergeSort(right));
}

基数排序

思路：将所有的待比较序列统一为同样的数字长度，然后从最低位开始，一次进行一次排序，这样，从最低位一直排到最高位以后，就变成了一个有序序列。

两大查找算法

折半查找法（二分查找法）

思路：折半查找算法要求查找表的数据是线性结构存储，还要求查找表中的顺序是由小到大排序（由大到小排序）。首先设两个标志，low和height，表示最低索引和最高索引，然后取中间位置索引middle，判断middle处的值是否与所要查找的数相同，相同则结束查找，middle处的值比所要查找的值小就把low设为middle+1，如果middle处的值比所要查找的值大就把height设为middle-1，然后再新区间继续查到，直到找到或者low>height找不到所要查找的值结束查找。

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
/*
* 折半查找法
*/
function binarySearch(list,key,low,height) {
	var mid = Math.floor((low+height)/2);
	if (low > height) {
		console.log('查找失败！');
		return -1;
	}
	if(list[mid] == key) {
		// 找到要查找的值
		return mid;
	}else if(list[mid] < key) {
		// 所要查找的值比中间值大
		low = mid + 1;
		return binarySearch(list,key,low,height);
	}else if(list[mid] > key) {
		// 所要查找的值比中间值小
		height = mid - 1;
		return binarySearch(list,key,low,height);
	}
}
function BinSearch(list,key) {
	var result = null;
	result = binarySearch(list,key,0,list.length-1);
	console.log('查找结果：'+result);
}

二叉查找树查找法

思路：首先先来讲一下二叉查找树的定义，如下
1.如果根节点的左子树非空，则左子树所有节点的值小于根节点；
2.如果根节点的右子树非空，则右子树所有节点的值大于根节点；
3.左右子树分别为一棵二叉树；
二叉查找树的查找：若二叉查找树为空，则查找失败，若所要查找的值等于根节点的值，则查找成功，若给定值下于根节点的值，则继续在左子树递归查找，若给定值大于根节点的值，则继续在右子树上递归查找。