快速排序

快速排序:

image

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

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

步骤为:

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

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

PHP 实现:

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 实现:

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 实现:

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]))

黄铭博客
请先登录后发表评论
  • latest comments
  • 总共0条评论