排序算法(梦幻媒体共享）【郭晓非吧】

1、选择排序
选择排序
1.基本的选择排序
  <1>基本思想

        首先从要排序的数中选择最大的数,将它放在第一个位置,然后从剩下的数中选择最大的数放在第二个位置,如此继续,直到最后从剩下的两个数中选择最大的数放在倒数第二个位置,剩下的一个数放在最后位置,完成排序.

        下表是六个元素的排序的过程

　


      4    5   7   1   2   3

         ┗━━┛

          5    4   7   1   2   3
     ┗━━━━┛

          7    4   5   1   2   3
     ┗━━━━━━┛

          7    4   5   1   2   3

         ┗━━━━━━━━━━┛    第一趟结束
      ⑦   4   5   1   2   3

              ┗━┛
      7    5   4   1   2   3

              ┗━━━┛
      7    5   4   1   2   3
          ┗━━━━━┛
      7    5   4   1   2   3
          ┗━━━━━━━┛     第二趟结束
      7    ⑤  4   1   2   3
              ┗━┛

          7    5   4   1   2   3
              ┗━━━┛

          7    5   4   1   2   3

                   ┗━━━━━┛    第三趟结束

          7    5   ④  1   2   3

                      ┗━┛
      7    5   4   2   1   3     第四趟结束
                  ┗━━━┛
      7    5   4   ③  1   2
                      ┗━┛     第五趟结束

          7    5   4   3   ②  ①


  <2>算法实现

           for i:=1 to 9 do

             for j:=i+1 to 10 do

               if a[i]<a[j]
            begin

                  temp:=a[i];

                  a[i]:=a[j];

                  a[j]:=temp;

                end;

    2.改进

         以上排序方案每次交换两个元素需要执行三个语句,过多的交换必定要花费许多时间.改进方案是在内循环的比较中找出最大值元素的下标,在内循环结束时才考虑是否要调换.

         代码如下

              for i:=1 to 9 do

                begin

                 k:=i;

                 for j:=i+1 to 20 do

                    if a[j]>a[k]

                      then k:=j;

                 if i<k {不可能大于}

                   then begin

                           temp:=a[i];

                           a[i]:=a[k];

                           a[k]:=temp;

                        end;

                end;
_____________________________
{Xuan3Ze2Pai2Xu4}
var a:array [1..10]of integer;i,j,k,temp:integer;{Pai2Xu4'>'}
begin
for i:=1 to 10 do readln (a[i]);
for i:=1 to 9 do
begin
  k:=i;
  for j:=i+1 to 10 do
     if a[j]>a[k] then k:=j;
     if i<k then begin
                 temp:=a[i];
                 a[i]:=a[k];
                 a[k]:=temp;
             end;
end;
for i:=1 to 10 do writeln (a[i]);
end.

送TA礼物

IP属地:广西

1楼2004-11-16 16:15回复

冒泡排序
1.基本的冒泡排序
<1> 基本思想

依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后......
由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.

下面是6个元素的排序的过程

　

　

4 5 7 1 2 3

┗━━┛
5 4 7 1 2 3
┗━━┛
5 7 4 1 2 3
┗━━┛
5 7 4 1 2 3

┗━━┛
5 7 4 2 1 3

┗━━┛ 第一趟结束

5 7 4 2 3 ①
┗━━┛

7 5 4 2 3 1
┗━━┛

7 5 4 2 3 1
┗━━┛
7 5 4 2 3 1

┗━━┛ 第二趟结束
7 5 4 3 ② 1

┗━━┛
7 5 4 3 2 1
┗━━┛

7 5 4 3 2 1
┗━━┛ 第三趟结束

7 5 4 ③ 2 1
┗━━┛
7 5 4 3 2 1
┗━━┛ 第四趟结束

7 5 ④ 3 2 1
┗━━┛ 第五趟结束

⑦ ⑤ 4 3 2 1

<2> 算法实现

for i:=1 to 9 do

for j:=1 to 10-i do

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

then begin

temp:=a[j];

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

a[j+1]:=temp;

end;

2 改进

　　　上例中,可以发现,第二趟结束已经排好序.但是计算机此时并不知道已经排好序.所以,还需进行一次比较,如果没有发生任何数据交换,则知道已经排好序,可以不干了.因此第三趟比较还需进行,第四趟、第五趟比较则不必要.

我们设置一个布尔变量bo 来记录是否有进行交换.值为false 进行了比较　true 则没有

代码如下

i:=1;
　　 repeat

bo:=true;

for j:=1 to 10-i

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

begin

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

a[j+1]:=temp;

bo:=false;

end;

　　　　　　inc(i);

until bo;
　　
3.再次改进
　如果说是有20个元素．数据序列是8,3,4,9,7再后跟着１５个大于９且已经排好序的数据．在第三趟后算法终止．总共做了19+18+17=54次比较使得绝大多数已排好序的数据在一遍扫描后足以发现他们是排好序的情况下仍然被检查３遍．

　　　　我们改进如下
　　　flag:=10;

while flag>0 do

begin
k:=flag-1;
flag:=0;

for i:=1 to k do

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

begin

temp:=a[i];

a[i]:=a[i+1];
a[i+1]:=temp;

flag:=i;

end;

end;　

　改进的冒泡算法对上述数据进行的比较次数是19+4+2=24.

_____________________________________________________________
{Mao4Pao4Pai2Xu4}
var a:array [1..10] of integer;
flag,temp,k,i:integer;
begin
for i:=1 to 10 do readln (a[i]);
flag:=10;
while flag>0 do
begin
k:=flag-1;
flag:=0;
for i:=1 to k do
if a[i]<a[i+1] then
begin
temp:=a[i];
a[i]:=a[i+1];
a[i+1]:=temp;
flag:=i;
end;
end;
for i:=1 to 10 do writeln (a[i]);
end.

IP属地:广西

2楼2004-11-16 16:16

希尔排序
<1> 基本思想

希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组; 然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.
可参阅<<计算机程序设计技巧??第三卷排序查找

<2> 算法实现

j:=10;

i:=1;

while j>1 do

begin

j:=j div 2;

repeat

alldone:=true;

for index:=1 to 10-j do

begin

i:=index+j;

if a[index]<a[i] then

begin

temp:=a[index];

a[index]:=a[i];

a[i]:=temp;

alldone:=false;

end;

end;

until alldone

end;

//说句实话,这个很少有人用.:( 当然我也不会,书上抄的
//分区复赛奥赛用前两种基本已经够用了

IP属地:广西

3楼2004-11-16 16:17

插入排序

<1> 基本思想

//对不起,我没书.所以是我自己讲.我很菜．不要介意
插入排序的思想就是读一个，排一个．　　//也许是这样,起码我是这么认为的：）

　　　　　将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．
<2> 算法实现　　｛加了读入语句｝

procedure insert(x,num:integer);

var

i,pos:integer;

search:boolean;

begin

pos:=1;

search:=true;

while search and (pos<=num ) do

if x>a[pos]

then search:=fasle

else inc(pos);

for i:=num downto pos do

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

a[pos]:=x;

num:=num+1;

end;

num:=0 {当前数组的长度｝

for i:=1 to 10 do

begin

read(x);

intert(x,num) 　　　　　　　

end;

IP属地:广西

4楼2004-11-16 16:18

合并排序

<1> 基本思想

合并排序的算法就是二分法。
分解：将n个元素分解成各含一半元素的子序列。
解决：用合并排序法对两个子序列递归地排序。
合并：合并两个已排序的子序列排序结果。
在对子序列排列时，当其长度为1时递归结束，因为单个元素被认为是已排好序的.合并排序的.合并排序的关键步骤在于合并目前产生的两个已排好序的子序列:
A[p..q] 和 A[q+1…r];
将它们合并成一个已排好序的子序列A[p..r]. 我们引入一个辅助过程merge(A,p,q,r)来完成这一项合并工作,其中A是数组,p,q,r是下标.

<2> 算法实现

procedure merge( p,q,r:integer);
var
i,j,t:integer;
it:array[1..10] of integer;
begin
t:=p; i:=p; j:=q+1;
while t<=r do
begin
if (i<=q) and ((j>j) or (a[i]<=a[j]))
then begin
it[t]:=a[i]; inc(i);
end
else begin
it[t]:=a[j]; inc(j);
end;
inc(t);
end;
for i:=p to r do a[i]:=t[i];
end;
procedure merge_sort(p,r:integer);
var q:integer;
begin
if p<>r then begin
q:=(p+r-1) div 2 ;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
end;
end;
begin
merge_sort(1,10);
end.

IP属地:广西

5楼2004-11-16 16:18

不错的，什么时候写的？忘记…�

IP属地:广西

7楼2006-06-26 15:00

日	一	二	三	四	五	六

排序算法(梦幻媒体共享）

登录百度账号

扫二维码下载贴吧客户端