数据结构课件

nullnull 重点：冒泡排序 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 、快速排序方法、堆排序方法、基数排序方法； 难点：快速排序方法、堆排序方法、基数排序方法、桶排序方法。 知识点： 概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内排方法比较第十章内部排序（8学时）概 述概 述排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 数据 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf (datalist): 它是待排序数据对象的有限集合。 主关键字(key): 数据对象有多个属性域, 即多个数据成员组成, 其中有一个属性域可用来区分对象, 作为排序依据，称为关键字。也称为排序码。null排序方法的稳定性: 如果在对象序列中有两 个对象r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 对象r[i]排在r[j]前面。如果在排序之后, 对象r[i]仍在对象r[j]的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的。 内排序与外排序: 内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。null排序的时间开销: 排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。内排序分类内排序分类依不同原则 插入排序、交换排序、选择排序、归并排序、和计数排序等。 依所须工作量 简单排序---时间复杂度o(n2) 先进排序方法---时间复杂度o(n logn) 基数排序---时间复杂度o(d.n)插入排序 (Insert Sorting)插入排序 (Insert Sorting)基本思想 当插入第i (i  1) 个对象时, 前面的V[0], V[1], …, V[i-1]已经排好序。这时, 用V[i]的排序码与V[i-1], V[i-2], …的排序码顺序进行比较, 找到插入位置即将V[i]插入, 原来位置上的对象向后顺移。 基本思想 每步将一个待排序的对象, 按其排序码大小, 插入到前面已经排好序的一组对象的适当位置上, 直到对象全部插入为止。直接插入排序 (Insert Sort)null直接插入排序过程0 1 2 3 4 5 temp i = 1i = 22125084925*16252125084925*16i = 32125084925*1625*2125084925*16nulli = 4i = 5null直接插入排序的算法 typedef int SortData; void InsertSort ( SortData V[ ], int n ) { //按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i < n; i++ ) { temp = V[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < V[j-1] ) V[j] = V[j-1]; else break; V[j] = temp; } } 算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法分析设待排序对象个数为 n, 则该算法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序码的初始排列有关。 最好情况下, 排序前对象已按排序码从小到大有序, 每趟只需与前面有序对象序列的最后一个对象比较1次, 移动2次对象, 总的排序 码比较次数为 n-1, 对象移动次数为 2(n-1)。null最坏情况下, 第 i 趟时第 i 个对象必须与前面 i 个对象都做排序码比较, 并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和对象移动次数RMN分别为 在平均情况下的排序码比较次数和对象移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。折半插入排序 (Binary Insertsort)折半插入排序 (Binary Insertsort)基本思想 设在顺序表中有一 个对象序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的对象。在插入V[i] 时, 利用折半搜索法寻找V[i] 的插入位置。折半插入排序的算法nulltypedef int SortData; void BinInsSort ( SortData V[ ], int n ) { SortData temp; int Left, Right; for ( int i = 1; i < n; i++) { Left = 0; Right = i-1; temp = V[i]; while ( Left <= Right ) { int mid = ( Left + Right )/2; if ( temp < V[mid] ) Right = mid - 1; else Left = mid + 1; } for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k];// 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 后移 V[Left] = temp; //插入 } }折半插入排序折半插入排序0 1 2 3 4 5 temp i = 1i = 20 1 2 3 4 5 temp52133i = 35521532144i = 4215388i = 52153161684421384516null折半搜索比顺序搜索查找快, 所以折半插入排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序列的初始排列无关, 仅依赖于对象个数。在插入第 i 个对象时, 需要经过 log2i +1 次排序码比较, 才能确定它应插入的位置。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半插入排序所进行的排序码比较次数为： 算法分析 null当 n 较大时, 总排序码比较次数比直接插入排序的最坏情况要好得多, 但比其最好情况要差。 在对象的初始排列已经按排序码排好序或接近有序时, 直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同, 依赖于对象的初始排列。 折半插入排序是一个稳定的排序方法。 折半插入排序的时间复杂度为o(n2)。希尔排序 (Shell Sort)希尔排序 (Shell Sort)基本思想设待排序对象序列有 n 个对象, 首先取一个整数 gap < n 作为间隔, 将全部对象分为 gap 个子序列, 所有距离为 gap 的对象放在同一个子序列中, 在每一个子序列中分别施行直接插入排序。然后缩小间隔 gap, 例如取 gap = gap/2，重复上述的子序列划分和排序工作。直到最后取 gap == 1, 将所有对象放在同一个序列中排序为止。 希尔排序方法又称为缩小增量排序。nulli = 3Gap = 30 1 2 3 4 5i = 2Gap = 22108254925*16i = 1Gap = 1希尔排序过程nulltypedef int SortData; void ShellSort ( SortData V[ ], int n ) { SortData temp; int gap = n / 2; //gap是间隔 while ( gap != 0 ) { //循环,直到gap为零 for ( int i = gap; i < n; i++) { temp = V[i]; //直接插入排序 for ( int j = i; j >= gap; j = j-gap ) if ( temp < V[j-gap] ) V[j] = V[j-gap]; else break; V[j] = temp; } gap = ( int ) ( gap / 2 ); } } 希尔排序的算法null开始时 gap 的值较大, 子序列中的对象较少, 排序速度较快; 随着排序进展, gap 值逐渐变小, 子序列中对象个数逐渐变多, 由于前面大多数对象已基本有序, 所以排序速度仍然很快。 Gap的取法有多种。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。 希尔排序所需的比较次数和移动次数约为n 1.3 当n趋于无穷时可减少到n(log2 n)2交换排序 ( Exchange Sort )交换排序 ( Exchange Sort )基本方法设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录地关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 基本思想是两两比较待排序对象的排序码,如发生逆序(即排列顺序与排序后的次序正好相反)，则交换之,直到所有对象都排好序为止。起泡排序 (Bubble Sort)null210825492516214925251608214925251608初 始 关 键 字第 一 趟 排 序第 四 趟 排 序第 二 趟 排 序第 三 趟 排 序214925251608第 五 趟 排 序起泡排序的过程null起泡排序的算法 typedef int SortData; void BubbleSort ( SortData V[ ], int n ) { int i = 1; int exchange = 1; while ( i < n && exchange ){ exchange = 0; //标志置为0,假定未交换 for ( int j = n-1; j >= i; j-- ) if ( V[j-1] > V[j] ) { //逆序 Swap ( V[j-1], V[j] ); //交换 exchange = 1; //标志置为1,有交换 } i++; } } 思考 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ：如何实现双起泡null 第i趟对待排序对象序列V[i-1],V[i],,V[n-1]进行排序, 结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1), 其它对象也都向排序的最终位置移动。。 最多做n-1趟起泡就能把所有对象排好序。 在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。 null最坏的情形是算法执行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序码比较, 执行 n-i 次对象交换。这样在最坏情形下总的排序码比较次数KCN和对象移动次数RMN为：起泡排序是一个稳定的排序方法。快速排序 (Quick Sort)快速排序 (Quick Sort)基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小,将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 右侧子序列中所有对象的排序码都大于基准对象的排序码null基准对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。 基准对象也称为枢轴（或支点）记录。nullQuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子序列 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); 将两个子序列 LeftList 和 RightList 合并为一个序列List; } }快速排序算法描述null快速排序的过程2108254925*16初始关键字08254925*162108254925*1608254925*1608254925*1608254925*1621prikey一次交换二次交换三次交换四次交换完成一趟排序ijijjinull08254925*1621完成一趟排序分别进行快速排序08254925*1621有序序列08254925*1621null 快速排序的算法 void QuickSort ( SqList &L, int low, int high ){ //在序列lowhigh 中递归地进行快速排序 if ( low < high) { int pivotloc= Partition (L, low, high); //划分 QuickSort ( L, low, pivotloc-1); //对左序列同样处理 QuickSort ( L, pivotloc+1, high); //对右序列同样处理 } }nullint Partition ( SqList &L, int low, int high ) { L.r[0]=L.r[low];//子表的第一个记录作基准对象 pivotkey = L.r[low].key; //基准对象关键字 While(low= pivotkey) --high; L.r[low] = L.r[high]; //小于基准对象的移到区间的左侧 While(lowdata[i] = arr[i]; H->CSize = n; //数组传送及当前堆大小 int CPos = (H->CSize-2)/2; //最后分支结点 while ( CPos >= 0 ) { //从下到上逐步扩大堆 FilterDown ( &H, CPos, H->CSize-1 ); CPos--; } }nullvoid FilterDown ( MinHeap *H, int start, int EndOfHeap ) { int i = start, j = 2*i+1; // j 是 i 的左子女 HeapData temp = H->data[i]; while ( j <= EndOfHeap ) { if ( j < EndOfHeap && //两子女中选小者 H->data[j] > H->data[j+1] ) j++; if ( temp <= H->data[j] ) break; else { H->data[i] = H->data[j]; i = j; j = 2*j+1; } //向下滑动 } H->data[i] = temp; }最小堆的向下调整算法null初始大顶堆的建立过程212525*491608012345i212525*164908025431i初始排序码集合i = 2 时的局部调整null212525*491608012345i492525*162108025431最大堆的向下调整算法最大堆的向下调整算法void FilterDown ( MaxHeap *H, int start, int EndOfHeap ) { int i = start; int j = 2*i+1; HeadData temp = H->data[i]; while ( j <= EndOfHeap ) { //最后位置 if ( j < EndOfHeap && H->data[j] < H->data[j+1] ) j = j+1; //选两子女的大者 if ( temp >= H->data[j] ) break; else { null H->data[i] = H->data[j]; //大子女上移 i = j; j = 2*j+1; //向下继续调整 } } H->data[i] = temp; //回放到合适位置 }将表转换成堆 for ( int i = ( H->CSize-2) / 2 ; i >= 0; i-- ) FilterDown ( H, i, H->CSize-1 ); 基于初始堆(大顶堆)进行堆排序基于初始堆(大顶堆)进行堆排序最大堆堆顶V[0]具有最大的排序码, 将V[0]与 V[n-1]对调, 把具有最大排序码的对象交换到最后, 再对前面的n-1个对象, 使用堆的调整算法FilterDown(0, n-2), 重新建立最大堆, 具有次最大排序码的对象又上浮到V[0]位置。 再对调V[0]和V[n-2],调用FilterDown(0, n-3), 对前n-2个对象重新调整，…。 如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，null492525*211608012345082525*16214902543149 25 21 25* 16 0808 25 21 25* 16 49交换 0 号与 5 号对象, 5 号对象就位初始最大堆基于初始堆进行堆排序null2525*082116490123451625*0825214902543125 25* 21 08 16 4916 25* 21 08 25 49交换 0 号与 4 号对象, 4 号对象就位从 0 号到 4 号 重新 调整为最大堆null25*1608212549012345081625*25214902543125* 16 21 08 25 4908 16 21 25* 25 49交换 0 号与 3 号对象, 3 号对象就位从 0 号到 3 号 重新 调整为最大堆null211625*082549012345081625*25214902543121 16 08 25* 25 4908 16 21 25* 25 49交换 0 号与 2 号对象, 2 号对象就位从 0 号到 2 号 重新 调整为最大堆null160825*212549012345081625*25214902543116 08 21 25* 25 4908 16 21 25* 25 49交换 0 号与 1 号对象, 1 号对象就位从 0 号到 1 号 重新 调整为最大堆null堆排序的算法 void HeapSort ( MaxHeap *H ) { //对表heap[0]到heap[n-1]进行排序, 使得表中 //各个对象按其排序码非递减有序。 for ( int i = ( H->CSize-2 ) / 2; i >= 0; i-- ) FilterDown ( H, i, H->CSize-1 ); //初始堆 for ( i = H->CSize-1; i >= 1; i--) { Swap ( H->data[0], H->data[i] ); //交换 FilterDown ( H, 0, i-1 ); //重建最大堆 } }null若设堆中有 n 个结点, 且 2k-1  n  2k, 则对应的完全二叉树有 k 层。在第 i 层上的结点数  2i (i = 0, 1, …, k-1)。 在第一个形成初始堆的 for 循环中对每一个非叶结点调用了 一次堆调整算法FilterDown( ), 因此该循环所用的计算时间为： 其中, i 是层序号, 2i 是第 i 层的最大结点数, (k-i-1)是第 i 层结点能够移动的最大距离。堆排序的算法分析null第二个for循环中调用了n-1次FilterDown( )算法, 该循环的计算时间为O(nlog2n)。因此, 堆排序的时间复杂性为O(nlog2n)。 该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。 堆排序是一个不稳定的排序方法。归并排序 (Merge Sort)归并排序 (Merge Sort)归并将两个或两个以上的有序表合并成一个新的有序表。 两路归并 (2-way merging)原始序列initList[ ]中两个有序表 initList[l] … initList[m]和initList[m+1] … initList[n]，它们可归并成一个有序表, 存于另一对象序列mergedList的 l … n 中。 null设变量 i 和 j 是表initList[l … m]和initList [m+1… n]的当前检测指针。k 是存放指针。 当 i 和 j 都在两个表的表长内变化时, 根据对应项的排序码的大小, 依次把排序码小的对象排放到新表 k 所指位置中； 当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。08 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightinitList08 16 21 25 25* 37 49 54 62 72 93 left rightkmergeListijnulltypedef int SortData; void merge ( SortData InitList[ ], SortData mergedList[ ], int left, int mid, int right ) { int i = left, j = mid+1, k = left; while ( i <= mid && j <= right ) //两两比较将较小的并入 if ( InitList[i] <= InitList[j] ) { mergedList [k] = InitList[i]; i++; k++; } else { mergedList [k] = InitList[j]; j++; k++; } while ( i <= mid ) { mergedList[k] = InitList[i]; i++; k++; }//将mid前剩余的并入 while ( j <= right ) { mergedList[k] = InitList[j]; j++; k++; } //将mid后剩余的并入 } 两路归并算法一趟归并排序的情形一趟归并排序的情形设initList[0]到initList[n-1]中 n 个对象已经分为一些长度为 len 的归并项, 将这些归并项两两归并, 归并成长度为 2len 的归并项, 结果放到mergedList[ ]中。 如果n不是2len的整数倍, 则一趟归并到最后,可能遇到两种情形： 剩下一个长度为len的归并项和另一个长度不足len的归并项, 可用merge算法将它们归并成一个长度小于 2len 的归并项。 只剩下一个归并项，其长度小于或等于 len, 将它直接抄到MergedList[ ]中。迭代的归并排序算法迭代的归并排序算法迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是： 假设初始对象序列有 n 个对象，首先把它看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，…，如此重复，最后得到一个长度为 n 的有序序列。null迭代的归并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16nullvoid MergePass ( SortData initList[ ], SortData mergedList[ ], int len ) { int i = 0; while (i+2*len-1 <= n-1) { merge( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; //循环两两归并 } if ( i+len <= n-1 ) merge( initList, mergedList, i, i+len-1, n-1); else for ( int j = i; j <= n-1; j++) mergedList [j] = initList[j]; } null归并排序的主算法 void MergeSort ( SortData initList[ ], int n ) { //按对象排序码非递减的顺序对表中对象排序 SortData tempList[n]; int len = 1; while ( len < n ) { MergePass ( initList, tempList, len ); len *= 2; MergePass ( tempList, initList, len ); len *= 2; } }null在迭代的归并排序算法中, 函数MergePass( ) 做一趟两路归并排序, 要调用merge ( )函数 n/(2*len)  O(n/len) 次, 函数MergeSort( )调用MergePass( )正好log2n 次,而每次merge( )要执行比较O(len)次, 所以算法总的时间复杂度为O(nlog2n)。 归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 归并排序是一个稳定的排序方法。null基数排序多关键字排序 例 对52张扑克牌按以下次序排序： 2<3<……<A<2<3<……<A< 2<3<……<A<2<3<……<A 两个关键字：花色（ <<< ） 面值（2<3<……