词语大全 > 排序

排序

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

快速排序希尔排序堆排序直接选择排序不是稳定的排序算法,而基数排序冒泡排序直接插入排序、折半插入排序、归并排序是稳定的排序算法

◆稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在

用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法

是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,堆属于不稳定排序。

◆就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),

则称为就地排序。

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似,若a[1]小于a[2]则交换两者的值,否则不变,后面以此类推。 总的来讲,每一轮排序后最大(或最小)的数将移动到数据序列的最后,理论上总共要进行n(n-1)/2次交换。

优点:稳定;

缺点:慢,每次只能移动相邻两个数据。

附Pascal程序:

program name;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln('Array before sorted:');

for i:=1 to N do write(a,' ');

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]<a[j+1] then

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp

end;

writeln('Array sorted:');

for i:=1 to N do write(a,' ');

writeln;

writeln('End sorted.');

readln;

end.

附c/c++ma程序(共有N个数)

附 c# 程序(指定个数)

static void Main(string[] args)

{

int[] arr = { 4, 2, 5, 7, 4, 9, 6, 21 };

for (int i = 0; i < arr.Length; i++)

{

for (int j = i + 1; j < arr.Length; j++)

{

int temp = 0;

if (arr[i] > arr[j])

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

}

foreach (int num in arr)

{

Console.Write(" {0}", num);

}

Console.ReadKey();

}

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法(很多教科书都说选择排序是不稳定的,但是,完全可以将其实现成稳定的排序方法)。

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(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

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

优点:移动数据的次数已知(n-1次);

缺点:比较次数多,不稳定。

插入排序:已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b[m],需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)

优点:稳定,快;

缺点:比较次数不一定,比较次数越多,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择

希尔在1959年提出,又称希尔排序(shell排序)。

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。首先取一增量d(d<n),将a[1]、a[1+d]、a[1+2d]……列为第一组,a[2]、a[2+d]、a[2+2d]……列为第二组……,a[d]、a[2d]、a[3d]……列为最后一组以次类推,在各组内用插入排序,然后取d'<d,重复上述操作,直到d=1。

program Shell;

type

arr=array[1..100] of integer;

var

a:arr;

i,j,t,d,n:integer;

bool:boolean;

begin

readln(n);

for i:=1 to n do

read(a[i]);

d:=n;

while d>1 do

begin

d:=d div 2;

for j:=d+1 to n do

begin

t:=a[j];

i:=j-d;

while (i>0) and (a[i]>t) do

begin

a[i+d]:=a[i];

i:=i-d;

end;

a[i+d]:=t;

end;

end;

for i:=1 to n do write(a[i],' ');

end.

优点:快,数据移动少;

缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。

不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法, 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是 最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快, 再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

快速排序是目前已知的常用排序算法中最快的排序方法。

已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数据>a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序

优点:极快,数据移动少;

缺点:不稳定。

program kuaipai;

var

a:array[1..100]of integer;

k,l,n,i:integer;

procedure kp(z,y:integer);

var

i,j,t:integer;

begin

i:=z;

j:=y;

t:=a[i];

repeat

while (a[j]>t)and(j>i) do

begin

inc(k);

dec(j);

end;

if i<j then

begin

a[i]:=a[j];

inc(i);

inc(l);

while (a[i]<t)and(i<j) do

begin

inc(k);

inc(i);

end;

if i<j then begin

a[j]:=a[i];

dec(j);

inc(l);

end;

end;

until i=j;

a[i]:=t;

inc(i);

dec(j);

inc(l);

if z<j then kp(z,j);

if i<y then kp(i,y);

end;

begin

readln(n);

for i:=1 to n do

read(a[i]);

k:=0;

l:=0;

kp(1,n);

for i:=1 to n do

write(a[i],' ');

end.

//化分区间,找到最后元素的排序位置。并返回分隔的点(即最后一数据排序的位置)。

//划分的区间是[nBegin, nEnd). pData是保存数据的指针

static int Partition(int[] pData, int nBeging, int nEnd)

{

int i = nBeging - 1; //分隔符号,最后nD保存在这里

--nEnd;

int nD = pData[nEnd]; //比较的数据。

int nTemp; // 交换用的临时数据

//遍历数据比较,找到nD的位置,这里注意,比较结果是,

//如果i的左边是小于等于nD的,i的右边是大于nD的

for (int j = nBeging; j < nEnd; ++j)

{

if (pData[j] <= nD) //如果数据比要比较的小,则在该数据的左边,与i+1交换

{

++i; //小于nD的数据多一个,所以要加1,i的左边数据都比nD小

nTemp = pData[i]; //交换数据

pData[i] = pData[j];

pData[j] = nTemp;

}

}

//最后不要忘了吧nD和i+1交换,因为这里就是nD的位置咯。

++i;

pData[nEnd] = pData[i];

pData[i] = nD;

return i; //返回nD的位置,就是分割的位置。

}

//排序的递归调用。

static int QuickSortRecursion(int[] pData, int nBeging, int nEnd)

{

if (nBeging >= nEnd -1) //如果区域不存在或只有一个数据则不递归排序

{

return 1;

}

//这里因为分割的时候,分割点处的数据就是排序中他的位置。

//也就是说他的左边的数据都小于等于他,他右边的数据都大于他。

//所以他不在递归调用的数据中。

int i = Partition(pData, nBeging, nEnd); //找到分割点

QuickSortRecursion(pData, nBeging, i); //递归左边的排序

QuickSortRecursion(pData, i + 1, nEnd); //递归右边的排序

return 1;

}

//快速排序

public static int QuickSort(int[] pData, int nLen)

{

//递归调用,快速排序。

QuickSortRecursion(pData, 0, nLen);

return 1;

}

已知一组无序正整数数据a[1]、a[2]、……a[n],需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n],接着循环n次,每次x[a]++.

