javascript的几种排序方法

所谓排序就是要整理文件中的记录使之按关键字递增(或递减)次序排列起来其确切定义如下

输入n个记录RR…Rn其相应的关键字分别为KK…Kn

输出RilRi…Rin使得Ki≤Ki≤…≤Kin(或Ki≥Ki≥…≥Kin)

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

直接插入排序基本思想

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

算法描述

function InsertSort(arr) { //插入排序>直接插入法排序

var st = new Date();

var temp j;

for(var i=; i<arrlength; i++) {

if((arr[i]) < (arr[i])) {

temp = arr[i];

j = i;

do {

arr[j+] = arr[j];

j;

}

while (j> && (temp) < (arr[j]));

arr[j+] = temp;

}//endif

}

status = (new Date() st) + ms;

return arr;

}

希尔排序基本思想

先取一个小于n的整数d作为第一个增量把文件的全部记录分成d个组所有距离为dl的倍数的记录放在同一个组中先在各组内进行直接插人排序然后取第二个增量d<d重复上述的分组和排序直至所取的增量dt=(dt<dtl<…<d<d)即所有记录放在同一组中进行直接插入排序为止

该方法实质上是一种分组插入方法

算法描述

function ShellSort(arr) { //插入排序>希儿排序

var st = new Date();

var increment = arrlength;

do {

increment = (increment/|) + ;

arr = ShellPass(arr increment);

}

while (increment > )

status = (new Date() st) + ms;

return arr;

}

function ShellPass(arr d) { //希儿排序分段执行函数

var temp j;

for(var i=d; i<arrlength; i++) {

if((arr[i]) < (arr[id])) {

temp = arr[i]; j = id;

do {

arr[j+d] = arr[j];

j = jd;

}

while (j> && (temp) < (arr[j]));

arr[j+d] = temp;

}//endif

}

return arr;

}

冒泡排序基本思想

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

算法描述

function BubbleSort(arr) { //交换排序>冒泡排序

var st = new Date();

var temp;

var exchange;

for(var i=; i<arrlength; i++) {

exchange = false;

for(var j=arrlength; j>=i; j) {

if((arr[j+]) < (arr[j])) {

temp = arr[j+];

arr[j+] = arr[j];

arr[j] = temp;

exchange = true;

}

}

if(!exchange) break;

}

status = (new Date() st) + ms;

return arr;

}

快速排序基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题递归地解这些子问题然后将这些子问题的解组合为原问题的解

在R[lowhigh]中任选一个记录作为基准(Pivot)以此基准将当前无序区划分为左右两个较小的子区间R[lowpivotpos)和R[pivotpos+high]并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivotkey右边的子区间中所有记录的关键字均大于等于pivotkey而基准记录pivot则位于正确的位置(pivotpos)上它无须参加后续的排序

算法描述

function QuickSort(arr) { //交换排序>快速排序

if (argumentslength>) {

var low = arguments[];

var high = arguments[];

} else {

var low = ;

var high = arrlength;

}

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(arrlowhigh);

QuickSort(arr low pivotpos);

QuickSort(arr pivotpos+ high);

} else

return;

return arr;

}

直接选择排序基本思想

n个记录的文件的直接选择排序可经过n趟直接选择排序得到有序结果

①初始状态无序区为R[n]有序区为空

②第趟排序

在无序区R[n]中选出关键字最小的记录R[k]将它与无序区的第个记录R[]交换使R[]和R[n]分别变为记录个数增加个的新有序区和记录个数减少个的新无序区

……

③第i趟排序

第i趟排序开始时当前有序区和无序区分别为R[i]和R[in](≤i≤n)该趟排序从当前无序区中选出关键字最小的记录R[k]将它与无序区的第个记录R[i]交换使R[i]和R[i+n]分别变为记录个数增加个的新有序区和记录个数减少个的新无序区

这样n个记录的文件的直接选择排序可经过n趟直接选择排序得到有序结果

算法描述

