javascript?的几种排序方法

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
　　输入：n个记录R₁，R₂，…，R_n，其相应的关键字分别为K₁，K₂，…，K_n。
　　输出：R_il，R_i2，…，R_in，使得K_i1≤K_i2≤…≤K_in。(或K_i1≥K_i2≥…≥K_in)。

??? 这里，我们简单介绍几种排序方法，直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序，文中所提及的代码在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<arr.length; 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的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。
? 　该方法实质上是一种分组插入方法。

??? 算法描述

?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<arr.length; 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<arr.length; 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<j) {
????while(i<j && arr[j]>=pivot)
?????j--;
????if(i<j)
?????arr[i++] = arr[j];
????while(i<j && arr[i]<=pivot)
?????i++;
????if(i<j)
?????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<arr.length; i++) {
???var k = i;
???for(var j=i+1; j<arr.length; 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;
?}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!