L3F.WIN

Github及Hexo的使用

0%

Javascript算法 -- 01 快速排序

Javascript算法 – 01 快速排序

快速排序一

对于数组 arr1 = new Array(15,12,3,2,7,15);

  1. 选择左右边的元素为基准数,7
  2. 将小于7的放在左边,大于7的放在右边,然后将基准数放到中间
  3. 然后再重复操作从左边的数组选择一个基准点2
  4. 3比2大则放到基准树的右边
  5. 右边的数组也是一样选择12作为基准数,15比12大所以放到了12的右边
  6. 最后出来的结果就是从左到右 2 ,3,7,12,15了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
	var quickSort = function(arr) {
if (arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];

for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};

var arr1 = new Array(15,12,3,2,7,15);

console.log(quickSort(arr1));

快速排序二

  1. 初始化i = -1
  2. 循环数组,找到比支点小的数就将i向右移动一个位置,同时与下标i交换位置
  3. 循环结束后,最后将支点与i+1位置的元素进行交换位置
  4. 最后我们会得到一个由i指针作为分界点,分割成从下标0-i,和 i+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

/*数组交换*/
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}

/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function divide(A, p, r) {
const x = A[r - 1];
let i = p - 1;

for (let j = p; j < r - 1; j++) {
if (A[j] <= x) {
i++;
swap(A, i, j);
}
}

swap(A, i + 1, r - 1);

return i + 1;
}

/**
*
* @param {*} A 数组
* @param {*} p 起始下标
* @param {*} r 结束下标 + 1
*/
function qsort(A, p = 0, r) {
r = r || A.length;

if (p < r - 1) {
const q = divide(A, p, r);
qsort(A, p, q);
qsort(A, q + 1, r);
}

return A;
}

console.log(qsort(arr1, p=0, arr1.length))