中国计量学院数据结构第10章排序介绍.pptVIP

第十章 内部排序;10.1 概述;10.1 概 述;一、何为排序？;二、内部排序和外部排序;三、内部排序的方法;　基于不同的“扩大” 有序序列长度的方法，内部排序大致可分下列几种类型：;1. 插入类;2. 交换类;3. 选择类;4. 归并类; 10. 2 插 入 排 序;有序序列R[1..i-1];（一趟）插入排序分三步走：;直接插入排序（基于顺序查找）;一、直接插入排序;void InsertionSort ( SqList L ) { // 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; ++i ) if (L.r[i].key L.r[i-1].key) { } } // InsertionSort; 因为 R[1..i-1] 是一个有序序列，因此可以利用折半查找在R[1..i-1]中找出R[i]的插入位置。称这种排序为折半插入排序。;void BiInsertionSort ( SqList L ) { } // BiInsertionSort;low = 1; high = i-1; while (low=high) { };三、希尔排序(又称缩小增量排序);将序列分成若干子序列，对每个子序列进行插入排序。;增量为5;增量为3;void ShellInsert ( SqList L, int d ) { for ( i=d+1; i=n; ++i ) if ( L.r[i].key L.r[i-d].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-d; j0(L.r[0].keyL.r[j].key); j-=d) L.r[j+d] = L.r[j]; // 记录后移，查找插入位置 L.r[j+d] = L.r[0]; // 插入 } // if } // ShellInsert;void ShellSort (SqList L, int delta[], int t) { // 增量为delta[]的希尔排序 for (k=0; kt; ++t) ShellInsert(L, delta[k]); //一趟增量为delta[k]的插入排序 } // ShellSort; 首先对无序序列进行“划分”，之后将两个子序列“递归”进行快速排序。;int partition(int a[], int left, int right) //划分 { int low = left; int high = right; int key = a[low]; //第一个记录作为枢轴 while(low high) { while(low high a[high] = key) high--; a[low] = a[high]; //将比枢轴小的移到低端 while(low high a[low] = key) low++; a[high] = a[low]; //将比枢轴大的移到高端 } a[low] = key; //将枢轴放到合适的位置 return low; //将枢轴位置返回 };void Qsort(int a[], int left, int right) { int s; if (left = right) return; s=partition(a, left, right); Qsort(a, left, s-1); //排序前半部分 Qsort(a, s+1, right); //排序后半部分 };10.4 选 择 排 序;一、简单选择排序;void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; in; ++i) { } } // SelectSort;二、树形选择排序;三、堆排序;ri;堆排序;堆排序的步骤;所谓“筛选”指的是，对一棵左/右子树 均为堆的完全二叉树，“调整”根结点 使整个二叉树也成为一个堆。;98;建堆是一个从下往上进行“筛选”的过程。;　堆排序即是利用堆的特性对记录序列进行排