第10章 排序

《第10章 排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序10.1排序的基本概念数据结构与算法DataStructuresandAlgorithms10.2插入排序10.2.1直接插入排序(straightinsertionsorting)基本思想：把数组A[n]中待排序的n个元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素A[0]，无序表中包含有n-1个元素A[1]～A[n-1]，排序过程中每次从无序表中取出第一个元素，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表就变为空表，有序表中就包含了全部

2、n个元素，至此排序完毕。数据结构与算法DataStructuresandAlgorithms已排序未排序数据结构与算法DataStructuresandAlgorithms数据结构与算法DataStructuresandAlgorithms数据结构与算法DataStructuresandAlgorithmsvoidInsertSort(structElemTypeA[],intn){ElemTypex;inti,j;for(i=1;i=0;j--)

3、if(x.stn

4、最小的元素，并把它和未排序列表中的第一个元素进行交换。已排序未排序最小元素数据结构与算法DataStructuresandAlgorithms数据结构与算法DataStructuresandAlgorithms数据结构与算法DataStructuresandAlgorithms初始化：wall=0开始找到未排序列表中的最小元素与未排序列表中第一个元素交换是否还有未排序元素？N结束Ywall=wall+1数据结构与算法DataStructuresandAlgorithmsvoidSelectSort

5、(ElemTypeA[],intn){ElemTypex;inti,j,k;for(i=1;i<=n-1;i++){k=i-1;for(j=i;j<=n-1;j++){if(A[j].stn

6、比较和交换使排序码较小的元素逐渐从底部移向顶部，即从下标较大的单元移向下标较小的单元，就象水底下的气泡一样逐渐向上冒。当然，随着排序码较小的元素逐渐上移，排序码较大的元素也逐渐下移。数据结构与算法DataStructuresandAlgorithms首先将A[n-1]元素同A[n-2]元素进行比较，若A[n-1].stn＜A[n-2].stn，则交换两元素的位置，使轻者上浮，重者下沉。接着比较A[n-2]同A[n-3]元素，同样使轻者上浮，重者下沉。以此类推，直到比较A[1]同A[0]元素，并使轻者上

7、浮重者下沉后，第一趟排序结束，此时A[0]为具有最小排序码的元素。然后在A[n-1]～A[1]排序区间内进行第二趟排序，使次最小的元素被上浮到第1单元中；至多重复进行n-1趟后，整个气泡排序结束。数据结构与算法DataStructuresandAlgorithms数据列表被分为两个子列表：已排序和未排序。未排序列表中最小（或最大）的元素通过冒泡的形式（从后往前冒泡）从未排序列表中交换到已排序列表中。数据结构与算法DataStructuresandAlgorithms数据结构与算法DataStructu

8、resandAlgorithms数据结构与算法DataStructuresandAlgorithms初始化：wall=0开始还有未排序的数？N结束Y交换相邻数还有未冒泡的数？比较相邻数YN数据结构与算法DataStructuresandAlgorithmsvoidBubbleSort(ElemTypeA[],intn){ElemTypex;inti,j,flag;for(i=1;i<=n-1;i++){flag=0;for(j=n-1;j>=i;j--)