数据结构6(4月28日)课件

查找：根据给定的关键字值，在一组数据元素中确定一个其关键字值等于给定值的数据元素的过程。若存在这样的数据元素，则称查找成功；若不存在这样的数据元素，则称查找失败。关键字:指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。查找表：指一组待查数据元素的集合。它具有一定存储结构，如顺序表结构、链式结构、树形结构等。

2.6查找查找：2.6查找1)查找的方法查找某个数据元素依赖于查找表中数据元素的组织方式。按照数据元素的组织方式决定采用某种查找方法；反之,为了提高查找方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。2)查找算法的评价衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。而在查找算法中，基本运算是给定值与关键字值的比较，即算法的主要时间是花费在“比较”上的，所以，用平均查找长度作为评价查找算法好坏的依据。对于含有n个数据元素的查找表，查找成功的平均查找长度为ASL=其中：Pi为查找第i个数据元素的概率；Ci为查找到第i个数据元素时，需进行的比较次数。1)查找的方法ASL=其中：Pi为查找第i个数据元**查找方法分类线性查找法顺序查找法对半查找法分块查找法…基于树的查找法二叉排序树B树…计算式查找法——哈希法顺序存储的查找方法链式存储的查找方法散列存储的查找方法**查找方法分类线性查找法顺序存储的查找方法链式存储的查找方2.6.1

