数据结构之树及图算法.ppt

设 n 个记录的序列为 { R1 , R2 , R3 , . . . , Rn };假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；;内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。;排序的时间复杂性;按照排序过程中所依据的原则的不同可以分类为:;思想: 利用有序表的插入操作进行排序;例，序列 49 38 65 97 76 13 27 ;void insertsort(ElemType R[],int n) //待排序元素用一个数组R表示，数组有n个元素 { for ( int i=1; in; i++) //i表示插入次数，共进行n-1次插入 { ElemType temp=R[i]; //把待排序元素赋给temp int j=i-1; while ((j=0) (tempR[j])) { R[j+1]=R[j]; j--; } // 顺序比较和移动 R[j+1]=temp;} } ;直接插入排序的效率分析 ;由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。;算法: void BinaryInsertSort(ElemType R[],int n) { for(int i=1; in; i++) //共进行n-1次插入 { int left=0,right=i-1;ElemType temp=R[i]; while(left=right) { int middle=(left+right)/2; //取中点 if(tempR[middle]) right=middle-1; //取左区间 else left=middle+1; } //取右区间 for(int j=i-1;j=left;j--) R[j+1]=R[j]; //元素后移空出插入位 R[left]=temp; } } ;折半插入效率分析;分析直接插入排序;思想: ;第二趟排序;希尔排序的算法 template class T void ShellSort (T Vector[], int arrSize ) { T temp; int gap = arrSize / 2; //gap是子序列间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i arrSize; i++) { temp = Vector[i]; //直接插入排序 for ( int j = i; j = gap; j -= gap ) if ( temp Vector[j-gap] ) Vector[j] = Vector[j-gap]; else break; Vector[j] = temp; } gap = ( int ) ( gap / 2 ); } } ;希尔排序效率分析;思想: 通过不断比较相邻元素大小，进行交换来实现排序。;例，序列 49 38 76 13 27;冒泡排序的算法实现。 void Bubblesort(ElemType R[],int n) { int flag=1; //当flag为0则停止排序 for (int i=1; in; i++) { //i表示趟数，最多n-1趟 flag=0;//开始时元素未交换 for (int j=n-1; j=i; j--) if (R[j]R[j-1]) { //发生逆序 ElemType t=R[j]; R[j]=R[j-1]; R[j-1]=t;flag=1; } //交换，并标记发生了交换 if(flag==0)return; }