多媒體課件第6講排序問題

排序問題2用冒泡法對數(shù)組元素進行升序排序?qū)個數(shù)進行排序的思路是：如果要對n個數(shù)據(jù)排序，就需要進行n-1輪的比較，每次都對相鄰兩個數(shù)進行比較，將較大的數(shù)交換到后一個元素中。每一輪的比較都找出未排好的數(shù)據(jù)中的最大數(shù)放在這幾個數(shù)的后面。例如，第一輪需要比較n-1次，在n個數(shù)中找出最大數(shù)放在數(shù)組的最后一個元素中；第二輪將對剩下的前n-1個數(shù)進行比較，需要比較(n-1)-1次，將前n-1個數(shù)中的最大者放入數(shù)組的倒數(shù)第二個元素中；……以此類推，第n-1輪需要進行1次比較，將剩下的2個數(shù)中的較大者放入a[1]中，將最小的數(shù)放入a[0]中。當?shù)趎-1輪比較進行完后，所有的數(shù)據(jù)都按照升序在數(shù)組中排列。3用冒泡法對數(shù)組元素進行升序排序的算法例如：a數(shù)組中有10個元素的值如果為：159-28731004第一輪(比較9次)：第1次：a[0]與a[1]159-28731004第2次：a[1]與a[2]159-28731004第3次：a[2]與a[3]15-298731004第4次：a[3]與a[4]15-289731004第5次：a[4]與a[5]15-287931004第6次：a[5]與a[6]15-287391004第7次：a[6]與a[7]15-287391004第8次：a[7]與a[8]15-287390104第9次：a[8]與a[9]15-2873904

104用冒泡法對數(shù)組元素進行升序排序的算法第一輪后a數(shù)組中有10個元素的值為：15-287390410第二輪(比較8次)：第1次：a[0]與a[1]15-287390410第2次：a[1]與a[2]1-2587390410第3次：a[2]與a[3]1-2587390410第4次：a[3]與a[4]1-2578390410第5次：a[4]與a[5]1-2573890410第6次：a[5]與a[6]1-2573890410第7次：a[6]與a[7]1-2573809410第8次：a[7]與a[8]1-25738049

105用冒泡法對數(shù)組元素進行升序排序的算法第二輪后a數(shù)組中有10個元素的值為：1-2573804

9

10第三輪(比較7次)：第1次：a[0]與a[1]-21573804

9

10第2次：a[1]與a[2]-21573804

9

10第3次：a[2]與a[3]-21573804

9

10第4次：a[3]與a[4]-21537804

9

10第5次：a[4]與a[5]-21537804

9

10第6次：a[5]與a[6]-21537084

9

10第7次：a[6]與a[7]-2153704

8

9

106用冒泡法對數(shù)組元素進行升序排序的算法第三輪后a數(shù)組中有10個元素的值為：-21537048

9

10第四輪(比較6次)：第1次：a[0]與a[1]-21537048

9

10第2次：a[1]與a[2]-21537048

9

10第3次：a[2]與a[3]-21357048

9

10第4次：a[3]與a[4]-21357048

9

10第5次：a[4]與a[5]-21350748

9

10第6次：a[5]與a[6]-213504

7

8

9

107用冒泡法對數(shù)組元素進行升序排序的算法第四輪后a數(shù)組中有10個元素的值為：-2135047

8

9

10第五輪(比較5次)：第1次：a[0]與a[1]-2135047

8

9

10第2次：a[1]與a[2]-2135047

8

9

10第3次：a[2]與a[3]-2135

047

8

9

10第4次：a[3]與a[4]-2130

547

8

9

10第5次：a[4]與a[5]-21304

5

7

8

9

108用冒泡法對數(shù)組元素進行升序排序的算法第五輪后a數(shù)組中有10個元素的值為：-21304

5

7

8

9

10第六輪(比較4次)：第1次：a[0]與a[1]-21304

5

7

8

9

10第2次：a[1]與a[2]-21304

5

7

8

9

10第3次：a[2]與a[3]-21034

5

7

8

9

10第4次：a[3]與a[4]-21034

5

7

8

9

109用冒泡法對數(shù)組元素進行升序排序的算法第六輪后a數(shù)組中有10個元素的值為：-21034

5

7

8

9

10第七輪(比較3次)：第1次：a[0]與a[1]-21034

5

7

8

9

10第2次：a[1]與a[2]-20134

5

7

8

9

10第3次：a[2]與a[3]-2013

4

5

7

8

9

1010用冒泡法對數(shù)組元素進行升序排序的算法第七輪后a數(shù)組中有10個元素的值為：-20134

5

7

8

9

10第八輪(比較2次)：第1次：a[0]與a[1]-20134

5

7

8

9

10第2次：a[1]與a[2]-201

34

5

7

8

9

1011用冒泡法對數(shù)組元素進行升序排序的算法第八輪后a數(shù)組中有10個元素的值為：-201

34

5

7

8

9

10第九輪(比較1次)：第1次：a[0]與a[1]-201

34

5

7

8

9

