- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
常见排序的算法
插入排序是最简单最直观的排序算法了,它的依据是:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止。
??? 算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是
??? 1 + 2 + 3 + …… + N = O(N ^ 2)的复杂度。
?// 插入排序void InsertSort(int array[], int length){ int i, j, key;
for (i = 1; i length; i++) { key = array[i]; // 把i之前大于array[i]的数据向后移动 for (j = i - 1; j = 0 array[j] key; j--) { array[j + 1] = array[j]; } // 在合适位置安放当前元素 array[j + 1] = key; }} shell排序是对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了。
?// shell排序void ShellSort(int array[], int length){ int temp;
// 增量从数组长度的一半开始,每次减小一倍 for (int increment = length / 2; increment 0; increment /= 2) for (int i = increment; i length; ++i) { temp = array[i]; // 对一组增量为increment的元素进行插入排序 for (int j = i; j = increment; j -= increment) { // 把i之前大于array[i]的数据向后移动 if (temp array[j - increment]) { array[j] = array[j - increment]; } else { break; } } // 在合适位置安放当前元素 array[j] = temp; }} 堆的定义:
??? n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
??? (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)
??? 若将此序列所存储的向量R[1……n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
??? 堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素。
??? 堆排序算法的过程如下:1)得到当前序列的最小(大)的元素 2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面 3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质。重复上面的过程,直到序列调整完毕为止。
?// array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度void HeapAdjust(int array[], int i, int nLength){ int nChild, nTemp;
for (nTemp = array[i]; 2 * i + 1 nLength; i = nChild) { // 子结点的位置是 父结点位置 * 2 + 1
文档评论(0)