02年06月01日排序分类

分类（排序）—外部排序二内部排序1.选择排序2.冒泡排序3.快速排序选择排序基本思想：首先从要排序的数中选择最大的数，将它放在第一个位置，然后从剩下的数中选择最大的数放在第二个位置，如此继续，直到最后从剩下的两个数中选择最大的数放在倒数第二个位置，剩下的一个数放在最后位置，完成排序。例：把下列数从大到小排序：4

5

7

1

23I

=1745123I

=2754123I

=3754123I

=4754312I

=5754321输入A(N)各值I 1

TO

N-1J I+1

TO

NA[I]<A[J]YN交换A[I]与A[J]的值输出排序后的结果流程图:K

IJ I+1

TO

NA[K]<A[J]NI<>JYNK

JY交换A[K]与A[J]的值输出排序后的结果优化后的选择排序算法:输入A[N]各值I 1

TO

N-1冒泡排序基本思想：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个数和第2个数，将大数放前，小数放后，然后比较第2个数和第3个数，大数放前，小数放后，如此继续，直到比较最后两数，大数放前，小数放后，至此第一趟结束，此时在最后一个位置上放的必是所有数中最小的数。重复以上过程，从第一个数开始，直比到最小数前的一对相邻数，至此次小数被放在了倒数第二个位置上，如此继续，直到最后一趟。例：把下列数从大到小排序：第一趟结束457123547123574123574123574213574231754231754231754231754321输入数组各值I

1

TO

N-1J

1

TO

N-IA[J]<A[J+1]YN交换A[J]和A[J+1]输出排序结果流程图:A[j]<A[j+1]yn交换A[j]和A[j+1]Flag

falsei

i+1Flag=true输出排序结果优化后的冒泡排序算法:输入数组各值

;

i

1;Flag

trueJ 1

to

n-i快速排序基本思想:从欲排序的数列中取一合适的数K,以K为标准把要排序的N个数分成两部分,一部分是比K小的,一部分是比K大的,即把数列分成:(小于K部分)K(大于K部分),然后对这两部分分别按此方法继续进行分组,直到被分成的每一部分都只含有一个数据为止.算法:将参加排序的数据放入一个数组A中,假定为A1,A2,…,An;将数组A重新组织成A’,A1,A”.其中A’是所有小于A1的数据的集合,A”是所有不小于

A1的数据的集合.对A’,A”重复步骤2,直到每个集合都只有一个数据,排序完毕.例：对下列数按从小到大排序3

9

1

6

5

4

8

2

10

72)指针j向左移动,直到碰到比3小的数为止,本例为23

9

1

6

5

4

8

2

10

7ij2与3互换得2

9

1

6

5

4

8

3

10

7ji1)引进指针i和j分别指向数列的开始和终止,并利用最左端的数据作为k3

9

1

6

5

4

8

2

10

7ijK=33)指针i向右移动,直到遇到比3大的数据为止.本例为9.2

9

1

6

5

4

8

3

10

7i

j9与3互换得2

3

1

6

5

4

8

9

10

74)对指针i和指针j间的序列继续以上(1)-(3)步骤直到指针重合为止,第一轮结束.把序列分成比3小的和比3大的两部分:231654891072i1j365489107ij6

5

4

8

9

10

7K=6i

j6

5

4

8

9

10

7j从往左找比6小的i

j4

5

6

8

9

10

74,6互换i右移,找6大的i

j4

5

6

8

9

10

7i

j4

5

6

8

9

10

7ij直到i,j重合这一轮结束开始7小于8,j不动

7,8互换i向右移,找比8大的8,9互换j向左移,找比8小的8

9

10

7i

j7

9

10

8i

j7

9

10

8i

j7

8

10

9i

j7

8

10

9ij直到i,j重合,此轮结束8

9

10

7ji7

9

10ji7

9

10i7i7j10

9j10

9ij7

8

10

9ij算法:(过程qk_sort(I,j)){I为1，J为n}a[i];left

i,

right j;

k重复只要I<j且a[j]>=k,循环j j-1;如果I<j,

则a[i]

a[j];只要I<j且a[I]<k,循环I

I+1;如果I<j,则a[j]

a[i];直到I=j;A[i]

k如果两部分数列长度均不为1,则重复

qk_sort(left,I-1);qk_sort(j+1,rLeft I;

right j;

k

a