快速排序

发表于2021-12-14更新于2021-12-15

快速排序：

快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分割版本。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

  1. 从数列中挑出一个元素，称为“基准”（pivot），
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

PHP 实现：

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 quickSort(array $array):array
{
	$count = count($array);
	if($count < 2){
		return $array;
	}

	$leftArray = $rightArray = [];
	$indexValue = $array[0];
	for ($i=1; $i < $count; $i++) { 
		if($array[$i] < $indexValue){
			$leftArray[] = $array[$i];
		} else {
			$rightArray[] = $array[$i];
		}
	}

	$leftArray = quickSort($leftArray);
	$rightArray = quickSort($rightArray);

	return array_merge($leftArray, [$indexValue], $rightArray);
}

var_export(quickSort([42323, 34, 45, 24, 45]));

Python 实现：

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
def quick_sort(array, l=0, r=False):
    length = len(array)
    left = l or 0
    right = r or length - 1

    if left < right:
        pivot = partition(array, left, right)
        quick_sort(array, left, pivot-1)
        quick_sort(array, pivot + 1, right)

    return array


def partition(array, left, right):
    right_value = array[right]
    i = left
    index = left
    while i < right:
        if array[i] < right_value:
            swap(array, i, index)
            index = index + 1
        i = i + 1

    swap(array, right, index)

    return index


def swap(array, i, j):
    array[i], array[j] = array[j], array[i]


a = quick_sort([2, 12, 32, 15, 34, 1, 0, 352, 32])
print(a)

JavaScript 实现：

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
60
61
unction quickSort(array, l, r){  
  var len = array.length;
  var left = l || 0;
  var right = r || len - 1;
  
  if(left < right){
    pivotIndex = partition(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
  }
 
  return array;
}

function partition(array, left, right){
  const value = array[right]
  var pivotIndex = left;
  for(var i = left; i < right; i++){
    if(array[i] < value){
      swap(array, i, pivotIndex);
      pivotIndex++;
    }
  }
  
  swap(array, right, pivotIndex);
  
  return pivotIndex;
}

function swap(array, i, j){
  const temp = array[i]
  array[i] = array[j]
  array[j] = temp
}

<<------------------------------------------------------->>
function quickSort2(array){
  var len = array.length
  if(len < 2){
    return array;   
  }
  
  var left = [], right = [];
  var value = array[0]
  
  for(var i = 1; i < len; i++){
    if(array[i] < value){
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }
  
  left = quickSort2(left);
  right = quickSort2(right);
  
  return left.concat([value], right)
}

console.log(quickSort([21, 23, 3, 2, 34, 3, 45, 1, 0]))
console.log(quickSort2([21, 23, 3, 2, 34, 3, 45, 1, 0]))