快速排序
快速排序 由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是对冒泡排序算法的一种改进，冒泡算法各位读者应该不会太陌生。在日常编码生活中喜闻乐见的排序算法，时间复杂度为O(n*n)，其中n为数组的长度。同冒泡排序一样的是，快速排序也是原址排序，只需要1个额外的内存交换单元即可。
假设数组Array[1,N]，使用快速排序对其进行排序的核心思路是在数组Array中取一个值作为特征值，就像绩效评定之前一定会有个标准一样，这个值就是标准，所有比它小的得在它的左边，所有比它大的在它的右边，如此数组就被分割成Array[1,keyIndex - 1],key,Array[keyIndex + 1]，然后再递归对Array[1,keyIndex - 1]和Array[keyIndex + 1]继续按照这个原则进行分割排列，则最终得到的序列一定是一个从左到右顺序增长的序列，完成排序目的。
下面，简单描述算法步骤
- 1、取数组的最后一个值作为特征值
- 2、设置数组起始值的位置为左侧探询指针，数组末位的前一位的位置为右侧探询指针
- 3、从左侧进行探询，如果值比特征值小则指针位置右移，直到找到第一个比特征值大的值，然后停住
- 4、从右侧进行探询，如果值比特征值大则指针位置左移，直到找到第一个比特征值小的值，然后停住
- 5、判断左侧指针是否已经超出要搜寻的数组范围，如果没有超出，则将左侧指针位置的数值和特征值进行交换
- 6、以左侧指针停住的位置作为数组的分隔位置，将数组分隔成2段，每一段继续处理
代码
(以下代码经过本人测试，可以使用nodejs环境运行)
/**
* Created by cluo on 2017/2/22.
*/
var arr = [5,2,4,6,1,3];
//var arr = [6,5,4,3,2,1];
/**
* 对数组进行划分，去除一个特征值，左边是比它小，右边是比它大
* @param arr : 数组片段
* @param start : 数组片段起始位置
* @param end : 数组片段结束位置
* */
function partition(arr,start,end) {
//处理到单个数据时结束处理
if(start >= end){
return;
}
//以数组片段最后一个值作为其他值比较的参考值
var key = arr[end];
//设置首尾的搜索指针
var left = start;
var right = end - 1;
//从左和右同事遍历数组，对数组进行分割
while (left <= right){
//搜寻左边第一个比特征值大数值在数组中的位置
while(arr[left] <= key){
left++;
}
//搜寻右边第一个比特征值小数值在数组中的位置
while(arr[right] > key){
right--;
}
//如果比较后是正常的顺序则直接跳出循环探测
if(left >= right){
break;
}else{
//把左边比特征值大和右边比特征值小的值进行交换
exchange(arr,left,right);
}
}
//到算法终止条件时，将关键值跟终结位置进行值交换
if(left <= end){
exchange(arr,left,end);
//对左侧和右侧的数组片段进行递归处理
partition(arr,start,left - 1);
partition(arr,left + 1,end);
}else{
//特征值刚好在最后一个，且在比较的数组片段中为最大值
partition(arr,start,end - 1);
}
}
/**
* 交换数组中的2个位置的数据
* */
function exchange(arr,i,j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**
* 对给定的数组进行快速排序
* @param arr : 待排序的数组
* @param flag : 顺序or逆序
* */
const quickSort = function(arr) {
partition(arr,0,arr.length - 1);
};
//测试算法
quickSort(arr);
快速排序算法是目前来讲比较快的排序算法，且对于空间的占用较少，但是它不稳定，算法的效率受源数据的特征影响较大。
