JavaScript快速排序算法

84 阅读 0 评论 56 点赞

我是靠谱客的博主迅速盼望，这篇文章主要介绍JavaScript快速排序算法，现在分享给大家，希望可以做个参考。

说明
时间复杂度指的是一个算法执行所耗费的时间
空间复杂度指运行完一个程序所需内存的大小
稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

原理
从数组中选定一个基数，然后把数组中的每一项与此基数做比较，小的放入一个新数组，大的放入另外一个新数组。然后再采用这样的方法操作新数组。直到所有子集只剩下一个元素，排序完成。
时间复杂度，空间复杂度，稳定性
平均时间复杂度O(nlogn)
最好情况O(nlogn)
最差情况O(n*n)
空间复杂度O(logn)
稳定性：不稳定

快速排序源码：

复制代码

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
// var bubbleArr = [1,3,44,5,9,15,22,20]
function random(min,max){
    //floor() 方法可对一个数进行下舍入
	return Math.floor(Math.random() * (max - min)) + min
}
var bubbleArr = [];
for(var i = 0; i< 50000; i++){
		bubbleArr.push(random(i,i+5))
}
console.log(bubbleArr)	
function bubbleSort(bubbleArr){
	var startTime = Date.parse(new Date());
	for(var i = 0; i < bubbleArr.length; i++){
		// 实现最后面的一个位最大数字(最后一个位数组的长度减去i)
		for(var j = 0; j < bubbleArr.length-1-i; j++){
			if(bubbleArr[j] > bubbleArr[j+1]){
				var temp = bubbleArr[j]
				bubbleArr[j] = bubbleArr[j+1];
				bubbleArr[j+1] = temp
			}
		}
		// 当i = 0 时,实现最后一个数字最大,为44;
		// 当i = 1 时,实现倒数第二个数位最大，为22 ,最后一个数已不再参与排序,
	}
	var endTime = Date.parse(new Date());
	console.log('开始时间（ms）' , startTime)
	console.log('结束时间' , endTime)
	console.log('花费的时间' , endTime - startTime)
	console.log(bubbleArr)
	
}
bubbleSort(bubbleArr)