快速排序（Quick Sort）
快速排序(Quick Sort)使用得最广泛，速度也较快，是图灵奖得主C.A.R.Hoare(1934-) 于1960事提出的
算法简介
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
算法描述和实现
快速排序使用分治法来吧一个串（list）分成两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为”基准“（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准值的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为（partition）操作
- 递归的（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
js代码实现
方法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| function quickSort(arr, left, right) {
if (Array.isArray(arr) && typeof left === 'number' && typeof right === 'number') {
if (left < right) {
var x = arr[right],
i = left - 1,
temp
for(var j = left ; j <= right ; j++){
if(arr[j] <= x){
i++
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
}
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
return arr
}
}
const arr = [2, 1, 3, 5, 4]
console.log(quickSort(arr, 0, arr.length - 1))
|
方法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| function quickSort2(arr){
if(arr.length <=1){
return arr
}
const middleIndex = Math.floor(arr.length/2)
const valueArr = arr.splice(middleIndex,1)
const middleVal = valueArr[0]
const left = []
const right = []
for(let i = 0 ; i < arr.length;i++){
if(arr[i]<middleVal){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort2(left).concat(valueArr,quickSort2(right))
}
const arr = [2, 1, 3, 5, 4]
console.log('quickSort2',quickSort2(arr))
|
