常见排序的算法.doc

  1. 1、本文档共9页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 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)

cgtk187 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档