快速排序（Quicksort）的Javascript实现

日本程序员norahiko，写了一个排序算法的动画演示，非常有趣。

这个周末，我就用它当做教材，好好学习了一下各种排序算法。

排序算法（Sorting algorithm）是计算机科学最古老、最基本的课题之一。要想成为合格的程序员，就必须理解和掌握各种排序算法。

目前，最常见的排序算法大概有七八种，其中"快速排序"（Quicksort）使用得最广泛，速度也较快。它是图灵奖得主C. A. R. Hoare（1934--）于1960时提出来的。

"快速排序"的思想很简单，整个排序过程只需要三步：

（1）在数据集之中，选择一个元素作为"基准"（pivot）。

（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。

（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/webkf/script/

时间： 2024-11-02 04:24:20

快速排序（Quicksort）的Javascript实现的相关文章

PHP快速排序quicksort实例详解_php技巧

本文实例讲述了PHP快速排序quicksort.分享给大家供大家参考,具体如下: quicksort 在快速排序算法中,使用了分治策略.首先把序列分成两个子序列,递归地对子序列进行排序,直到整个序列排序结束.(即一分为二的思想) 步骤如下: 在序列中选择一个关键元素做为轴: 对序列进行重新排序,将比轴小的元素移到轴的前边,比轴大的元素移动到轴的后面.在进行划分之后,轴便在它最终的位置上: 递归地对两个子序列进行重新排序:含有较小元素的子序列和含有较大元素的子序列. 比如序列$arr: 5 3 0

快速排序(quicksort)算法实现

快速排序(quicksort)是分治法的典型例子,它的主要思想是将一个待排序的数组以数组的某一个元素X为轴,使这个轴的左侧元素都比X大,而右侧元素都比X小(从大到小排序).然后以这个X在变换后数组的位置i分为左右两个子数组,再分别进行快速排序,直到子数组中只有一个元素为止. 快速排序算法如下 void quicksort(int A[], int p, int r) { int i; if(p < r) { i = partition(A, p,

Java 快速排序(QuickSort)原理及实现代码_java

快速排序(QuickSort )是常用到的效率比较高的一种排序算法,在面试过程中也经常提及.下面就详细讲解一下他的原理.给出一个Java版本的实现. 快速排序思想: 通过对数据元素集合Rn 进行一趟排序划分出独立的两个部分.其中一个部分的关键字比另一部分的关键字小.然后再分别对两个部分的关键字进行一趟排序,直到独立的元素只有一个,此时整个元素集合有序. 快速排序的过程--挖坑填数法(这是一个很形象的名称),对一个元素集合R[ low ... high ] ,首先取一个数(一般是R[low] )做

快速排序 php与javascript的不同之处_javascript技巧

1. PHP 复制代码代码如下: <?php $unsorted = array(2,4,5,63,4,5,63,2,4,43); function quicksort($array) { if (count($array) == 0) return array(); $pivot = $array[0]; $left = $right = array(); for ($i = 1; $i < count($array); $i++) { if ($array[$i] < $pivot

JavaScript版几种常见排序算法分享

说明 · 每个浏览器测试得出的数据会不一样.比如我用chrome 测试一般快速排序都会最快,IE 则根据数组长度有可能希尔最快. · 不要用太大数据去测试冒泡排序(浏览器崩溃了我不管) 个人理解 · 冒泡排序:最简单,也最慢,貌似长度小于7最优 · 插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势 · 快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合 · 希尔排序:在非chrome下数组长度小于1000,希尔排序比快速更快 · 系统

javascript数组排序汇总_javascript技巧

javascript数组排序汇总 //排序算法 window.onload = function(){ var array = [0,1,2,44,4, 324,5,65,6,6, 34,4,5,6,2, 43,5,6,62,43, 5,1,4,51,56, 76,7,7,2,1, 45,4,6,7,8]; //var array = [4,2,5,1,0,3]; console.log('原始数组'); console.log(array); array = sorting.shellSort

Javascript中的常见排序算法_javascript技巧

具体代码及比较如下所示: 复制代码代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

分治法-快速排序

问题:应用快速排序方法对一个记录序列进行生序排序(运用分治法) 策略:请读者先了解快速排序的基本概念(<数据结构>或百度百科) 如下所示是一个快速排序的完整例子:(化成中间一个数,左边的比他小,右边的比他大) 23 13 35 6 19 50 28 [19 13 6] 23 [35 50 28] [6 13] 19 23 [28] 35 [50] 6 [13] 19 23 28 35 50 6 13 19 23 28 35 50 实现代码: #include<stdio.h> in

c-检验快速排序及其改进算法时间效率问题

问题描述检验快速排序及其改进算法时间效率问题其中正序逆序的时间效率均正确,乱序的部分就有错误.但是正序逆序及乱序的检验部分基本都是复制粘贴,随机数产生的地方好像也没有什么问题.但运行后只有乱序的改进算法比原算法的时间慢.跪求指导,哪一部分除了问题. 具体代码如下: #include<iostream> #include <ctime> #include <stdlib.h> #define Maxsize 20000 using namespace std; typ

Java排序算法快速排序

排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.下面让我们一起来看快速排序. AD: 快速排序(Quicksort)是对冒泡排序的一种改进.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.快速排序不稳定,O(log(n))的额外空间,时间复杂度为O(nlog