优点:快,效率达到O(1)

缺点:数据范围必须为正整数并且比较小

箱排序(Bin Sort)

1、箱排序的基本思想

箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序,需设置13个"箱子",排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌。

2、箱排序中,箱子的个数取决于关键字的取值范围。

若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

(1) 实现方法一

每个箱子设为一个链队列。当一记录装入某箱子时,应做人队操作将其插入该箱子尾部;而收集过程则是对箱子做出队操作,依次将出队的记录放到输出序列中。

(2) 实现方法二

若输入的待排序记录是以链表形式给出时,出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域,令其指向箱子链表的头,然后修改输出链表的尾指针,令其指向箱子链表的尾即可。

5、算法简析

分配过程的时间是O(n);收集过程的时间为O(m) (采用链表来存储输入的待排序记录)或O(m+n)。因此,箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n)。

注意:

箱排序实用价值不大,仅适用于作为基数排序的一个中间步骤。

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

program guibing;

type

arr=array[1..100] of integer;

var

a,b,c:arr;

i:integer;

procedure gb(r:arr;l,m,n:integer;var r2:arr);

var

i,j,k,p:integer;

begin

i:=l;

j:=m+1;

k:=l-1;

while (i<=m)and (j<=n) do

begin

k:=k+1;

if r[i]<=r[j] then

begin

r2[k]:=r[i];

i:=i+1

end

else

begin

r2[k]:=r[j];

j:=j+1

end

end;

if i<=m then

for p:=i to m do

begin

k:=k+1;

r2[k]:=r[p]

end;

if j<=n then

for p:=j to n do

begin

k:=k+1;

r2[k]:=r[p]

end;

end;

procedure gp( var r,r1:arr;s,t:integer);

var

k:integer;

c:arr;

begin

if s=t then r1[s]:=r[s]

else

begin

k:=(s+t) div 2;

gp(r,c,s,k);

gp(r,c,k+1,t);

gb(c,s,k,t,r1)

end;

end;

begin

readln(n);

for i:= 1 to n do

read(a[i]);

gp(a,b,1,n);

for i:=1 to n do

write(b[i],' ');

writeln;

end.

树形排序的要素就是让所有的左子树都比根及右子树大,但不太稳定。

优点:效率高

缺点:不稳定

program shupai;

type

point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var

a:array[1..100]of integer;

root,first:point;

k:boolean;

i:integer;

procedure hyt(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin

w:=d;

right:=nil;

left:=nil

end;

if k then

begin

root:=p;

k:=false

end;

end

else

with p^ do

if d>=w then

hyt(d,right)

else

hyt(d,left);

end;

procedure hyt1(p:point);

begin

with p^ do

begin

if left<>nil then

hyt1(left);

write(w,' ');

if right<>nil then hyt1(right);

end;

end;

begin

first:=nil;

k:=true;

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

hyt(a[i],first);

hyt1(root);

end.

1.对无序数组进行二分查找

2.对单链表进行排序

3.对40亿个8位正整数进行排序

相关解释:

词语大全 8944.net

copyright ©right 2010-2021。
词语大全内容来自网络,如有侵犯请联系客服。zhit325@126.com