制作外贸网站模板,ppt在线制作免费,京东网上商城手机,网站建设 php jsp .net目录 8.1. 排序的基本概念 8.2. 插入排序 8.2.1. 直接插入排序 8.2.2. 折半插入排序 8.2.3. 希尔排序 8.3. 交换排序 8.3.1. 冒泡排序 8.3.2. 快速排序 8.4. 选择排序 8.4.1. 简单选择排序 8.4.2. 堆排序 8.5. 归并排序和基数排序 8.5.2. 基数排序 8.1. 排序的基本概念 排… 目录 8.1. 排序的基本概念 8.2. 插入排序 8.2.1. 直接插入排序 8.2.2. 折半插入排序 8.2.3. 希尔排序 8.3. 交换排序 8.3.1. 冒泡排序 8.3.2. 快速排序 8.4. 选择排序 8.4.1. 简单选择排序 8.4.2. 堆排序 8.5. 归并排序和基数排序 8.5.2. 基数排序 8.1. 排序的基本概念 排序重新排列表中的元素使表中元素满足按关键字有序的过程。 输入n个记录 对应的关键字为 。 输出:输入序列的一个重排 使得 。算法的稳定性若待排序表中有两个元素和其对应的关键字相同即 且在排序前在的前面若使用某一排序算法排序后仍然在的前面则称这个排序算法是稳定的否则称排序算法是不稳定的。排序算法的评价指标时间复杂度、空间复杂度、稳定性。 排序算法的分类内部排序 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。 外部排序 排序期间元素无法全部同时存在内存中必须在排序的过程中根据要求不断地在内、外存之间移动——关注如何使时间、空间复杂度更低如何使读/写磁盘次数更少。
8.2. 插入排序 8.2.1. 直接插入排序
算法思想每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中直到全部记录插入完成。
代码实现不带哨兵:
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){int i,j,temp;for(i1; in; i){if(A[i]A[i-1]){ //如果A[i]关键字小于前驱tempA[i]; for(ji-1; j0 A[j]temp; --j)A[j1]A[j]; //所有大于temp的元素都向后挪A[j1]temp;}}
}代码实现带哨兵
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[], int n){int i,j;for(i2; in; i){if(A[i]A[i-1]){A[0]A[i]; //复制为哨兵A[0]不放元素for(ji-1; A[0]A[j]; --j)A[j1]A[j];A[j1]A[0];}}
}算法效率分析 时间复杂度最好情况 O(n)最差情况O()平均情况 O()。空间复杂度O(1)。算法稳定性稳定。适用性适用于顺序存储和链式存储的线性表。
对链表进行插入排序代码实现
//对链表L进行插入排序
void InsertSort(LinkList L){LNode *pL-next, *pre;LNode *rp-next;p-nextNULL;pr;while(p!NULL){rp-next;preL;while(pre-next!NULL pre-next-datap-data)prepre-next;p-nextpre-next;pre-nextp;pr;}
}8.2.2. 折半插入排序
算法思路 每次将一个待排序的记录按其关键字大小使用折半查找找到前面子序列中应该插入的位置并插入直到全部记录插入完成。注意为了保证稳定性当查找到和插入元素关键字一样的元素时应该在这个元素的右半部分继续查找以确认位置。即当 A[mid] A[0] 时应继续在mid所指位置右边寻找插入位置。
代码实现
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n){ int i,j,low,high,mid;for(i2; in; i){A[0]A[i]; //将A[i]暂存到A[0]low1; highi-1;while(lowhigh){ //折半查找mid(lowhigh)/2;if(A[mid]A[0])highmid-1;elselowmid1;}for(ji-1; jhigh1; --j)A[j1]A[j];A[high1]A[0];}
}与直接插入排序相比比较关键字的次数减少了但是移动元素的次数没有变。时间复杂度仍为 O(n²)。
8.2.3. 希尔排序 算法思路先追求表中元素的部分有序再逐渐逼近全局有序以减小插入排序算法的时间复杂度。具体实施希尔排序:先将待排序表分割成若干形如 的“特殊”子表对各个子表分别进行直接插入排序。缩小增量d重复上述过程直到d1为止。
希尔排序代码实现
// 对A[]数组共n个元素进行希尔排序
void ShellSort(ElemType A[], int n){int d,i,j;for(dn/2; d1; dd/2){ //步长d递减for(id1; in; i){if(A[i]A[i-d]){A[0]A[i]; //A[0]做暂存单元不是哨兵for(ji-d; j0 A[0]A[j]; j-d)A[jd]A[j];A[jd]A[0];}}}
}算法效率分析 时间复杂度希尔排序时间复杂度依赖于增量序列的函数。最差情况O()n在某个特顶范围时可达O() 。空间复杂度O(1)算法稳定性不稳定。
8.3. 交换排序
8.3.1. 冒泡排序 算法思路从后往前或从前往后两两比较相邻元素的值若为逆序即 A [ i − 1 ] A [ i ]) 则交换它们直到序列比较完。如此重复最多 n-1 次冒泡就能将所有元素排好序。为保证稳定性关键字相同的元素不交换。
冒泡排序代码实现
// 交换a和b的值
void swap(int a, int b){int tempa;ab;btemp;
}// 对A[]数组共n个元素进行冒泡排序
void BubbleSort(int A[], int n){for(int i0; in-1; i){bool flag false; //标识本趟冒泡是否发生交换for(int jn-1; ji; j--){if(A[j-1]A[j]){swap(A[j-1],A[j]);flagtrue;}}if(flagfalse)return; //若本趟遍历没有发生交换说明已经有序}
}算法效率分析 时间复杂度最好情况O(n) 最差情况O()平均情况O()。空间复杂度O(1)。稳定性稳定。适用性冒泡排序可以用于顺序表、链表。
8.3.2. 快速排序 算法思路在待排序表 L [ 1... n ] 中任选一个元素 pivot 作为枢轴通常取首元素通过一趟排序将待排序表分为独立的两部分 L [ 1... k − 1 ] 和 L [ k − 1... n ] 。使得 L [ 1... k − 1 ] 中的所有元素小于 pivotL [ k − 1... n ]中的所有元素大于等于 pivot则 pivot 放在了其最终位置 L [ k ]上。重复此过程直到每部分内只有一个元素或空为止。快速排序是所有内部排序算法中性能最优的排序算法。在快速排序算法中每一趟都会将枢轴元素放到其最终位置上。可用来判断进行了几趟快速排序快速排序可以看作数组中n个元素组织成二叉树每趟处理的枢轴是二叉树的根节点递归调用的层数是二叉树的层数。
快速排序代码实现
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){int pivot A[low];while(lowhigh){while(lowhigh A[high]pivot)--high;A[low] A[high];while(lowhigh A[low]pivot) low;A[high] A[low];}A[low] pivot;return low;
} // 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){if(lowhigh){int pivotpos Partition(A, low, high); //划分QuickSort(A, low, pivotpos - 1);QuickSort(A, pivotpos 1, high);}
}算法效率分析 时间复杂度快速排序的时间复杂度 O ( n × 递 归 调 用 的 层 数 ) 。最好情况 O(),最差情况 O() 平均情况O()。空间复杂度快速排序的空间复杂度 O ( 递 归 调 用 的 层 数 ) O(递归调用的层数)O(递归调用的层数)。最好情况O()最差情况 O(n)平均情况 O()。
8.4. 选择排序
选择排序思想 每一趟在待排序元素中选取关键字最小或最大的元素加入有序子序列。
8.4.1. 简单选择排序 算法思路每一趟在待排序元素中选取关键字最小的元素与待排序元素中的第一个元素交换位置。
简单选择排序代码实现
// 交换a和b的值
void swap(int a, int b){int temp a;a b;b temp;
}// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n){for(int i0; in-1; i){ //一共进行n-1趟i指向待排序序列中第一个元素int min i;for(int ji1; jn; j){ //在A[i...n-1]中选择最小的元素if(A[j]A[min])min j;}if(min!i) swap(A[i], A[min]);}
}算法效率分析 时间复杂度无论待排序序列有序、逆序还是乱序都需要进行 n-1 次处理总共需要对比关键字(n−1)(n−2). . .1n( n−1) /2 次因此时间复杂度始终是O() 。空间复杂度O(1) 。稳定性不稳定。适用性适用于顺序存储和链式存储的线性表。
对链表进行简单选择排序
void selectSort(LinkList L){LNode *hL,*p,*q,*r,*s;LNULL;while(h!NULL){psh; qrNULL;while(p!NULL){if(p-datas-data){sp; rq;}qp; pp-next;}if(sh)hh-next;elser-nexts-next;s-nextL; Ls;}
}8.4.2. 堆排序 算法思路首先将存放在 L [ 1... n ] 中的n个元素建成初始堆由于堆本身的特点堆顶元素就是最大值。将堆顶元素与堆底元素交换这样待排序列的最大元素已经找到了排序后的位置。此时剩下的元素已不满足大根堆的性质堆被破坏将堆顶元素下坠使其继续保持大根堆的性质如此重复直到堆中仅剩一个元素为止。在顺序存储的完全二叉树中 非终端结点的编号 i ≤ [ n / 2 ]i 的左右孩子 2i 和 2i1i 的父节点[ i / 2 ]
堆排序代码实现
// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){for(int ilen/2; i0; i--) //从后往前调整所有非终端结点HeadAdjust(A, i, len);
}// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){A[0] A[k];for(int i2*k; ilen; i*2){ //沿k较大的子结点向下调整if(ilen A[i]A[i1]) i;if(A[0] A[i])break;else{A[k] A[i]; //将A[i]调整至双亲结点上ki; //修改k值以便继续向下筛选}}A[k] A[0]
}// 交换a和b的值
void swap(int a, int b){int temp a;a b;b temp;
}// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){BuildMaxHeap(A, len); //初始建立大根堆for(int ilen; i1; i--){ //n-1趟的交换和建堆过程swap(A[i], A[1]);HeadAdjust(A,1,i-1);}
}算法效率分析 时间复杂度O()。建堆时间 O(n) 之后进行 n-1 次向下调整操作每次调整时间复杂度为O()。空间复杂度O(1)。稳定性不稳定。 堆的插入对于大或小根堆要插入的元素放到表尾然后与父节点对比若新元素比父节点更大或小则将二者互换。新元素就这样一路“上升”直到无法继续上升为止。 堆的删除被删除的元素用堆底元素替换然后让该元素不断“下坠”直到无法下坠为止。
8.5. 归并排序和基数排序 归并Merge把两个或多个已经有序的序列合并成一个新的有序表。k路归并每选出一个元素需对比关键字k-1次。算法思想把待排序表看作 n 个有序的长度为1的子表然后两两合并得到 ⌈ n / 2 ⌉ 个长度为2或1的有序表……如此重复直到合并成一个长度为n的有序表为止。
代码实现
// 辅助数组B
int *B(int *)malloc(n*sizeof(int));// A[low,...,mid]A[mid1,...,high]各自有序将这两个部分归并
void Merge(int A[], int low, int mid, int high){int i,j,k;for(klow; khigh; k)B[k]A[k];for(ilow, jmid1, ki; imid j high; k){if(B[i]B[j])A[k]B[i];elseA[k]B[j];}while(imid)A[k]B[i];while(jhigh) A[k]B[j];
}// 递归操作
void MergeSort(int A[], int low, int high){if(lowhigh){int mid (lowhigh)/2;MergeSort(A, low, mid);MergeSort(A, mid1, high);Merge(A,low,mid,high); //归并}
}8.5.2. 基数排序
算法思想把整个关键字拆分为d位按照各个关键字位递增的次序比如个、十、百做d趟“分配”和“收集”若当前处理关键字位可能取得r个值则需要建立r个队列。分配顺序扫描各个元素根据当前处理的关键字位将元素插入相应的队列。一趟分配耗时O ( n ) O(n)O(n)。收集把各个队列中的结点依次出队并链接。一趟收集耗时O ( r ) O(r)O(r)。 基数排序擅长处理的问题 数据元素的关键字可以方便地拆分为d组且d较小。每组关键字的取值范围不大即r较小。数据元素个数n较大。算法效率分析算法效率分析 时间复杂度一共进行d趟分配收集一趟分配需要 O ( n )一趟收集需要 O(r) 时间复杂度为 O[ d ( n r ) ] 且与序列的初始状态无关.空间复杂度O(r)其中r为辅助队列数量。稳定性稳定。
未完待续
