数据结构第10章资料.ppt

第10章 排序;10.1 排序的基本概念 ;;10.2插入排序 ;算法如下： void InsertSort (DataType a[], int n) //用直接插入法对a[0]--a[n-1]排序 { int i, j; DataType temp; for(i=0; in-1; i++) { temp = a[i+1]; j = i; while(j -1 temp.key a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } };算法分析:;{64};2.希尔(shell)排序(又称缩小增量排序); 算法如下： void ShellSort (DataType a[], int n, int d[], int numOfD) //用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值 { int i, j, k, m, span; DataType temp; ? for(m = 0; m numOfD; m++) //共numOfD次循环 { span = d[m]; //取本次的增量值 for(k = 0; k span; k++) //共span个小组 { //组内是直接插入排序，区别是每次不是增1而是增span for(i = k; i n-span; i = i+span) { temp = a[i+span]; j = i; while(j -1 temp.key a[j].key) { a[j+span] = a[j]; j = j-span; } a[j+span] = temp; } } } };65;10.3 选择排序 ;1.直接选择排序;算法如下： void SelectSort(DataType a[], int n) { int i, j, small; DataType temp; ? for(i = 0; i n-1; i++) { small = i; //设第i个数据元素关键字最小 for(j = i+1; j n; j++) //寻找关键字最小的数据元素 if(a[j].key a[small].key) small=j; //记住最小元素的下标 if(small != i) //当最小元素的下标不为i时交换位置 { temp = a[i]; a[i] = a[small]; a[small] = temp; } } };64;算法分析 时间效率： O(n2)——虽移动次数较少，但比较次数仍多。 空间效率：O(1)——仅用到若干个临时变量。 算法的稳定性：不稳定;2.堆排序 ;10;二、 创建堆 ;void CreatHeap (DataType a[], int n, int h) { int i, j, flag; DataType temp; ? i = h; // i为要建堆的二叉树根结点下标 j = 2*i+1; // j为i的左孩子结点的下标 temp = a[i]; flag = 0; ? while(j n flag !=