数据结构(Java)-第9章排序

基本内容1.概述第9章排序2.插入排序3.交换排序4.选择排序5.基数排序6.各种内部排序的比较7.排序项目实践排序是以关键字为基准的，将关键字重新排列成递增或递减的序列。一、概述1.排序算法的稳定性假设待排序的序列中存在多个具有相同关键字的数据元素，若使用某个排序算法后，这些元素的相对位置保持不变，则称此排序算法是稳定的；若元素的相对位置发生了变化，则称为不稳定的。2.内排序与外排序内排序：指在排序的整个过程中，数据全部放在计算机的内存储器中。外排序：指待排序的记录数量很大，以致内存不能一次容纳全部记录，在排序过程中需对外存进行访问的排序过程。二、插入排序9.2.1直接插入排序基本思想：从第2个记录开始，依次将每个记录按其关键字的大小，插入到一个有序的子序列中，使之仍然是有序的，直至所有的记录插完为止。【例9.1】有一组记录，它们的关键字分别为：（28，15，19，37，33，12），用直接插入法进行排序（关键字递增有序）。二、插入排序排序过程：第三趟排序后：(15192837)3312第二趟排序后：(151928)373312第一趟排序后：(1528)19373312数组下标：012345关键字序列：(28)1519373312第四趟排序后：(1519283337)12第五趟排序后：(121519283337)二、插入排序算法实现：publicclassInsertSortTest{

publicvoidInsertSort(int[]a){ intt; for(inti=0;i<a.length-1;i++){//n-1趟扫描

t=a[i+1]; intj=i; while(j>=0){//为每个待插入元素寻找插入位置

if(t<a[j]){//发现插入位置后，执行元素移动

a[j+1]=a[j];//元素后移

} else break; j--; } a[j+1]=t;//将待插入元素放入合适的位置

} }}二、插入排序9.2.2折半插入排序基本思想：利用折半查找代替直接插入排序中的顺序查找，则构成折半插入排序。算法实现：publicclassBinaryInsertSort{//对数组a按关键字升序进行折半插入排序

publicvoidsort(int[]a){sort(a,1);}二、插入排序//将下标为findFlag的元素插入到已排好序的子序列sortArray中

privatevoidsort(int[]sortArray,intfindFlag){if(findFlag>sortArray.length){//排序结束

return;}//将下标为findFlag的元素插入到下标范围在0到findFlag-1的数组sortArraysort(sortArray,0,findFlag-1,findFlag);if(findFlag<sortArray.length-1){sort(sortArray,findFlag+1);}}二、插入排序

//将下标为findFlag的元素插入到下标范围在from到to的数组sortArrayprivatevoidsort(int[]sortArray,intfrom,intto,intfindFlag){//获得即将插入的元素的下标

intsortKey=fintFlag(sortArray,from,to,sortArray[findFlag]);for(;sortKey<=to;sortKey++){charge(sortArray,sortKey,findFlag);}}//将下标为from和下标为to的数组元素交换privatevoidcharge(int[]sortArray,intfrom,intto){if(sortArray[from]>sortArray[to]){inttemp=sortArray[to];sortArray[to]=sortArray[from];sortArray[from]=temp;}}二、插入排序

//返回即将插入的关键字值为key的元素在有序表sortArray中的下标privateintfintFlag(int[]sortArray,intfrom,intto,intkey){if(to-from<=1){if(key<sortArray[from]){returnfrom;}else{returnto;}}

//如果关键字值key比有序表的上届还小，则插入的元素下标应为fromif(key<sortArray[from]){returnfrom;}二、插入排序

//如果关键字值key比有序表的下届还大，则插入的元素下标应为toif(key>sortArray[to]){returnto;}inttemp=(from+to)/2;//获得查找区间的中间点if(key<sortArray[temp+1]&&key>sortArray[temp]){returntemp;}if(sortArray[temp]<key){returnfintFlag(sortArray,temp,to,key);//递归查找右半区}

else{returnfintFlag(sortArray,from,temp,key);//递归查找左半区}}二、插入排序9.2.3希尔排序基本思想：将一个数据序列分成若干组，每组由若干相隔一段距离的元素组成，这段距离称为增量，也称步长因子，然后在一个组内采用直接插入排序算法进行排序。【例9.2】有一组记录，它们的关键字分别为：（28，15，19，37，33，12，45，20，19*，41），用希尔排序算法进行排序（关键字递增有序）。二、插入排序排序过程：

19*37

1920第二趟排序后：12152019*332819453741

3341

15451228第一趟排序后：12151919*33284520374112203319371519*28454112152019*332819453741第三趟排序后：12151919*202833374145281519373312452019*41二、插入排序算法实现：publicclassShellSortTest{//对数组a按增量d进行希尔排序

publicvoidshell(int[]a,intd){ intt; intn=a.length; intj=0; for(inti=d;i<n;i++){//对每组子序列执行插入操作

if(a[i]<a[i-d]){ t=a[i]; j=i-d; do{ a[j+d]=a[j];//记录后移

j=j-d;//查找下一个记录

}while(j>0&&t<a[j]); a[j+d]=t;//插入a[i] } } }二、插入排序

//计算希尔排序的增量，然后调用希尔排序算法实现排序 publicvoidshellSort(int[]a){ intincr=a.length; do{ incr=incr/2;//计算增量 shell(a,incr); }while(incr>=1); }}三、交换排序9.3.1冒泡排序基本思想：将长度为n的记录，从头到尾依次与相邻的两个记录进行比较，若为逆序则将两个记录交换，将序列照此方法从头到尾处理一遍称作一趟冒泡排序，这样就可以将关键字值最大的记录交换到最后的位置上（假设按升序排列）。然后，对前面n-1个记录进行同样的操作，那么经过第二趟排序，关键字值次大的记录交换到n-1个位置上。依次类推，直到所有的记录有序。【例9.3】有一组记录，它们的关键字分别为：（33，15，19，28，37，12），用冒泡排序算法进行排序（关键字递增有序）。排序过程：三、交换排序第五趟排序后：121519333741第三趟排序后：151912333741第二趟排序后：151933123741第一趟排序后：153319371241数组下标：012345关键字序列：331541193712第四趟排序后：151219333741算法实现：publicclassBubbleSortTest{//对数组a按关键字升序进行冒泡排序publicvoidbubbleSort(int[]a){ intt; intn=a.length; for(inti=0;i<n-1;i++){ for(intj=0;j<n-i-1;j++){ if(a[j]>a[j+1]){//若为逆序，则将a[j]与a[j+1]交换

t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } }}}三、交换排序三、交换排序9.3.2快速排序基本思想：从数组中取出一个元素作为基准值，把其它元素分为两组：一组是全部小于基准值的元素；另一组是全部大于基准值的元素，然后通过递归对这两个组再分别排序。排序过程：设1≤p<q≤n，r[p],r[p+1],...,r[q]为待排序列，快速排序的具体算法描述如下：步骤一：low=p；high=q；//设置两个对象low和highr[0]=r[low]；//取第一个记录为基准记录，low位置暂设为空位步骤二：若low=high，则r[low]=r[0];//填入基准记录，即确定了基准记录的位置否则，若low<high，搜索需要交换的记录，并交换之三、交换排序步骤三：若low<high且r[high]≥r[0]，则high=high-1；转步骤三；//从high所指位置向前搜索，至多到 //low+1位置；然后寻找r[high]<r[0]r[low]=r[high]；//找到r[high]<r[0]，设置high为新基准位置，

//然后小于基准记录关键字的记录前移。步骤四：若low<high且r[low]<r[0]low=low+1；转步骤四；//从low所指位置向后搜索，至多到high-1位 //置，然后寻找r[low]≥r[0] r[high]=r[low]；//找到r[low]≥r[0]，设置low为新基准记录位置，

//大于等于基准记录关键字的记录后移。 转步骤二//继续寻找空位算法实现：publicclassQuickSortTest{publicvoidquickSort(int[]c,intlow,inthigh){ inttemp=c[low];//取出基准记录

intn=high-low+1;//获得排序的元素个数

inti=low,j=high; while(i<j){ while(c[j]>temp&&i<j){//从j开始搜索小于基准记录的值

j--; } if(i<j){//出现小于基准记录的值后，将j对应的值放到i处

c[i]=c[j]; i++; } while(c[i]<=temp&&i<j){//从i向后搜索，找出大于基准记录的值

i++; }三、交换排序 if(i<j){//出现大于基准记录的值后，将i处的值放入j处

c[j]=c[i]; j--; } } c[i]=temp;//把基准记录放入合适的位置

if(low<i-1) quickSort(c,low,i-1);//对左子序列进行快速排序

if(high>i+1) quickSort(c,i+1,high);//对右子序列进行快速排序

}}三、交换排序四、选择排序9.4.1简单选择排序基本思想：从待排序的所有记录中，选取关键字值最小的记录并将它与原始序列中的第一个记录交换位置；然后，去掉关键字值最小的记录，从剩下的记录中选取关键字值最小的记录并将它与原始序列中第二个记录交换位置……如此反复进行下去，直到序列中全部记录排序完毕。【例9.5】有一组记录，它们的关键字分别为：（83,40,63,13,84,35），用简单选择排序算法进行排序（关键字递增有序）。排序过程：四、选择排序第五趟排序后：133540638384第三趟排序后：133540838463第二趟排序后：133563838440第一趟排序后：134063838435数组下标：012345关键字序列：834063138435第四趟排序后：133540638483算法实现：publicclassSelectSortTest{ publicvoidselectSort(int[]a){ intmin;//min存储单趟排序的最小元素

inttemp;//temp作为交换的临时变量

intindex=0;//存储单趟排序最小元素的下标

intn=a.length;//存取待排序列的长度

for(inti=0;i<n;i++){//n个元素排n-1趟

min=a[i]; index=i; for(intj=i+1;j<n;j++){//查找最小元素

if(a[j]<min){ min=a[j]; index=j;//记录最小元素的下标

} }四、选择排序

if(index!=i){//如果最小元素不是下标为i的元素，则进行交换 temp=a[i]; a[i]=a[index]; a[index]=temp; }

} }}四、选择排序四、选择排序9.4.2堆排序堆的定义：具有n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系时，称之为堆。（1）ki≤k2i并且ki≤k2i+1（2）ki≥k2i并且ki≥k2i+1满足条件（1）称为小根堆，满足条件（2）称为大根堆。962791138831327384965765097小根堆大根堆四、选择排序基本思想：利用小根堆（或大根堆）来选取当前无序序列中关键字最小（或最大）的记录来排序。设有n个元素，首先将这n个元素按关键字建成堆，将堆顶元素输出，得到n个元素中关键字最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键字次小(或次大)的元素。如此反复，便得到一个按关键字有序的序列。堆排序分两个阶段：（1）创建最小堆（或最大堆），即：将n个元素的序列按关键字建成堆；（2）调整堆，即：输出堆顶元素后，调整剩余n-1个元素，使其按关键字成为一个新堆。四、选择排序（1）创建最小堆在具有n个结点的完全二叉树中，首先从第个结点为根的子树开始，将该子树的根结点与它的孩子结点的值进行比较，将较小者与之交换，使该子树成为堆，然后向前依次对各结点为根的子树重复上述步骤，使之成为堆，直到根结点。【例9.6】设关键字序列为{（49，38，65，97，76，13，27，50）}，创建最小堆。49653827137697504965382713765097491338276576509749133827657650971327384965765097四、选择排序（2）调整堆输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。例9.6已创建好了一个最小堆，写出其堆排序的过程。13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13273849502765769713输出：13276549502738769713输出：1327384965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765762738495013输出：1327384950657665972738495013输出：1327384950659765762738495013输出：132738495065769765762738495013输出：1327384950657697五、归并排序2－路归并排序基本思想：假设初始序列有n个记录，首先把n个记录看成n个长度为1的有序序列，进行两两归并，得到个长度为2的关键字有序序列，再两两归并直到所有记录归并成一个长度为n的有序序列为止。【例9.8】有一组记录，它们的关键字分别为：（51，60，38，17，59，22，20，85），用2-路归并法进行排序（关键字递增有序）。五、归并排序排序过程：数组下标：01234567关键字序列：5160381759222085第三趟排序后：[1720223851596085]第一趟排序后：[5160][1738][2259][2085]第二趟排序后：[17385160][20225985]六、基数排序9.6.1多关键字排序多关键字的定义例对52张扑克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A两个关键字：花色（<<<）面值（2<3<……<A）并且“花色”地位高于“面值”六、基数排序多关键字排序最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。六、基数排序