function SelectSort(arr) { //选择排序>直接选择排序

var st = new Date();

var temp;

for(var i=; i<arrlength; i++) {

var k = i;

for(var j=i+; j<arrlength; 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;

}

<style>

fieldset {

fontsize:px;

padding:px;

width:%;

margin:auto;

}

input {

fontsize:px;

fontfamily:Tahoma;

}

</style>

<title>排序</title><h align=center>排序</h><fieldset>

<legend>插入排序</legend><p><b>直接插入排序</b>

请输入一段要排序的字符用半角逗号隔开

<input name=insert type=text size= value=gvufpoiatjelk>

<br><input type=button value= 排序 onclick=alert(InsertSort(insertvaluesplit()));><p><b>希儿排序</b><br> <input name=Shell type=text size= value=gvufpoiatj>

<br><input type=button value= 排序 onclick=alert(ShellSort(Shellvaluesplit()));></fieldset><p><fieldset><legend>交换排序</legend><b>冒泡排序</b><br>

<input name=bubble type=text size= value=gvufpoiatjelk>

<br><input type=button value= 排序 onclick=alert(BubbleSort(bubblevaluesplit()));><p><b>快速排序<br></b> <input name=quick type=text size= value=>

<br><input type=button value= 排序 onclick=alert(QuickSortDemo(quickvaluesplit()));></fieldset><p><fieldset>

<legend>选择排序</legend><b>直接选择排序</b><br>

<input name=select type=text size= value=gvufpoiatjelk>

<br><input type=button value= 排序 onclick=alert(SelectSort(selectvaluesplit()));><p> </fieldset><script>

function InsertSort(arr) { //插入排序>直接插入法排序

var st = new Date();

var temp j;

for(var i=; i<arrlength; i++) {

if((arr[i]) < (arr[i])) {

temp = arr[i];

j = i;

do {

arr[j+] = arr[j];

j;

}

while (j> && (temp) < (arr[j]));

arr[j+] = temp;

}//endif

}

status = (new Date() st) + ms;

return arr;

}

function ShellSort(arr) { //插入排序>希儿排序

var st = new Date();

var increment = arrlength;

do {

increment = (increment/|) + ;

arr = ShellPass(arr increment);

}

while (increment > )

status = (new Date() st) + ms;

return arr;

}

function ShellPass(arr d) { //希儿排序分段执行函数

var temp j;

for(var i=d; i<arrlength; i++) {

if((arr[i]) < (arr[id])) {

temp = arr[i]; j = id;

do {

arr[j+d] = arr[j];

j = jd;

}

while (j> && (temp) < (arr[j]));

arr[j+d] = temp;

}//endif

}

return arr;

}

function BubbleSort(arr) { //交换排序>冒泡排序

var st = new Date();

var temp;

var exchange;

for(var i=; i<arrlength; i++) {

exchange = false;

for(var j=arrlength; j>=i; j) {

if((arr[j+]) < (arr[j])) {

temp = arr[j+];

arr[j+] = 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 (argumentslength>) {

var low = arguments[];

var high = arguments[];

} else {

var low = ;

var high = arrlength;

}

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(arrlowhigh);

QuickSort(arr low pivotpos);

QuickSort(arr pivotpos+ high);

} else

return;

return arr;

}

/*function Partition(arr i j) { //快速排序 对待排序的数组进行划分

var pivot = arr[i];

while(i<j) {

while(arr[j]>=pivot)

j;

if(i<j)

arr[i++] = arr[j];

while(arr[i]<=pivot)

i++;

if(i<j)

arr[j] = arr[i];

}

arr[i] = pivot;

return arr;

}*/

function SelectSort(arr) { //选择排序>直接选择排序

var st = new Date();

var temp;

for(var i=; i<arrlength; i++) {

var k = i;

for(var j=i+; j<arrlength; 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=;

for(var i=; i<strlength; i++){

uni += strcharCodeAt(i)/ * Mathpow( strlengthi);

}

return uni;

}

</script>