首页 > 代码库 > 快速排序之算法
快速排序之算法
一、定义
快速排序是一种基于比较的排序算法，通过选取平均数将整个数据集划分成两部分，并把所有小于平均数的元素移动到平均数左边；在左半部分重复上述操作，直到左边部分的排序完成后，对右边部分执行相同的操作。
二、算法思想
先确定一个“支点”，将所有小于“支点”的值都放在该点的左侧，大于“支点”的值都放在该点的右侧，然后对左右两侧不断重复这个过程，直到所有排序完成。
三、具体实现
function quickSort1(arr) { var len = arr.length; if (len < 2) { return arr; } var midIndex = Math.floor(len / 2); // 中间元素的索引值 var baseValue = http://www.mamicode.com/arr.splice(midIndex, 1); // 基准值 var left = []; // 保存小于基准值元素 var right = []; // 保存大于或等于基准值元素 for (var i = 0; i < arr.length; i++) { if (arr[i] < baseValue) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort1(left).concat(baseValue, quickSort1(right));}console.log(quickSort1([3,115,9,2,11,6,3,19]));
function quickSort2(arr, left, right) { var len = arr.length, partitionIndex, left = typeof left != ‘number‘ ? 0 : left, right = typeof right != ‘number‘ ? len - 1 : right; if (left < right) { partitionIndex = partition(arr, left, right); quickSort2(arr, left, partitionIndex-1); quickSort2(arr, partitionIndex+1, right); } return arr;}function partition(arr, left ,right) { //分区操作 var pivot = left, //设定基准值（pivot） index = pivot + 1; for (var i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index-1;}function swap(arr, i, j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}console.log(quickSort2([3,115,91,2,11,6,3,19]));
四、效率分析
快速排序排序效率非常高。虽然它运行最糟糕时将达到O(n²)的时间复杂度，但通常，平均来看，它的时间复杂为O(nlogn)，比同样为O(nlogn)时间复杂度的归并排序还要快。快速排序似乎更偏爱乱序的数列，越是乱序的数列，它相比其他排序而言，相对效率更高。
Chrome的v8引擎为了高效排序，在排序数据超过了10条时，便会采用快速排序，对于10条及以下的数据采用的便是插入排序。
同选择排序相似，快速排序每次交换的元素都有可能不是相邻的，因此它有可能打破原来值为相同的元素之间的顺序。因此，快速排序并不稳定。
1、时间复杂度
最坏的情况：时间复杂度为O(n²)；
最佳的情况：时间复杂度为O(n)；
平均来讲，时间复杂度为O(nlogn)。
2、空间复杂度
空间复杂度为常量O(nlogn)。
快速排序之算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。