合理假设

对于任意无序数组中的任意一个元素,如何确定它在排序后的索引位置?
无序数组
通常思路是先对无序数组排序,后遍历该有序数组,比较与给定的元素值,得到有序索引值。

那么,是否存在一种不对无序数组排序,就可知其指定元素在排序后的索引位置?
对于一个无序数组而言,最简单莫过于对该数组中小于指定元素的个数进行计数,
该数字即是从小到大有序后的索引位,如上数组小于25的数有4个,那么排序后25值的索引为4

不排序求排序后位置

有序的基础,是按照一定顺序有规律排序。假定是升序,那么排序必为如 a < b <c ,
即,只要找到该值比其前面元素大,比后面的元素小,就可确定它在有序数组中的位置

arr = [25, 84, 21, 46, 13, 27, 68, 35, 20]
source = [...arr]
// 初始状态 ,假定求任意值v在排序后的位置
v = arr[0]	
i = 0
j = arr.length - 1


while (true) {

  // 先检测
  while (j >= 0) {
    if (arr[j] <= v) {
      arr[i] = arr[j]
      break;
    }
    j--;
  }

  // 中止条件检测判断必须在中间
  if (i >= j) {
    arr[i] = v
    console.log(i, j)
    console.log('排序后的索引', i, ' 值', v)
    break
  }
  
  while (i <= arr.length - 1) {
    if (arr[i] >= v) {
      arr[j] = arr[i]
      break
    }
    i++
  }
}


分别打印源数组,查找后的数组,排序后的数组

console.log(source)
console.log(arr)
console.log(arr.sort())

效果

3 2
排序后的索引 3  值 25
[ 25, 84, 21, 46, 13, 27, 68, 35, 20 ]			// source
[ 20, 13, 21, 25, 46, 27, 68, 35, 84 ]			// search
[ 13, 20, 21, 25, 27, 35, 46, 68, 84 ]			// sort

改进

在一段区间求指定值在排序后的索引位,本质上是看区间内有多个元素比该值小的元素个数,简化为golang代码

// 数据源
// left  区间起始索引
// right 区间终止索引
func partitiontt(arr []int, left, right int) int {
	// 目标索引
	pivot := left
	// 右区
	index := pivot + 1
	for i := index; i <= right; i++ {
		if arr[i] < arr[pivot] {
			// 比基准目标值小次数
			index += 1
		}
	}
	// -1 消除偏移量
	return index - 1
}

查找分析

i,j
i=0j--

必要性

比较源数据 找 25,在上述查找交换,后变化的search

[ 25, 84, 21, 46, 13, 27, 68, 35, 20 ]			// source
[ 20, 13, 21, 25, 46, 27, 68, 35, 84 ]			// search
[ 13, 20, 21, 25, 27, 35, 46, 68, 84 ]			// sort

达到两个如下作用

  • 给定数组i指针向右,j指针向左,依据排序规则,在j,i 交叉时,可断定基准值在排序后的位置(25)
  • 上述操作之后,基准值25左边的数比它小,右边数比它大,形成了两个区,只需要对这两个区做同样的操作,可裁定出2个有序位及值
  • 循环重复,类似一棵二叉树,由始至末,则分别裁定1,2,4… 个数的有序位,直至只有出现1个或2个数的末区

比基准值小,可确定它们的索引位一定在基准值的左边

基本思想: 分治递归,每一层以类似2叉树的形式,确定n个有序数及位置

快排实现

golang实现思路

  1. 先找寻找分治点索引,将合适的数据送到适的位置
  2. 分区递归,重复1的动作,直到分区元素为0或1个实现有序
func quickSort(arr []int) []int {
    return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
    if left < right {
        partitionIndex := partition(arr, left, right)
        _quickSort(arr, left, partitionIndex-1)
        _quickSort(arr, partitionIndex+1, right)
    }
    return arr
}

func partition(arr []int, left, right int) int {
    pivot := left
    index := pivot + 1
	// 单指针定位
    for i := index; i <= right; i++ {
        if arr[i] < arr[pivot] {
        	// 以基准值作为交换参考,将所有小于基准值的数前移,
            swap(arr, i, index)
            // 索引
            index += 1
        }
    }
    // 将基准值调整到它最终要到的有序目标位置
    // 达到区间内基准值左侧比它小右边比它大,实现双指值双向移动的效果
    swap(arr, pivot, index-1)
    return index - 1
}

func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

小结

  • 寻找分治点在排序后的索引位置及并填充(基准值)
  • 分区规则,左侧比分治点小(大)右侧比分治点大(小)
  • 递归前两步,直到各区只余下一个元素自然达到有序之目的

附录

快排对有众多内置函数的php,写起来更简单

function quickSort($arr)
{
    if (count($arr) <= 1)
        return $arr;
    $middle = $arr[0];
    $leftArray = [];
    $rightArray = [];

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] > $middle)
            $rightArray[] = $arr[$i];
        else
            $leftArray[] = $arr[$i];
    }
    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);
    
    return array_merge($leftArray,[$middle], $rightArray);
}