代码详解JavaScript如何实现快速排序

来源：动视网责编：小采时间：2020-11-27 19:56:09

代码详解JavaScript如何实现快速排序

代码详解JavaScript如何实现快速排序:本篇文章给大家分享的内容是JavaScript如何实现快速排序，有着一定的参考价值，有需要的朋友可以参考一下偶然看到阮一峰老师博客中几年前的一个快速排序算法，每次循环一次都要创建两个额外数组，如果数据量大的话要占用不少额外内存。但是数组是引用类型，

推荐度：

点击下载本文 文档为doc格式

导读代码详解JavaScript如何实现快速排序:本篇文章给大家分享的内容是JavaScript如何实现快速排序，有着一定的参考价值，有需要的朋友可以参考一下偶然看到阮一峰老师博客中几年前的一个快速排序算法，每次循环一次都要创建两个额外数组，如果数据量大的话要占用不少额外内存。但是数组是引用类型，

本篇文章给大家分享的内容是JavaScript如何实现快速排序，有着一定的参考价值，有需要的朋友可以参考一下

偶然看到阮一峰老师博客中几年前的一个快速排序算法，每次循环一次都要创建两个额外数组，如果数据量大的话要占用不少额外内存。但是数组是引用类型，是可修改的，可以直接操作原数组本身来节约内存。

快速排序方法的关键在于选取一个值，将整个数组分为两部分，小的在左，大的在右，下面就是这个函数的写法：

//该函数的主要目的是交换数组中两个元素的位置
function swap(arr, index1, index2) {

 let data = arr[index1];
 arr[index1] = arr[index2];
 arr[index2] = arr[index1];

 //数组是引用类型，允许修改原数组。
}

//选取随机值，将数组分为两部分
function partition(arr, start, end) {
 let keyIndex = end,
 key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数，也可以真的随机选取，见下一行
 // let keyIndex = Math.floor(Math.random() * (end - start)) + start;

 let i = start,
 j = end,
 order = true;
 //当order为true时正向筛选，当order为false时逆向筛选
 //先从正向开始，因为我们把key值保存到了数组的结尾处。
 while(i != j) {
 if(order) {
 //正向筛选
 if (arr[i]>key) {
 swap(arr, i, j); //将大于key的数字和key进行交换
 order = false;
 } else {
 i++;
 }

 } else {
 //逆向筛选
 if(arr[j]<key) {
 swap(arr, i, j); //将小于key的数字和key进行交换
 order = true;
 } else {
 j--;
 }
 }
 }
 return i;//返回key值最终的位置
}

观察分组算法partition不难发现，其实i和j位置上始终有一个存着key值，然后和比它大或者比它小的值进行交换。那么我们也可以将其写成一个单向的分组方法：

function partition2(arr, start, end) {
 let keyIndex = end,
 key = arr[end];
 let i = start -1,
 j = start;
 for (;j<end;j++) {
 if (arr[j]< key) {
 // i位置的值永远比key值小
 i++;
 if (i != j) {
 swap(arr, i, j);
 }
 }
 } 
 ++i;
 swap(arr, i, end);

 return i; //返回key值最终的位置
}

接下来递归调用分组函数，将整个数组排序：

function quickSort(arr, start, end) {
 if (start == end) return;
 let index = partition(arr, start, end);
 if (index > start){
 quickSort(arr, start, index-1);
 }
 if (index<end) {
 quickSort(arr, index+1, end);
 }
}

代码详解JavaScript如何实现快速排序

推荐度：

点击下载本文 文档为doc格式

标签：讲解实现代码

热门焦点

代码详解JavaScript如何实现快速排序

代码详解JavaScript如何实现快速排序

代码详解JavaScript如何实现快速排序

最新推荐

猜你喜欢

热门推荐