javascript实现快速排序算法

热网热热 5评论
快速排序也是计算机科学领域中经典的排序算法,在1962年就被提出。快速排序算法是交换排序算法中的一种,同时它也是对冒泡排序算法的改进。
设计算法要考虑的就是空间复杂度和时间复杂度,快速排序听名字应该在速度方面更优于冒泡排序吧,下面我们来使用js代码来实现快速排序算法。

快速排序思想

快速排序思想是在待排序序列A[0,n]中,选择一个基准位置记为i,然后以A[i]作为基准,将待排序无序区换分成两个较小的无序区,分别为A[0,m]和A[m+1,n],并且左边无序区的所有值小于A[i],右边无序区的所有值均大于A[i]。i值最终就在m位置上,这就是第一趟排序,如此返回进行直到所有无序区的值排好为止。
一趟快速排序的具体操作是:设两个指针i和j,它们的初值分别为low和high,基准记录x=R[i],首先从j所指位置起向前搜索找到第一个关键字小于基准x.key的记录存入当前i所指向的位置上,i自增l,然后再从i所指位置起向后搜索,找到第一个关键字大于x.key的记录存入当前j所指向的位置上,j自减1;重复这两步,直至i等于j为止。

JavaScript代码实现快速排序算法

JavaScript代码实现快速排序算法,这次我们使用while循环来实现。
function Partition(R,i,j){
var x = R[i]; //记录标准值
while(i < j){ //每一趟排序控制
while(i < j && R[j] >= x){ //根据J从后往前,寻找小于基准值的值直到找到或者未找到为止
j--;
}
if(i<j){
R[i] = R[j]; //此处,只要是 存着 i < j,就会存在 R[j] < x,所以交换 i和j位置的值
i++;
}
while(i < j && R[i]<= x){ //这里 从i开始从前往后查找大于基准数的值 逻辑与之前一致。
i++;
}
if(i<j){
R[j] = R[i];
j--;
}
}
R[i] = x;    //完成一趟以基准值为界,前面的所有值小于基准值,后面所有值大于基准值
return i;    //返回此时基准值的位置,用于下一趟排序的开始位置或者结束位置
}
function QuickSort(R,low,high){
if(low < high){
var p = Partition(R,low,high); //这里采用递归的方式 来处理每趟排序后的序列
QuickSort(R,low,p-1);          //递归方式排序基准值前面的无序序列
QuickSort(R,p + 1,high);       //递归方式排序基准值后面的无序序列
}
}
var a = [3,2,4,7,1,8,3,9,11,6]
QuickSort(a,0,a.length - 1)
console.log(JSON.stringify(a))//[1,2,3,3,4,6,7,8,9,11]

算法代码说明

最外层while循环循环一次,完成一个大于基准值和小于基准值两个之间的交换,以上面代码为例。
第一次i为0j为9,x为3,进入里面第一层while循环,寻找小于基准值x的值,j一步一步往前移动到j=4的时候满足条件。4位置的1放入0位置。
接下来while循环开始一步一步往后移动,查找大于基准值的值,当i=2的时候满足条件,将此时的2位置的值4,放入之前j为4的位置。
此时的数组变为了
1,2,4,7,4,8,3,9,11,6
接下来j和在交替的前后移动,满足条件就交换值,直到i>=j时就完成了一次,以基准值为分界的,前面的所有值小于基准值,后面所有值大于基准值。
此时我们就需要递归,再次对前后两个无需求进行排序即可。
快速排序

快速排序算法性能分析

算法时间复杂度
快速排序的时间复杂度为O(nlog2n)。快速排序方法被认为是排序时间效率非常高的一种方法,但是,当参加排序的原始序列已经是一个按值有序或基本有序的序列时,快速排序方法的时间效率将降到最低,这种情况下其时间复杂度为O(n2)
算法空间复杂度
快速排序的空间复杂度为O(log2n)。
算法的稳定性
快速排序方法是一种不稳定的排序方法,因为在排序过程中,不能保证之前相同值的相对位置不发生变化。

转载请注明觅施南网,javascript实现快速排序算法:https://www.rewonng.com/qianduanzhishi/153.html

查看剩余内容

相关内容推荐

猜你喜欢内容