文档介绍：第四章数组
数组
一维数组
二维数组
n维数组
字符数组和字符串
数组排序
排序操作在实际生活中经常遇到,比如给全班总成绩排序?如何用数组实现?
常用的排序方法:
冒泡排序
选择排序
插入排序
冒泡排序法
(1)将第n个数与第n-1个数进行比较,按升序,如果a[n]<a[n-1],则交换它们的值;然后比较第n-1个数与第n-2个数;依次类推,直至第2个数和第1个数比较为止—第一趟冒泡排序结束,结果最小的数被安置在第1个位置即a[1]。
(2)对剩余n-1个数进行第二趟冒泡排序,结果使次小的数被安置在第2个位置即a[2]。
(3)重复上述过程,直到在一趟排序过程中没有进行过交换数为止。
49 38 65 97 76 13 27 30
元素初始化
例
13
76
13
97
13
65
13
38
49
13
13 49 38 65 97 76 27 30
第一趟冒泡结果
27
27
76
97
27
65
27
38
27
49
13 27 49 38 65 97 76 30
第二趟冒泡结果
30
76
30
97
30
65
30
38
49
30
13 27 30 49 38 65 97 76
第三趟冒泡结果
97
76
49
38
13 27 30 38 49 65 76 97
第四趟冒泡结果
13 27 30 38 49 65 76 97
第五趟冒泡结果
13 27 30 38 49 65 76 97
第六趟冒泡结果
13 27 30 38 49 65 76 97
第七趟冒泡结果
冒泡排序编程实现
冒泡排序过程使用双重for循环来实现,设外循环变量为i,用它来决定循环的趟数,它需要从1顺序取值到n-1,其中n为待排序数组中元素的个数;设内循环变量为j,用它来决定每趟循环中两数比较的次数,它的初始值为n-1,即从数组中最后一个数开始,终止值为i,因为第一趟的终止值为1,第二趟的终止值为2,依次类推,第i趟的终止值为i。
选择排序法
(1)首先从n个数中选出最小数的下标,然后将最小数与第1个数交换位置。
(2)除第1个数外,其余n-1个数再按步骤(1)的方法选出次小的数,与第二个数交换。
(3)重复上述操作,共进行n-1趟选择后,最后构成递增序列。
例
初始化:[ 49 38 65 97 76 13 27 ]
k
j
j
j
j
j
j
k
k
13
49
第一趟: 13 [38 65 97 76 49 27 ]
k
k
j
j
j
j
j
27
38
第二趟: 13 27 [65 97 76 49 38 ]
第三趟: 13 27 38 [97 76 49 65 ]
第四趟: 13 27 38 49 [76 97 65 ]
第五趟: 13 27 38 49 65 [97 76 ]
第六趟: 13 27 38 49 65 76 [97 ]
选择排序编程实现
选择排序过程使用双重for循环来实现,设外循环变量为i,它需要从1顺序取值到n-1,其中n为待排序数组中元素的个数,每次的待排序区间为a[i-1]~a[n-1];设内循环变量为j,它需要从i顺序取值到n-1;设k为待排序区间中值最小的元素的下标,开始设k=i-1,每次取值都让a[j]和a[k]进行比较,若a[j]<a[k],则把j赋给k,使得k始终为当前区间中已比较过的所有元素中最小值的下标,每次从当前排序区间中选择出最小值a[k]后,都要把它与a[i-1]的值相交换,使得a[i-1]成为当前区间中的最小值。
插入排序法
把数组a[n]中的n个元素看作为一个有序表和一个无序表,开始时有序表中只有一个元素a[0],无序表中包含n-1个元素a[1]~a[n-1],以后每次从无序表中取出第一个元素a[i](i=1, 2, 3, . . ., n-1),把它插入到前面有序表中的合适位置,使之仍为有序表,这样有序表中就增加一个元素,由上一次的a[0]~a[i-1]变为a[0]~a[i],无序表中就减少一个元素,由上一次的a[i]~a[n-1]变为当前的a[i+1]~a[n-1],经过n-1次插入过程后整个数组a中的n个元素就成为一个有序表。
插入排序算法
需要使用双重for循环,设外层循环变量为i,由于总共需要进行n-1次插入操作,因此设其循环区间为1到n-1;设内层循环变量为j,它的变化范围是从有序表中的最后一个元素到第一个元素,因此其区间是i-1到0。在内层循环开始之前,应首先将无序表中的第一个元素赋给一个变量,设为x,然后通过内层循环找到x在有序表中的位置,并将该位置腾出,最后将