站内搜索: 请输入搜索关键词

当前页面: 开发资料首页 → Javascript 专题 → javascript 的几种排序方法

javascript 的几种排序方法

摘要: javascript 的几种排序方法
<tr> <td>

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
　　输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

这里，我们简单介绍几种排序方法，直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序，文中所提及的代码在IE6下测试通过。

直接插入排序基本思想

假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

算法描述

function InsertSort(arr) { //插入排序->直接插入法排序
var st = new Date();
var temp, j;
for(var i=1; i if((arr[i]) < (arr[i-1])) {
temp = arr[i];
j = i-1;
do {
arr[j+1] = arr[j];
j--;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+1] = temp;
}//endif
}
status = (new Date() - st) + ' ms';
return arr;
}

希尔排序基本思想

　 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2 　该方法实质上是一种分组插入方法。

算法描述

function ShellSort(arr) { //插入排序->希儿排序
var st = new Date();
var increment = arr.length;
do {
increment = (increment/3|0) + 1;
arr = ShellPass(arr, increment);
}
while (increment > 1)
status = (new Date() - st) + ' ms';
return arr;
}
function ShellPass(arr, d) { //希儿排序分段执行函数
var temp, j;
for(var i=d; i if((arr[i]) < (arr[i-d])) {
temp = arr[i]; j = i-d;
do {
arr[j+d] = arr[j];
j = j-d;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+d] = temp;
}//endif
}
return arr;
}

冒泡排序基本思想

将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。


算法描述

function BubbleSort(arr) { //交换排序->冒泡排序
var st = new Date();
var temp;
var exchange;
for(var i=0; i exchange = false;
for(var j=arr.length-2; j>=i; j--) {
if((arr[j+1]) < (arr[j])) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
}

快速排序基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

算法描述

function QuickSort(arr) { //交换排序->快速排序
if (arguments.length>1) {
var low = arguments[1];
var high = arguments[2];
} else {
var low = 0;
var high = arr.length-1;
}
if(low < high){
// function Partition
var i = low;
var j = high;
var pivot = arr[i];
while(i while(i=pivot)
j--;
if(i arr[i++] = arr[j];
while(i i++;
if(i arr[j--] = arr[i];
}//endwhile
arr[i] = pivot;
// end function
var pivotpos = i; //Partition(arr，low，high);
QuickSort(arr, low, pivotpos-1);
QuickSort(arr, pivotpos+1, high);
} else
return;
return arr;
}

直接选择排序基本思想

　n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
　　……
③第i趟排序
　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

算法描述

function SelectSort(arr) { //选择排序->直接选择排序
var st = new Date();
var temp;
for(var i=0; i var k = i;
for(var j=i+1; j if((arr[j]) < (arr[k]))
k = j;
}
if (k != i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
status = (new Date() - st) + ' ms';
return arr;
}



排序

排序


插入排序

直接插入排序
请输入一段要排序的字符，用半角逗号隔开
<input name=insert type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">

<input type=button value=" 排序 " onclick="alert(InsertSort(insert.value.split(',')));">

希儿排序
<input name=Shell type=text size=100 value="g,v,u,f,p,o,i,a,t,j">

<input type=button value=" 排序 " onclick="alert(ShellSort(Shell.value.split(',')));">

交换排序冒泡排序

<input name=bubble type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">

<input type=button value=" 排序 " onclick="alert(BubbleSort(bubble.value.split(',')));">

快速排序
 <input name=quick type=text size=100 value="3,1,5,4,6">

<input type=button value=" 排序 " onclick="alert(QuickSortDemo(quick.value.split(',')));">


选择排序直接选择排序

<input name=select1 type=text size=100 value="g,v,u,f,p,o,i,a,t,j,e,l,k">

<input type=button value=" 排序 " onclick="alert(SelectSort(select1.value.split(',')));">

... ...

<script>
function InsertSort(arr) { //插入排序->直接插入法排序
var st = new Date();
var temp, j;
for(var i=1; i if((arr[i]) < (arr[i-1])) {
temp = arr[i];
j = i-1;
do {
arr[j+1] = arr[j];
j--;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+1] = temp;
}//endif
}
status = (new Date() - st) + ' ms';
return arr;
}

function ShellSort(arr) { //插入排序->希儿排序
var st = new Date();
var increment = arr.length;
do {
increment = (increment/3|0) + 1;
arr = ShellPass(arr, increment);
}
while (increment > 1)
status = (new Date() - st) + ' ms';
return arr;
}

function ShellPass(arr, d) { //希儿排序分段执行函数
var temp, j;
for(var i=d; i if((arr[i]) < (arr[i-d])) {
temp = arr[i]; j = i-d;
do {
arr[j+d] = arr[j];
j = j-d;
}
while (j>-1 && (temp) < (arr[j]));
arr[j+d] = temp;
}//endif
}
return arr;
}

function BubbleSort(arr) { //交换排序->冒泡排序
var st = new Date();
var temp;
var exchange;
for(var i=0; i exchange = false;
for(var j=arr.length-2; j>=i; j--) {
if((arr[j+1]) < (arr[j])) {
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
exchange = true;
}
}
if(!exchange) break;
}
status = (new Date() - st) + ' ms';
return arr;
}

function QuickSortDemo(arr) {
var st = new Date();
var result = QuickSort(arr);
status = (new Date() - st) + ' ms';
return result;
}

function QuickSort(arr) { //交换排序->快速排序
if (arguments.length>1) {
var low = arguments[1];
var high = arguments[2];
} else {
var low = 0;
var high = arr.length-1;
}
if(low < high){
// function Partition
var i = low;
var j = high;
var pivot = arr[i];
while(i while(i=pivot)
j--;
if(i arr[i++] = arr[j];
while(i i++;
if(i arr[j--] = arr[i];
}//endwhile
arr[i] = pivot;
// end function
var pivotpos = i; //Partition(arr，low，high);
QuickSort(arr, low, pivotpos-1);
QuickSort(arr, pivotpos+1, high);
} else
return;
return arr;
}

/*function Partition(arr, i, j) { //快速排序, 对待排序的数组进行划分
var pivot = arr[i];
while(i while(arr[j]>=pivot)
j--;
if(i arr[i++] = arr[j];
while(arr[i]<=pivot)
i++;
if(i arr[j--] = arr[i];
}
arr[i] = pivot;
return arr;
}*/

function SelectSort(arr) { //选择排序->直接选择排序
var st = new Date();
var temp;
for(var i=0; i var k = i;
for(var j=i+1; j if((arr[j]) < (arr[k]))
k = j;
}
if (k != i){
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
status = (new Date() - st) + ' ms';
return arr;
}

function unicode(str) {//求字符串的unicode码
var uni=0;
for(var i=0; i uni += str.charCodeAt(i)/6553.5 * Math.pow(10, str.length-i);
}
return uni;
}
</script>

</td> </tr> </table>
↑返回目录
前一篇: 关于字符串的几个有用函数
后一篇: JavaScript 的变量