1012用冒泡法對數(shù)組元素進行升序排序的算法程序main(){inta[10];inti,j,t,n=10;printf(“Input10numbers:\n");for(i=0;i<n;i++)scanf("%d",&a[i]);printf("\n");for(i=1;i<n;i++)/*for(i=0;i<n-1;i++)*/ for(j=0;j<n-1;j++)/*可優(yōu)化為for(j=0;j<n-1-i;j++)*/ if(a[j]>a[j+1]){t=a[j]; a[j]=a[j+1];a[j+1]=t;}printf("thesortednumbers:\n");for(i=0;i<n;i++)printf("%d",a[i]);}為數(shù)組元素賦值外循環(huán)控制比較輪數(shù)內(nèi)循環(huán)控制每輪比較次數(shù)相鄰兩個元素進行比較如果后一個元素比前一個元素小，二者交換輸出排序后的數(shù)組13用選擇法對數(shù)組元素進行升序排序選擇法對n個數(shù)進行排序的思路是：如果要對n個數(shù)據(jù)排序，就需要進行n-1輪的比較，每次都從數(shù)組中未排好的子序列中找出一個最小數(shù)，與子序列最前面的一個元素交換，使小數(shù)放在子序列的最前面。例如，第一輪需要比較n-1次，在n個數(shù)中找出最小數(shù)與數(shù)組中的第一個元素（即a[0]）交換，使數(shù)組中的最小數(shù)放在數(shù)組的最前面；第二輪將對剩下的n-1個數(shù)進行比較，需要比較(n-1)-1次，將n-1個數(shù)中的最小的數(shù)與子序列最前面的元素交換，也就數(shù)組中的第二個元素（即a[1]）交換，使子序列中的最小數(shù)放在子序列的最前面；……以此類推，第n-1輪需要進行1次比較，將剩下的2個數(shù)中的小數(shù)與子序列的前面即a[n-2]交換，使子序列中的最小數(shù)子序列中的前面。當?shù)趎-1輪比較進行完后，所有的數(shù)據(jù)都按照升序在數(shù)組中排列。14用選擇法對數(shù)組元素進行升序排序的算法例如：a數(shù)組中有10個元素的值如果為：159-28731004第一輪(比較9次)：第1次：a[0]與a[1]159-28731004第2次：a[0]與a[2]159-28731004第3次：a[0]與a[3]-25918731004第4次：a[0]與a[4]-2591

8731004第5次：a[0]與a[5]-25918

731004第6次：a[0]與a[6]-259187

31004第7次：a[0]與a[7]-25918731004第8次：a[0]與a[8]-259187310

04第9次：a[0]與a[9]-2591873100415用選擇法對數(shù)組元素進行升序排序的算法第一輪后a數(shù)組中有10個元素的值為：-25918731004第二輪(比較8次)：第1次：a[1]與a[2]-25918731004第2次：a[1]與a[3]-2

1958731004第3次：a[1]與a[4]-21958731004第4次：a[1]與a[5]-21958731004第5次：a[1]與a[6]-21958731004第6次：a[1]與a[7]-21958731004第7次：a[1]與a[8]-2

0958731014第8次：a[1]與a[9]-2

095873101416用選擇法對數(shù)組元素進行升序排序的算法第二輪后a數(shù)組中有10個元素的值為：-2

0958731014第三輪(比較7次)：第1次：a[2]與a[3]-2

0

598731014第2次：a[2]與a[4]-2

0598731014第3次：a[2]與a[5]-2

0598731014第4次：a[2]與a[6]-2

0

398751014第5次：a[2]與a[7]-2

0398751014第6次：a[2]與a[8]-2

0

198751034第7次：a[2]與a[9]-2

0

19875103417用選擇法對數(shù)組元素進行升序排序的算法第三輪后a數(shù)組中有10個元素的值為：-2

0

198751034第四輪(比較6次)：第1次：a[3]與a[4]-2

0

1

89751034第2次：a[3]與a[5]-2

0

1

798510

34第3次：a[3]與a[6]-2

0

1

59871034第4次：a[3]與a[7]-2

0

159871034第5次：a[3]與a[8]-2

0

1

39871054第6次：a[3]與a[9]-2

0

1

3987105418用選擇法對數(shù)組元素進行升序排序的算法第四輪后a數(shù)組中有10個元素的值為：-2

0

1

39871054第五輪(比較5次)：第1次：a[4]與a[5]-2

0

1

3

8971054第2次：a[4]與a[6]-2

0

1

3

7981054第3次：a[4]與a[7]-2

0

1

37981054第4次：a[4]與a[8]-2

0

1

3

5981074第5次：a[4]與a[9]-2

0

1

3

498107519用選擇法對數(shù)組元素進行升序排序的算法第五輪后a數(shù)組中有10個元素的值為：-2

0

1

3

4981075第六輪(比較4次)：第1次：a[5]與a[6]-2

0

1

3

4

891075第2次：a[5]與a[7]-2

0

1

3

4891075第3次：a[5]與a[8]-2

0

1

3

4

791085第4次：a[5]與a[9]-2

0

1

3

4

59108720用選擇法對數(shù)組元素進行升序排序的算法第六輪后a數(shù)組中有10個元素的值為：-2

0

1

3

4

591087第七輪(比較3次)：第1次：a[6]與a[7]-2

0

1

3

4

591087第2次：a[6]與a[8]-2

0

1

3

4

5

81097第3次：a[6]與a[9]-2

0

1

3

4

5

7109821用選擇法對數(shù)組元素進行升序排序的算法第七輪后a數(shù)組中有10個元素的值為：-2

0

1

3

4

5

71098第八輪(比較2次)：第1次：a[