顺序查找法基本思想是：从数组的第一个元素开始，与查找的关键字逐个比对，直到找到关键字所在的位置或遇到数组的结尾为止，若找到，则返回关键字在数组中的位置，否则返回-1(因为C#的数组下标不可能为-1)。publicintsearch(intkeyValue){inti=0；while()i++;if()return(i);elsereturn(-1);}假设每个元素等概率查找,则平均查找次数为(n+1)/2i<length&&

data[i]!=keyValuei<length2.6.1顺序查找法假设每个元素等概率查找,则平均查找次数2.6.2对半查找法以顺序方式存放的有序表的查找可采用对半查找。将被查关键字k与线性表中间位置mid上的数据元素的关键字进行比较：(假设表按由小到大顺序排列）（1）若k==a[mid]，则查找成功，过程结束。（2）若k>a[mid],则取表的后半部分作为新表再去查找。（3）若k<a[mid],则取表的前半部分作为新表再进行查找。这个过程一直进行到查找成功或子表的长度为0为止。对半查找是基于关键字比较的最优方法。2.6.2对半查找法对半查找是基于关键字比较的最优方法。publicintbinSearch(intkeyValue){intlow,high,mid;low=0;high=length-1;while(){mid=(low+high)/2;if(data[mid]==keyValue);elseif(data[mid]<keyValue);else;}return(-1);}low<=highreturn(mid)low=mid+1high=mid-1对半查找成功时比较次数最多为log2n+1publicintbinSearch(intkeyVa**分块查找(索引顺序查找）“分块有序”表特点：(1)表中数据分块(2)块中数据不必有序(3)块间有序“分块有序”表的结构有两部分：(1)顺序存储结构的线性表(2)索引表（由每块的最大元素组成）分块查找过程：(1)用对半查找法查找索引表，确定待查项x所在的块。(2)在相应的块中用顺序查找法查找待查项x。**分块查找(索引顺序查找）2.6.3二叉排序树及查找若线性表中的结点经常插入和删除，就应设计成把链表和二分法结合的查找方法。二叉排序树是将线形表中的元素组织成二叉树的形式，以达到与对半查找相同的查找效率。1、二叉排序树定义：（1）若它的左子树不空，则左子树上所有的关键字均小于它 的根结点的关键字；（2）若它的右子树不空，则右子树上所有的关键字均大于或 等于它的根结点的关键字；（3）它的左、右子树也是二叉排序树。

如果按中序遍历二叉排序树，可得到一个递增排列的序列。2.6.3二叉排序树及查找526481937中序遍历序列：1、2、3、4、5、6、7、8、9二叉排序树示例：526481937中序遍历序列：1、2、3、4、5、6、7、//TreeNode类publicclassTreeNode{publicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}//BiTree类publicclassBiTree{privateTreeNoderoot;publicBiTree(){root=null;}publicvoidinsBTree(chark){//二叉排序树创建}

publicTreeNodebanSearch(chark){//二叉排序查找方法}}二叉排序树代码表示：//TreeNode类//BiTree类二叉排序树代码表示：2、查找算法及实现在给定的二叉排序树t中查找给定待查关键字k：从根结点出发（1）如果树t为空，那么查找失败。算法结束；否则，转（2）（2）如果t.data等于k，则查找成功。算法结束。否则转（3）（3）如果k<t.data，则t=t.leftchild(到左子树查找)， 转(1);否则t=t.rightchild（到右子树查找），转（1）。2、查找算法及实现publicTreeNodebanSearch(chark){TreeNodep=root;while(){if(p.data>k);else;}return(p);}(p!=null)&&(p.data!=k)p=p.leftChildp=p.rightChildpublicTreeNodebanSearch(cha

假设一组数据元素的关键字序列如下：{45，24，53，12，37，93，30，40，80}分析查找元素40

如何创建二叉排序树？假设一组数据元素的关键字序列如下：如3、创建二叉排序树

通过在初始为空的树中不断插入数k来建立二叉排序树，步骤：（1）若二叉排序树为空，则插入结点应为根结点（2）若二叉排序树非空，根据关键字比较的结果确定是在左 子树还是在右子树中继续查找插入位置，直至某个结点的 左子树或右子树空为止，则插入结点应为该结点的左孩子 或右孩子。3、创建二叉排序树

假定由整数序列{10，6，19，22，8，2}生成一棵二叉排序树，可以采用逐个元素插入的方法实现。

(1)首先将10作为根结点

(2)然后插入6时，通过比较知6<10，所以将6作为10的 左孩子插入；

(3)同理将19作为10的右孩子插入；

(4)整数22通过和10、19比较后，作为19的右孩子插入。

(5)依次插入剩余的其他元素

假定由整数序列{10，6，19，22，8，2}生成一棵publicvoidinsBTree(chark)//将k插入到二叉排序树{TreeNodep,q;q=newTreeNode(k);if(root==null)//树为空，该节点即根节点

{root=q;return;}p=root;//从根开始开始找位置

while((p.leftChild!=q)&&(p.rightChild!=q))//尚未插入新节点

{if(k<p.data){if(p.leftChild!=null);else;}else{if()p=p.rightChild;elsep.rightChild=q;}}}p=p.leftChildp.leftChild=qp.rightChild!=nullpublicvoidinsBTree(chark)4.二叉排序树的构造如果给定一个数据元素的集合，则数据元素的读入顺序不同，其构造出的二叉排序树的形态也不同。例序列(53,61,12,37,90,100,3,78,45)， (61,37,90,45,100,78,12,3,53), (3,12,37,45,53,61,78,90,100)构造的二叉排序树分别为图1，图2和图3。531261337904578100613790124535378100图1图2312374553617890100图34.二叉排序树的构造53126133790457810065.二叉排序树的平衡化处理二叉排序树的查找效率与构成的二叉排序树的形态有关。为了提高查找效率，还需在构造二叉排序树的过程中进行“平衡化”处理，使之成为平衡的二叉排序树。这样，平衡二叉排序树的查找就与折半查找一样高效。平衡二叉树的递归定义如下：平衡二叉树或是一棵空树，或是一棵具有下列性质的二叉树：(1)左子树与右子树的深度之差的绝对值不超过1；(2)左、右子树也是平衡二叉树。5.二叉排序树的平衡化处理2.7排序排序是将一个数据元素的无序序列，按其关键字的大小重新排列，变成一个有序序列。分为内部排序和外部排序.内部排序:排序操作都在内存中进行.以比较次数衡量算法效率.外部排序:排序操作还需访问外存.以访问外存的次数衡量算法效率排序算法的稳定性:对于关键字相同的元素,排序中不改变其相对次序,称为稳定的排序算法;反之称为不稳定的排序算法.按算法效率分简单的排序和先进的排序。前者包括选择法排序、冒泡法排序、插入法排序；后者则包括快速排序法和归并排序。2.7排序2.7.1选择排序第1步：在N个元素的排序表中选择最小元素第2步：将最小元素与表头元素交换第3步：N=N-1第4步：若N>1，则执行第1步，否则结束排序

初始状态4521341952603424第1趟（i=1）[19]21344552603424第2趟（i=2）[19

21]344552603424第3趟（i=3）[19

2124]4552603434第4趟（i=4）[19

212434]52604534第5趟（i=5）[19

21243434]604552第6趟（i=6）[19

2124343445]6052第7趟（i=7）[19

212434344552]60可见，选择排序是一种不稳定的排序。2.7.1选择排序第1步：在N个元素的排序表中选择最小元素具体算法描述如下:

publicvoidselectSort(){inti,j,k;for(i=0;i<length-1;i++){; for(j=i+1;j<n;j++)if()

k=j;//记录最小元素的位置

if(){intx=data[i];data[i]=data[k];data[k]=x;}}}k=idata[j]<data[k]k!=i具体算法描述如下:k=idata[j]<data[k2.6.2交换排序1、冒泡排序将待排序文件中的记录两两比较，若为逆序，则进行交换。按此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是将关键字最大的记录交换到了表尾。对余下n-1个记录，重复此过程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状态[4521341952603424]第一趟21341945523424[60]第二趟211934453424[5260]第三趟1921343424[455260]第四趟19213424[34455260]第五趟192124[3434455260]第六趟1921243434455260可见，冒泡算法是稳定的。2.6.2交换排序可见，冒泡算法是稳定的。publicvoidbubSort(){boolneedChange=true;

intj=length-1;while(){needChange=false;//先假定不需要交换

for(inti=0;i<j;i++)if(data[i]>data[i+1]){;

inttemp=data[i];data[i]=data[i+1];data[i+1]=temp;}j--;}}needChange的作用是当前内循环无交换时，即终止程序的运算。needChange&&j>0needChange=truepublicvoidbubSort()needChan**直接插入排序基本思想：将n个待排序元素看成为一个有序表和一个无序表。开始有序表只有一个元素，无序表中则有n-1个元素。排序过程中每次从无序表中取出第一个元素，将其关键字与有序表的关键字比较，将其插入到适当位置，使之成为新的有序表。插入步骤：（1）将无序表中的第一个元素存入辅助变量temp中。（2）将temp和有序表中从最后一个元素开始进行比较，若小于有序表中的元素，则有序表中该元素后移一位，同时继续和前一元素比较。否则插入到该元素的后面。**直接插入排序基本思想：初始状态[45]21341952603424

第一趟[2145]341952603424

第二趟[213445]1952603424

第三趟[19213445]52603424

第四趟[1921344552]603424

第五趟[192134455260]3424

第六趟[19213434455260]24

第七趟[1921243434455260]

有序文件1921243434455260插入排序是稳定的排序初始状态[45]21341952publicvoidinsertSort(){ inti,j,temp; for(i=1;i<length;i++) {;//将待插入元素保存 j=i-1;//有序表最后一个元素的下标 while(j>=0&&temp<data[j]) { ; j--; } ; }}data[j+1]=data[j]data[j+1]=temptemp=data[i]publicvoidinsertSort()data[j2.6.4快速排序基本思想：在待排序的n个元素中任取一个元素R，以该元素排序码k为准，将所有剩下的n-1个元素分割为两个子序列：第一个子序列中每个元素的排序码均小于或等于k；第二个子序列中每个元素的排序码均大于或等于k。然后将k所对应的元素放在两个子序列之间。完成第一趟排序，使得待排序序列成为

<子序列1>R<子序列2>分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个元素时为止。2.6.4快速排序线性表分割步骤:（1）设置两个指示器i和j，其初始状态分别指向区间内第一个记录和最后一个记录。（2）将第一个记录移向辅助变量x中（3）从j所指位置起向前搜索第一个小于x的记录，找到后，将a[j]移至a[i]的位置；（4）从i所指向的位置向后搜索第一个关键字大于x的记录，找到后，将a[i]移至a[j]的位置；（5）重复3、4两步，直至i==j，最后将x送至a[i]中去。至此一趟排序完成，文件划分为两个子序列。重复以上步骤直到每个子序列中只有一个元素时为止。数据结构6(4月28日)课件初始状态4521341952603424ij一次交换24213419526034

24

i→j二次交换2421341952603452i←j三次交换242134193460

3452i→j[2421341934]45[6052]ij(a)一趟排序初始状态[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件1921243434455260(b)全部快速排序初始状态452134195260

privatevoidqkOne(intstart,intend,outintmid){intx,i,j;i=start;j=end;x=data[i];//将第一个值保存在x中

while(){while(i<j&&data[j]>=x)//自右向左扫描

;

if(i<j){;i++;}while(i<j&&data[i]<=x)//自左向右扫描

;

if(i<j){data[j]=data[i];j--;}};mid=i;}i!=jj--data[i]=data[j]i++data[i]=x一趟分割的代码privatevoidqkOne(intstart,快速排序是不稳定的排序，但是内排序中速度最快的。publicvoidqkSort(){intstart=0,end=length-1,mid;ArrayStackas=newArrayStack(100);//建立一个堆栈as.push(start);as.push(end);while(!as.isEmpty()){end=as.pop();//与压栈的次序相反，弹出位置start=as.pop();while(start<end){qkone(start,end,outmid);as.push(mid+1);//将分割后的第二个序列压栈

as.push(end);end=mid-1;//调节位置准备对第一个序列再分割，位置从start到mid-1}}}快速排序快速排序是不稳定的排序，但是内排序中速度最快的。public2.7.3归并排序采用二路归并技术，即每次将数组a中两个相邻的有序序列归并为一个有序序列。排序步骤：（1）假设待排序文件含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1（2）两两归并，得到[n/2]个长度为2或1的有序子序列（3）再两两归并，直到得到一个长度为n的有序文件为止。2.7.3归并排序初始状态[45][21][34][19][52][60][34][24]┕━━┙┕━━┙┕━━┙┕━━┙第一趟[2145][1934][5260][2434]┕━━┙┕━━┙第二趟[19213445][24345260]┕━━━━━━┙第三趟1921243434455260二路归并排序过程示例

二路归并排序是稳定的排序初始状态[45][21][34][19][52]有序文件a[s..m]和a[m+1...t]归并为b[s..t]的算法:twoSort(inta[],ints,intm,intt,intb[]){inti,j,k;i=s;//i是a[s..m]的指示器j=m+1;//j是a[m+1..t]的指示器k=s-1;//k是b[s..t]的指示器while(){k++;if(a[i]<=a[j]){;i++;}else{;j++;}}

b[k]=a[i]b[k]=a[j]i<=m&&j<=t有序文件a[s..m]和a[m+1...t]归并为b[s..if(i>m)for(;;j++){k++;b[k]=a[j];}elsefor(;;i++){k++;b[k]=a[i];}}j<=ti<=mif(i>m)j<=ti<=m

假设文件长度为n,每个子文件的长度为k，归并结果存放在数组b中，则一趟归并描述如下:voidmerge(inta[],intk,intn,intb[]){inti=0;while(n-i>=2*k){twosort(a,i,i+k-1,i+2*k-1,b);i=i+2*k;}if(n-i>k)twosort(a,i,i+k-1,n-1,b);elsefor(;i<n;i++)b[i]=a[i];}

假设文件长度为n,每个子文件的长度为k，归并结果存放一趟归并后，有序子文件长度为2，二趟归并后，有序子文件长度为4，因归并的结果在b中,故每次归并完将其复制到a中。重复此过程，直到有序子文件为n，具体算法描述如下voidmergeSort(inta[],intn){intk=1,b[N];//N为已定义的符号常量,代表线性表的长度while(k<n){merge(a,k,n,b);k=2*k;for(inti=0;i<N;i++)a[i]=b[i];}

}一趟归并后，有序子文件长度为2，二趟归并后，有序子文件长度为各种排序方法的比较各种排序方法的比较（学号-6-1）将如下一组数据插入到一棵二叉排序树中，并将该二叉排序树的中序遍历结果输出。{45，24，53，12，37，93，30，40，80}作业（学号-6-1）将如下一组数据插入到一棵二叉排序树中，并将该查找：根据给定的关键字值，在一组数据元素中确定一个其关键字值等于给定值的数据元素的过程。若存在这样的数据元素，则称查找成功；若不存在这样的数据元素，则称查找失败。关键字:指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。查找表：指一组待查数据元素的集合。它具有一定存储结构，如顺序表结构、链式结构、树形结构等。

2.6查找查找：2.6查找1)查找的方法查找某个数据元素依赖于查找表中数据元素的组织方式。按照数据元素的组织方式决定采用某种查找方法；反之,为了提高查找方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。2)查找算法的评价衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。而在查找算法中，基本运算是给定值与关键字值的比较，即算法的主要时间是花费在“比较”上的，所以，用平均查找长度作为评价查找算法好坏的依据。对于含有n个数据元素的查找表，查找成功的平均查找长度为ASL=其中：Pi为查找第i个数据元素的概率；Ci为查找到第i个数据元素时，需进行的比较次数。1)查找的方法ASL=其中：Pi为查找第i个数据元**查找方法分类线性查找法顺序查找法对半查找法分块查找法…基于树的查找法二叉排序树B树…计算式查找法——哈希法顺序存储的查找方法链式存储的查找方法散列存储的查找方法**查找方法分类线性查找法顺序存储的查找方法链式存储的查找方2.6.1

顺序查找法基本思想是：从数组的第一个元素开始，与查找的关键字逐个比对，直到找到关键字所在的位置或遇到数组的结尾为止，若找到，则返回关键字在数组中的位置，否则返回-1(因为C#的数组下标不可能为-1)。publicintsearch(intkeyValue){inti=0；while()i++;if()return(i);elsereturn(-1);}假设每个元素等概率查找,则平均查找次数为(n+1)/2i<length&&

data[i]!=keyValuei<length2.6.1顺序查找法假设每个元素等概率查找,则平均查找次数2.6.2对半查找法以顺序方式存放的有序表的查找可采用对半查找。将被查关键字k与线性表中间位置mid上的数据元素的关键字进行比较：(假设表按由小到大顺序排列）（1）若k==a[mid]，则查找成功，过程结束。（2）若k>a[mid],则取表的后半部分作为新表再去查找。（3）若k<a[mid],则取表的前半部分作为新表再进行查找。这个过程一直进行到查找成功或子表的长度为0为止。对半查找是基于关键字比较的最优方法。2.6.2对半查找法对半查找是基于关键字比较的最优方法。publicintbinSearch(intkeyValue){intlow,high,mid;low=0;high=length-1;while(){mid=(low+high)/2;if(data[mid]==keyValue);elseif(data[mid]<keyValue);else;}return(-1);}low<=highreturn(mid)low=mid+1high=mid-1对半查找成功时比较次数最多为log2n+1publicintbinSearch(intkeyVa**分块查找(索引顺序查找）“分块有序”表特点：(1)表中数据分块(2)块中数据不必有序(3)块间有序“分块有序”表的结构有两部分：(1)顺序存储结构的线性表(2)索引表（由每块的最大元素组成）分块查找过程：(1)用对半查找法查找索引表，确定待查项x所在的块。(2)在相应的块中用顺序查找法查找待查项x。**分块查找(索引顺序查找）2.6.3二叉排序树及查找若线性表中的结点经常插入和删除，就应设计成把链表和二分法结合的查找方法。二叉排序树是将线形表中的元素组织成二叉树的形式，以达到与对半查找相同的查找效率。1、二叉排序树定义：（1）若它的左子树不空，则左子树上所有的关键字均小于它 的根结点的关键字；（2）若它的右子树不空，则右子树上所有的关键字均大于或 等于它的根结点的关键字；（3）它的左、右子树也是二叉排序树。

如果按中序遍历二叉排序树，可得到一个递增排列的序列。2.6.3二叉排序树及查找526481937中序遍历序列：1、2、3、4、5、6、7、8、9二叉排序树示例：526481937中序遍历序列：1、2、3、4、5、6、7、//TreeNode类publicclassTreeNode{publicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc){data=c;leftChild=null;rightChild=null;}}//BiTree类publicclassBiTree{privateTreeNoderoot;publicBiTree(){root=null;}publicvoidinsBTree(chark){//二叉排序树创建}

publicTreeNodebanSearch(chark){//二叉排序查找方法}}二叉排序树代码表示：//TreeNode类//BiTree类二叉排序树代码表示：2、查找算法及实现在给定的二叉排序树t中查找给定待查关键字k：从根结点出发（1）如果树t为空，那么查找失败。算法结束；否则，转（2）（2）如果t.data等于k，则查找成功。算法结束。否则转（3）（3）如果k<t.data，则t=t.leftchild(到左子树查找)， 转(1);否则t=t.rightchild（到右子树查找），转（1）。2、查找算法及实现publicTreeNodebanSearch(chark){TreeNodep=root;while(){if(p.data>k);else;}return(p);}(p!=null)&&(p.data!=k)p=p.leftChildp=p.rightChildpublicTreeNodebanSearch(cha

假设一组数据元素的关键字序列如下：{45，24，53，12，37，93，30，40，80}分析查找元素40

如何创建二叉排序树？假设一组数据元素的关键字序列如下：如3、创建二叉排序树

通过在初始为空的树中不断插入数k来建立二叉排序树，步骤：（1）若二叉排序树为空，则插入结点应为根结点（2）若二叉排序树非空，根据关键字比较的结果确定是在左 子树还是在右子树中继续查找插入位置，直至某个结点的 左子树或右子树空为止，则插入结点应为该结点的左孩子 或右孩子。3、创建二叉排序树

假定由整数序列{10，6，19，22，8，2}生成一棵二叉排序树，可以采用逐个元素插入的方法实现。

(1)首先将10作为根结点

(2)然后插入6时，通过比较知6<10，所以将6作为10的 左孩子插入；

(3)同理将19作为10的右孩子插入；

(4)整数22通过和10、19比较后，作为19的右孩子插入。

(5)依次插入剩余的其他元素

假定由整数序列{10，6，19，22，8，2}生成一棵publicvoidinsBTree(chark)//将k插入到二叉排序树{TreeNodep,q;q=newTreeNode(k);if(root==null)//树为空，该节点即根节点

{root=q;return;}p=root;//从根开始开始找位置

while((p.leftChild!=q)&&(p.rightChild!=q))//尚未插入新节点

{if(k<p.data){if(p.leftChild!=null);else;}else{if()p=p.rightChild;elsep.rightChild=q;}}}p=p.leftChildp.leftChild=qp.rightChild!=nullpublicvoidinsBTree(chark)4.二叉排序树的构造如果给定一个数据元素的集合，则数据元素的读入顺序不同，其构造出的二叉排序树的形态也不同。例序列(53,61,12,37,90,100,3,78,45)， (61,37,90,45,100,78,12,3,53), (3,12,37,45,53,61,78,90,100)构造的二叉排序树分别为图1，图2和图3。531261337904578100613790124535378100图1图2312374553617890100图34.二叉排序树的构造53126133790457810065.二叉排序树的平衡化处理二叉排序树的查找效率与构成的二叉排序树的形态有关。为了提高查找效率，还需在构造二叉排序树的过程中进行“平衡化”处理，使之成为平衡的二叉排序树。这样，平衡二叉排序树的查找就与折半查找一样高效。平衡二叉树的递归定义如下：平衡二叉树或是一棵空树，或是一棵具有下列性质的二叉树：(1)左子树与右子树的深度之差的绝对值不超过1；(2)左、右子树也是平衡二叉树。5.二叉排序树的平衡化处理2.7排序排序是将一个数据元素的无序序列，按其关键字的大小重新排列，变成一个有序序列。分为内部排序和外部排序.内部排序:排序操作都在内存中进行.以比较次数衡量算法效率.外部排序:排序操作还需访问外存.以访问外存的次数衡量算法效率排序算法的稳定性:对于关键字相同的元素,排序中不改变其相对次序,称为稳定的排序算法;反之称为不稳定的排序算法.按算法效率分简单的排序和先进的排序。前者包括选择法排序、冒泡法排序、插入法排序；后者则包括快速排序法和归并排序。2.7排序2.7.1选择排序第1步：在N个元素的排序表中选择最小元素第2步：将最小元素与表头元素交换第3步：N=N-1第4步：若N>1，则执行第1步，否则结束排序

初始状态4521341952603424第1趟（i=1）[19]21344552603424第2趟（i=2）[19

21]344552603424第3趟（i=3）[19

2124]4552603434第4趟（i=4）[19

212434]52604534第5趟（i=5）[19

21243434]604552第6趟（i=6）[19

2124343445]6052第7趟（i=7）[19

212434344552]60可见，选择排序是一种不稳定的排序。2.7.1选择排序第1步：在N个元素的排序表中选择最小元素具体算法描述如下:

publicvoidselectSort(){inti,j,k;for(i=0;i<length-1;i++){; for(j=i+1;j<n;j++)if()

k=j;//记录最小元素的位置

if(){intx=data[i];data[i]=data[k];data[k]=x;}}}k=idata[j]<data[k]k!=i具体算法描述如下:k=idata[j]<data[k2.6.2交换排序1、冒泡排序将待排序文件中的记录两两比较，若为逆序，则进行交换。按此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是将关键字最大的记录交换到了表尾。对余下n-1个记录，重复此过程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状态[4521341952603424]第一趟21341945523424[60]第二趟211934453424[5260]第三趟1921343424[455260]第四趟19213424[34455260]第五趟192124[3434455260]第六趟1921243434455260可见，冒泡算法是稳定的。2.6.2交换排序可见，冒泡算法是稳定的。publicvoidbubSort(){boolneedChange=true;

intj=length-1;while(){needChange=false;//先假定不需要交换

for(inti=0;i<j;i++)if(data[i]>data[i+1]){;

inttemp=data[i];data[i]=data[i+1];data[i+1]=temp;}j--;}}needChange的作用是当前内循环无交换时，即终止程序的运算。needChange&&j>0needChange=truepublicvoidbubSort()needChan**直接插入排序基本思想：将n个待排序元素看成为一个有序表和一个无序表。开始有序表只有一个元素，无序表中则有n-1个元素。排序过程中每次从无序表中取出第一个元素，将其关键字与有序表的关键字比较，将其插入到适当位置，使之成为新的有序表。插入步骤：（1）将无序表中的第一个元素存入辅助变量temp中。（2）将temp和有序表中从最后一个元素开始进行比较，若小于有序表中的元素，则有序表中该元素后移一位，同时继续和前一元素比较。否则插入到该元素的后面。**直接插入排序基本思想：初始状态[45]21341952603424

第一趟[2145]341952603424

第二趟[213445]1952603424

第三趟[19213445]52603424

第四趟[1921344552]603424

第五趟[192134455260]3424

第六趟[19213434455260]24

第七趟[1921243434455260]

有序文件1921243434455260插入排序是稳定的排序初始状态[45]21341952publicvoidinsertSort(){ inti,j,temp; for(i=1;i<length;i++) {;//将待插入元素保存 j=i-1;//有序表最后一个元素的下标 while(j>=0&&temp<data[j]) { ; j--; } ; }}data[j+1]=data[j]data[j+1]=temptemp=data[i]publicvoidinsertSort()data[j2.6.4快速排序基本思想：在待排序的n个元素中任取一个元素R，以该元素排序码k为准，将所有剩下的n-1个元素分割为两个子序列：第一个子序列中每个元素的排序码均小于或等于k；第二个子序列中每个元素的排序码均大于或等于k。然后将k所对应的元素放在两个子序列之间。完成第一趟排序，使得待排序序列成为

<子序列1>R<子序列2>分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个元素时为止。2.6.4快速排序线性表分割步骤:（1）设置两个指示器i和j，其初始状态分别指向区间内第一个记录和最后一个记录。（2）将第一个记录移向辅助变量x中（3）从j所指位置起向前搜索第一个小于x的记录，找到后，将a[j]移至a[i]的位置；（4）从i所指向的位置向后搜索第一个关键字大于x的记录，找到后，将a[i]移至a[j]的位置；（5）重复3、4两步，直至i==j，最后将x送至a[i]中去。至此一趟排序完成，文件划分为两个子序列。重复以上步骤直到每个子序列中只有一个元素时为止。数据结构6(4月28日)课件初始状态4521341952603424ij一次交换24213419526034

24

i→j二次交换2421341952603452i←j三次交换242134193460

3452i→j[2421341934]45[6052]ij(a)一趟排序初始状态[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件1921243434455260(b)全部快速排序初始状态452134195260

privatevoidqkOne(intstart,intend,outintmid){intx,i,j;i=start;j=end;x=data[i];//将第一个值保存在x中

while(){while(i<j&&data[j]>=x)//自右向左扫描

;

if(i<j){;i++;}while(i<j&&data[i]<=x)//自左向右扫描