JavaScript中的排序算法代码 - 湖南信息网
JavaScript中的排序算法代码
来源：转载
作者：佚名
当变量A赋值给变量B时，会将栈中的值复制一份到为新变量分配的空间中。 如何理解？ 复制代码 代码如下: var x = y = 1; y = 2; alert(x);
x的值为多少？ 复制代码 代码如下: var obj = {}; var sub = {}; sub['id'] = 3; obj['sub'] = sub['id'] = 4; alert(obj['sub']['id
作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 排序分为两类：内排序和外排序。 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。 现在贴3种排序算法的JavaScript实现。 首先是最简单的，是个人都会的冒泡排序。就不多说了，直接贴代码 复制代码 代码如下: /** @name 冒泡排序 * @lastmodify
* @desc 比较排序 复杂度为O(n*n) */ function BubbleSort(list){ var len = list. var cl, while(len--){ cl = list. while(cl--){ if(list[cl]&list[len] && cl & len){ temp = list[len]; list[len] = list[cl]; list[cl] = } } }
然后是最常见的快速排序，面试基本上都会问到。 复制代码 代码如下: /** @name 快速排序 * @lastmodify
* @desc 比较排序 最差运行时间O(n*n); 最好运行时间O(nlogn) */ function QuickSort(list){ var i = 0; var j = list. var len =
var k = findK(i , j); if(k != 0){ var leftArr = []; var rightArr = []; var midArr = [list[k]]; while(len--) { if(len != k){ if(list[len] & list[k]){ rightArr.push(list[len]); } else{ leftArr.push(list[len]); } } } left = QuickSort(leftArr); right = QuickSort(rightArr); list = left.concat(midArr).concat(right); }
} function findK(i,j){ //默认找它的中间位置 return Math.floor((i + j) / 2); }
快速排序的主要思想就是分治法，将被排序的序列分割为2块，从而将排序的复杂度降低。递归的巧用也是快速排序的精妙之处。在上个例子中，首先使用findK函数找出“参照元素”，其他元素依次和该元素进行比较，所有比其大的放入一个集合中，比其小的放入另外一个集合中，再分别对两个集合进行排序。快速排序的效率主要取决于findK函数的实现和待排序元素的有序程度。因此，快速排序是一个不稳定的排序算法。 但是快速排序仍然是一个基于比较的排序算法。所有基于比较的排序算法有一个特点，就是无论怎样优化，它对于一个元素集合的平均排序时间总是随着该集合元素数量的增加而增加。而非比较的排序很好的克服了这个缺点，它们试图让排序时间复杂度趋于一个数量无关的稳定值。其中比较有代表性的就是桶排序了。先看看它的JavaScript实现。 复制代码 代码如下: /** @name 桶排序 * @author lebron * @lastmodify
* @desc 非比较排序 */ function BucketSort(list) { var len = list. var range = findMax(list); var result = [], count = []; var i,j; for (i = 0; i & i++) { count.push(0); } for ( j = 0; j & j++) { count[list[j]]++; result.push(0); } for (i = 1; i & i++) { count[i] = count[i-1] + count[i]; } for (j = len - 1; j &= 0; j--) { result[count[list[j]]] = list[j]; count[list[j]]--; }
} function findMax(list) { return MAX; }
可以看到，在桶排序的实现中，仍然使用了一个findMax函数来确定一个大数组的范围，这里直接用一个常量MAX来代替。首先初始化一个大数组count，长度为MAX。在将被排序集合里面的值放入到对应的位置上去，比如有一个元素值为24，那么count的第24位被标记为1，同时result数组长度+1。再计算出count数组中标志为1的元素位置在整个count数组中标志为1的排位。此时count数组中，第n个元素的值，就应当是排序后它的位置，而n这是这个排序后这个位置对应的值。所以，最后再一一的将count数组里面的键值倒过来映射入结果数组中即可。 桶排序巧妙的利用了这样一种思想，如果一个元素它在一个集合中是第n大的，那么它应该排第n位，而无需关心它前一位或者后一位是比它大还是比它小（无需比较）。很显然的是，在实际情况中，被排序集合的元素的值的范围很可能远远大于这个集合的元素数量，因此，也需要分配相应的一个巨大空间的数组才行。因此，桶排序的常见场景是在外排序上面。 有兴趣的同学，可以测试下3种排序在不同数量级下的耗时。
说明 写这个主要是为了锻炼自己，并无实际意义。 每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快，IE 则根据数组长度有可能希尔最快。 不要用太大数据去测试冒泡排序(浏览器崩溃了我不管) 如果有兴趣可以 下载测试页面 个人理解 冒泡排序：最简单，也最慢，貌似长度小于7最优 插入排序： 比冒泡快，比快速排序和希尔排序慢，较小数据有优势 快速排序：这是一个非常快的排序
栏目ID=44的表不存在(操作类型=1)为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先（新用户需要等待1个小时才能正常使用该功能）。
将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。
插入排序的基本思想:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置p，原来p后的元素一一向右移动一个位置,
使得L[1..i]又是排好序的序列。对于数据比较大的，通常可以采取二分查找来确定一个数应该加入的位置。
例2:输入序列数据按非减顺序输出.
program InsertionS
if l &= r then exit(l);
mid := (l + r) div 2;
if w & a[mid] then find := find(mid+1, r, w)
else find := find(l, mid, w);
assign(input,'num.in');
reset(input);
assign(output,'num.out');
rewrite(output);
readln(n);
a[1] :=
for i := 1 to n do
read(x);
p := find(1, i, x);
for j := i downto p do a[j+1] := a[j];
a[p] :=
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
write('Enter date:');
for i:= 1 to n do read(a[i]);
for i:=2 to n do
k:=a[i];j:=i-1;
while (k&a[j]) and (j&0) do
begin a[j+1]:=a[j];j:=j-1 end;
a[j+1]:=k;
write('output data:');
for i:= 1 to n do write(a[i]:6);
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
例1:输入序列数据按非减顺序输出.
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
write('Enter data:');
for i:= 1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[j]&a[k] then k:=j;
if k&&i then
begin t:=a[i];a[i]:=a[k];a[k]:=t;end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
const max=100;
type arr=array[0..max]of integer;
i,n:integer;
procedure BinSort(var r: rn:integer);
var i,j,low,high,mid:integer;
for i:=2 to rn do
r[0]:=r[i];
{ 将待插入记录存放到监视哨r[0]里 }
high:=i-1; { 确定查找的上下界 }
while(low&=high) do
{ 寻找插入位置 }
mid:=(low+high)div 2;
{ 记录后移 }
if r[0]&r[mid] then high:=mid-1
{ 左半边查找 }
else low:=mid+1;
{ 右半边查找 }
for j:=i-1 downto low do r[j+1]:=r[j];
{ 记录依次向后移动 }
r[low]:=r[0];
{ 将待插入记录插入到已排序的序列中 }
assign(fin,'input.txt');
reset(fin);
readln(fin,n);
for i:=1 to n do read(fin,a[i]);
write('before sort:');
for i:=1 to n do write(a[i]:5); writeln;
BinSort(a,n);
write('after sort: ');
for i:=1 to n do write(a[i]:5); writeln;
close(fin);
const max=100;
type arr=array[0..max]of integer;
i,n:integer;
procedure InsSort(var r: rn:integer); { 直接插入排序算法 }
var i,j:integer;
for i:=2 to rn do
r[0]:=r[i];
{ 将待插入记录存放到监视哨r[0]里 }
while(r[0]&r[j]) do
{ 寻找插入位置 }
r[j+1]:=r[j];
{ 记录后移 }
dec(j);
r[j+1]:=r[0];
{ 将待插入记录插入到已排序的序列中 }
assign(fin,'input.txt');
reset(fin);
readln(fin,n);
for i:=1 to n do read(fin,a[i]);
write('before sort:');
for i:=1 to n do write(a[i]:5); writeln;
InsSort(a,n);
write('after sort: ');
for i:=1 to n do write(a[i]:5); writeln;
close(fin);
基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2&d1重复上述的分组和排序，直至所取的增量dt=1(dt&dt-l&…&d2&d1)，即所有记录放在同一组中进行直接插入排序为止。
const n=7;
var a:array[1..n]of longint;
i,j,d,x:longint;
write('Enter data:');
for i:=1 to n do read(a[i]);
d:=n div 2;
while d&=1 do
for i:=d+1 to n do
x:=a[i];
while (j&0)and(x&a[j]) do
a[j+d]:=a[j];
a[j+d]:=x;
d:=d div 2;
write('output data:');
for i:=1 to n do write(a[i],' ');
冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个
记录是反序的,则进行交换,直到无反序的记录为止。
例:输入序列数据按非减顺序输出。
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
write('Enter date:');
for i:= 1 to n do read(a[i]);
for i:=1 to n -1 do
for j:=n downto i+1 do
if a[j-1]&a[j] then
begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
bool:boolean;
write('Enter date:');
for i:= 1 to n do read(a[i]);
i:=1;bool:=true;
while (i&n) and bool do
bool:=false;
for j:=n downto i+1 do
if a[j-1]&a[j] then
begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
write('Enter date:');
for i:= 1 to n do read(a[i]);
while k&0 do
j:=k-1;k:=0;
for i:=1 to j do
if a[i]&a[i+1] then
begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
var a:array[1..100000] of integer;
n,i,i,p:integer;
procedure swap(var x,y:integer);
var t:integer;
begin{main};
readln(n);
for p:=1 to n do
read(a[p]);
for i:=1 to n-1 do
for j:=i to n do
if a[i]&a[j] then swap(a[i],a[j]);
for p:=1 to n do
writeln(a[p]);
var a:array[1..maxint] of integer;
n,i:integer;
procedure sort(b:array of integer);
var i,bottom,top,t:integer;
f:boolean;
bottom:=1;
while(f=true) do
for i:=bottom to top-1
if a[i]&a[i+1] then begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;f:=true;end;
top:=top-1;
for i:=top downto bottom+1 do
if a[i]&a[i-1] then begin t:=a[i];a[i]:=a[i-1];a[i-1]:=t;f:=true end;
bottom:=bottom+1;
readln(n);
for i:=1 to n do
read(a[i]);
sort(a);
for i:=1 to n do
write(a[i],' ');
const n=7;
arr=array[1..n] of integer;
i:integer;
procedure quicksort(var b: s,t:integer);
var i,j,x,t1:integer;
i:=s;j:=t;x:=b[i];
while (b[j]&=x) and (j&i) do j:=j-1;
if j&i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]&=x) and (i&j) do i:=i+1;
if i&j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s&j then quicksort(b,s,j);
if i&t then quicksort(b,i,t);
write('input data:');
for i:=1 to n do read(a[i]);
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
const n=7;
arr=array[1..n] of integer;
i:integer;
procedure quicksort(var b: s,t:integer);
var i,j,x:integer;
i:=s;j:=t;x:=b[i];
while (b[j]&=x) and (j&i) do j:=j-1;
if j&i then begin b[i]:=b[j];i:=i+1;end;
while (b[i]&=x) and (i&j) do i:=i+1;
if i&j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s&j then quicksort(b,s,j);
if i&t then quicksort(b,i,t);
write('input data:');
for i:=1 to n do read(a[i]);
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
（言过其实了，C++ STL的Sort实现用的是Introsort，是快速排序的变种，主要是递归过深的时候自动转换为堆排或插入排序（是堆排还是插入排序还要视具体实现而定），可以保证最坏情况下还是O(nlogn)，并且充分使用了尾递归优化（快排最后不是两个递归吗？最后一个递归可以不必真的递归，可以像gcd算法一样通过迭代参数来改善运行速度），STL快排可以经受任何实践的考验，而这段代码在最坏情况下还是O(n^2)) -- by 某奋战的OIer
&template T&
void sort(T a[],T st,T ed)
{ if(st&ed)
//先设一个开关优化，会更快一些
{ T tmp=a[st],i=st,j=ed;
while(i&j)
{ while(a[j]&tmp&&i&j) --j;
//C++在判断时，会打开编译开关，把a[j]与tmp放在前比较，这样会更快一些~~
if(i&j) a[i++]=a[j]; //ps:j-- ,i++(下行）比不了--j,++i快
while(a[i]&tmp&&i&j) ++i;//注意：这里用的不是&&=&或&&=&而是&&&&&，事实证明，前者会增加交换的次数，做无用功~~~
if(i&j) a[j--]=a[i];
a[i]=tmp;
sort(a,st,i-1);
sort(a,i+1,ed);
//这里不用return语句，会快一些
//由于以上的种种，程序在大的排序中（N&=10e6)优势越来越大--By LinuxKernel
[''惭愧惭愧，当时我没拿出BT级别的数据,听你这么一说后试了一下，挂了14:31 2011年6月12日 (LinuxKernel)'']
procedure qsort(l,r:longint);
mid:=d[(l+r) div 2];
while d[i]&mid do
//小的在前
inc(i);
while d[j]&mid do
dec(j);
if i&=j then
swap(d[i],d[j]);
inc(i);
dec(j);
until i&j;
if i&r then qsort(i,r);
if l&j then qsort(l,j);
这有一段C++代码，并且用了模版
其中，cmp是比较函数，和stl中qosrt中最后那个参数类似。
template&typename T&
int cmp(const void *e1, const void *e2) {
if (*((T*)e1) & *((T*)e2))
else if (*((T*)e1) & *((T*)e2))
return -1;
else return 0;
template&typename T&
int partition(T a[], int l, int r, int(*cmp)(const void*, const void*)) {
int i = l, j = r-1;
while (true) {
while (i &= j && cmp(a+i, a+r) != 1)
while (i &= j && cmp(a+j, a+r) == 1)
if (i & j)
swap(a[i], a[j]);
swap(a[r], a[i]) ;
template&typename T&
void qSort(T a[], int l, int r, int(*cmp)(const void*, const void*)) {
if (l & r) {
int q = partition(a, l, r, cmp);
qSort(a, l, q-1, cmp);
qSort(a, q+1, r, cmp);
Procedure Qst(i,j:integer);
Var ii,jj,xx:integer;
ii:=i;jj:=j;xx:=a[ii];
while (ii&jj) and (a[jj]&=xx) do dec(jj);a[ii]:=a[jj];//先又指针因为xx已经把a[i]保存了，就可以覆盖了
while (ii&jj) and (a[ii]&=xx) do inc(ii);a[jj]:=a[ii];
a[ii]:=//这句太重要了我刚学的时候因为少了这句郁闷了一星期
if i&ii-1 then qst(i,ii-1);
if ii+1&j then qst(ii+1,j);
类似C库函数的Pascal快排，可以排序任意数组
FCompair=Function (const cmpx,cmpy:pointer):boolean;
PInt32=^LongI
procedure qsort(varcount,dsize:great:FCompair);
tmp,cmp:pointer;
procedure qsortin(l,r:pointer);
i,j:pointer;
i:=l;j:=r;move(l^,cmp^,dsize);
while i&=j do
while great(j,cmp) do dec(j,dsize);
while great(cmp,i) do inc(i,dsize);
if i&=j then
move(i^,tmp^,dsize);move(j^,i^,dsize);move(tmp^,j^,dsize);
inc(i,dsize);dec(j,dsize);
if l&j then qsortin(l,j);
if i&r then qsortin(i,r);
getmem(tmp,dsize);
getmem(cmp,dsize);
qsortin(@first,@first+(count-1)*dsize);
freemem(tmp,dsize);
freemem(cmp,dsize);
function Int32cmp(const cmpx,cmpy:pointer):boolean;
exit(PInt32(cmpx)^&PInt32(cmpy)^);
a:array [1..15] of longint;
i:longint;
for i:=1 to 15 do
a[i]:=random(200);
qsort(a[1],15,sizeof(longint),@Int32cmp);//一定要有@
for i:=1 to 15 do
write(a[i],' ');
writeln(a[15]);
堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有
Ri&=R2i 和Ri&=R2i+1(或&=)
堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。
堆排序的思想是：
1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）
2）当未排序完时
输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。
程序如下：
const max=100;
type arrtype=array[1..max] of integer;
i,n,temp:integer;
procedure heap(var r:nn,ii:integer);
var x,i,j:integer;
x:=r[ii];
while j&=nn do
if (j&nn) and (r[j]&r[j+1]) then j:=j+1;
if x&r[j] then
r[i]:=r[j];i:=j;j:=2*i
else j:=nn+1;
r[i]:=x;
readln(n);
for i:=1 to n do
read(a[i]);
for i:=n div 2 downto 1 do
heap(a,n,i);
for i:=n downto 2 do
temp:=a[1];
a[1]:=a[i];
a[i]:=
heap(a,i-1,1);
for i:=1 to n do
write(a[i]:4);
writeln;readln;
这是一段C++程序：
其中，heap_size和length作为了全局变量，也可以作为参数传到函数中。
// heapsort
int heap_size ;
int length ;
inline int PARENT(int i) { return (i+1)/2-1 ; }
inline int LEFT(int i) { return 2*(i+1)-1 ; }
inline int RIGHT(int i) { return 2*(i+1) ; }
void build_max_heap(double *a)
heap_size = length ;
for (i = length/2-1; i&=0; --i)
max_heapify(a, i) ;
void max_heapify(double *a, int i)
int l = LEFT(i) ;
int r = RIGHT(i) ;
int largest ;
if ((l&heap_size)&&(a[l]&a[i]))
largest = l ;
largest = i ;
if ((r&heap_size)&&(a[r]&a[largest]))
largest = r ;
if (i != largest)
swap(a[i], a[largest]) ;
max_heapify(a, largest) ;
void heapsort(double *a)
build_max_heap(a) ;
for (i = length-1; i&0; --i)
swap(a[0], a[i]) ;
--heap_size ;
max_heapify(a, 0) ;
归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n个长度为1的子序列,两两归并最后变为有序的序列。
1.二路归并
例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L.
const m=3;n=7;
type arrl1=array[1..m] of integer;
arrl2=array[1..n] of integer;
arrl=array[1..m+n] of integer;
var a:arrl1;
i,j,k,r:integer;
write('Enter l1(sorted):');
for i:=1 to m do read(a[i]);
write('Enter l2(sorted):');
for i:=1 to n do read(b[i]);
i:=1;j:=1;k:=0;
while (i&=m) and (j&=n) do
if a[i]&=b[j] then begin c[k]:=a[i];i:=i+1; end
else begin c[k]:=b[j];j:=j+1;end;
if i&=m then for r:=i to m do c[n+r]:=a[r];
if j&=n then
for r:=j to n do c[m+r]:=b[r];
writeln('Output data:');
for i:=1 to m+n do write(c[i]:5);
2.归并排序
通常采取直接的区间操作（原版是用另外的一个数组来存储二分的数据，这样的话，数组开不了1000以上）
program MergeS
arr1 = array[1..10000] of longint;
n, i : longint;
a, ans, temp: arr1;
procedure merge(l, mid, r : longint; var c : arr1);
i, j, k, p: longint;
j := mid + 1;
k := l - 1;
while (i &= mid) and (j &= r) do
inc(k);
if temp[i] & temp[j] then
c[k] := temp[i];
inc(i);
c[k] := temp[j];
inc(j);
if i &= mid then
for p := i to mid do
inc(k);
c[k] := temp[p];
if j &= r then
for p := j to r do
inc(k);
c[k] := temp[p];
procedure mergesort(var b: arr1; l, r : longint);
mid : longint;
if l = r then
b[l] := a[l];
mid := (l + r) div 2;
mergesort(b, l, mid);
mergesort(b, mid+1, r);
merge(l, mid, r, b);
readln(n);
for i := 1 to n do read(a[i]);
mergesort(ans, 1, n);
for i := 1 to n do writeln(ans[i]);
3、推广：统计逆序对个数
只需将归并排序程序中加一句即可
if temp[i]&temp[j] then
c[k]:=temp[i];
inc(i);
c[k]:=temp[j];
inc(j);
inc(t,mid-i+1);
//这里加一句，最后输出t，即为逆序对的个数
基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。
例：n个整数序列且每个值在[1,m],排序之。
const m=6;n=8;
var i,j:integer;
a,b:array[1..n] of integer;
c:array[1..m] of integer;
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=1 to m do c[i]:=0;
for i:=1 to n do c[a[i]]:=c[a[i]]+1;
for i:=2 to m do c[i]:=c[i]+c[i-1];
for i:=n downto 1 do
b[c[a[i]]]:=a[i];
c[a[i]]:=c[a[i]]-1;
writeln('Sorted data:');
for i:= 1 to n do
write(b[i]:6);
桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。
例：输入n个0到100之间的整数，由小到大排序输出。
program Bin_
const n=7;
var b:array[0..100] of integer;
i:integer;
write('Enter date:(0-100)');
for i:=0 to 100 do b[i]:=0;
for i:= 1 to n do
read(k);
b[k]:=b[k]+1;
writeln('Output data:');
for i:=0 to 100 do
while b[i]&0 do begin write(i:6);b[i]:=b[i]-1 end;
基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。
const n=8;
type link=^
node=record
data:integer;
var i,j,l,m,k:integer;
a:array[1..n] of integer;
q,head:array[0..9] of
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
for j:=0 to 9 do
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
for j:=1 to n do
str(a[j],s);
for k:=1 to 5-length(s) do
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
for j:=0 to 9 do
p:=head[j];
while p^.next&&nil do
l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;
writeln('Sorted data:');
for i:= 1 to n do
write(a[i]:6);
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序、快速排序、堆排序是不稳定的。
不过通过使用“第二关键字”的技术，可将不稳定的排序算法转化为稳定的。
插入排序、冒泡排序最优为O(n),最坏为O(n^2),平均O(n^2）；
快速排序最优为O(nlogn),最坏为O(n^2),平均O(nlogn);
堆排序最优为O(nlogn),最坏为O(nlogn),平均O(nlogn);
线形排序的时间复杂性为O(n)。
线形排序、归并排序的辅助空间为O(n),快速排序的辅助空间为O(logn),其它排序的辅助空间为O(1)。
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时,且空间允许时用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
此页面已被浏览过77,779次。
本页面由NOCOW用户于日 (星期五) 16:07做出最后修改。 在NOCOW匿名用户、、和和的工作基础上。