图解数组的快速排序【附源代码】

介绍

快速排序属于排序算法中利用二分思想来实现的排序算法之一，他的时间时间复杂度介于O(nlogn)到O(n^2)之间，它属于一种不稳定排序但是思路特别适合我们学习。

原理

快速排序的排序思想是在数组中挑选一个值作为中间值，比如当我们的需求是从大到小排序的时候，它会从前和后两个方向分别和中间值进行对比，将比中间值大的放在数组的左侧，比中间值小的放在数组的右侧，这样在一次整理之后数组就会变成介于中间值两册的两种大小的数组，然后再一次从两段数据中按照同样的思路选择中间值并且重复上面的交换，直到所有的交换都完成这样便完成了排序。

图解

根据上面的描述我们发现快速排序其实就是不停的将数据分散成大小两个界限然后无限的分，知道每一个数据都分配完毕。所以我们以一个常见的纯数字数组举例来图解一下快速排序的步骤。

根据上面的数组我们来研究一下快速排序的过程，首先我们就拿第一个位置的数据做中间值来进行标记，使用一个temp变量来记录这个数据

记录之后我们从右侧开始与中间值temp进行对比如果右侧的值比10小则直接向左移动指针，直到有数据比10大的时候

当右指针指向的元素比temp的值大的时候将右侧指针的数据设置到左侧指针位置，然后左指针开始移动重复又指针的动作直到找到比10小的数据复制到右侧指针当前的位置

下图便是继续移动指针到最后两个指针重合的过程

当最终指针重合的时候我们记录当前的位置2，测试temp的10要放在指针重合的位置，这样我们第一次整理就完成了，完成之后左侧的所有数据都比10大，右侧的所有数据都比10小，接下来我们需要利用递归的手段从左右两侧进一步拆分数组，并且按照相同的步骤进行替换直到所有的指针重合即结束。

代码实现

今天我们采用JS作为实现语言来实现快速排序的代码代码如下。

/**
 * @param {Object} arr 原数组
 * @param {Object} left 左指针位置
 * @param {Object} right 右指针位置
 */
function sort(arr,left,right){
	let oldLeft = left
	let oldRight = right
	let temp = arr[left]
	// 当指针不重合时进行指针移动和交换
	while(left<right){
		// 当右侧的内容比temp小的时候移动指针
		while(left<right && arr[right]<=temp){
			right--
		}
		// 跳出循环代表需要交换了
		arr[left] = arr[right]
		// 右侧交换之后左侧指针移动
		while(left<right && arr[left]>=temp){
			left++
		}
		// 移动到位置交换数据
		arr[right] = arr[left]
	}
	// 指针重合之后将temp复位
	arr[left] = temp
	// 通过中间值分左右两侧进一步递归
	let middle = left
	if(oldLeft<oldRight){
		sort(arr,oldLeft,middle)
		sort(arr,middle+1,oldRight)
	}
}

尾声

今天的分享到此为止，快速排序的思路很清晰，只要掌握好递归的基础和交换的规则时很容易进行实现的。下次我们再分享其他的数据结构和算法内容。

最后送大家一句话：【算法主要以思想为主，语言只是一种实现方式，不要被编程语言限制了自己的思想】