2022年各种排序算法小结[linxingke.docx
精品学习资源各种排序算法小结排序算法是一种基本并且常用地算法.由于实际工作中处理地数量庞大,所以排序算法 对算法本身地速度要求很高. 而一般 我 们 所 谓 地 算 法 地 性 能 主 要 是 指 算 法 地 复 杂 度 , 一 般 用 O 方 法 来 表 示 . 在 后 面 我 将 给 出 详 细 地 说 明 .对于排序地算法我想先做一点简洁地介绍,也是给这篇文章理一个提纲. 我将根据算法地复杂度 ,从简洁到难来分析算法 . 第一部分是简洁排序算法,后面你将看到他们地共同点是算法复杂度为ON*N>< 由于没有使用word, 所以无法打出上标和下标) . 其次部分是高级排序算法 ,复杂度为 OLog2N>>. 这里我们只介绍一种算法.另外仍有几种算法由于涉及树与堆地概念, 所以这里不于争论. 第三部分类似动脑筋.这里地两种算法并不是最好地<甚至有最慢地) ,但是算法本身比较奇妙,值得参考<编程地角度) .同时也可以让我们从另外地角度来熟悉这个问题. 第四部分是我送给大家地一个餐后地甜点一个基于模板 地 通 用 快 速 排 序 . 由 于 是 模 板 函 数 可 以 对 任 何 数 据 类 型 排 序 < 抱 歉 , 里 面 使 用 了 一 些 论 坛 专 家 地 呢 称 ) .现在,让我们开始吧: 一、简单排序算法由 于 程 序 比 较 简 单 , 所 以 没 有 加 什 么 注 释 . 所 有 地 程 序 都 给 出 了 完 整 地 运 行 代 码 , 并 在 我 地 VC 环 境下 运 行 通 过 . 因 为 没 有 涉 及 MFC 和 WINDOWS 地 内 容 , 所 以 在 BORLAND C+ 地 平 台 上 应 该 也 不 会 有 什 么问 题 地 . 在 代 码 地 后 面 给 出 了 运 行 过 程 示 意 , 希 望 对 理 解 有 帮 助 .1.冒泡法: 这 是 最 原 始 , 也 是 众 所 周 知 地 最 慢 地 算 法 了 . 他 地 名 字 地 由 来 因 为 它 地 工 作 看 来 象 是 冒 泡 :#include<iostream.h>voidBubbleSortint*pData,intCount>intiTemp;forinti=1;i<Count;i+>forintj=Count-1;j>=i;j->ifpDataj<pDataj-1>iTemp=pDataj-1;pDataj-1=pDataj;pDataj=iTemp;voidmain>intdata=10,9,8,7,6,5,4;BubbleSortdata,7>forinti=0;i<7;i+>cout<<datai<<"";cout<<"n";倒序第一轮第二轮:最糟10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,87,10,9,8->7,10,8,9->7,8,10,9情交换交换2况>3次>次>第一轮:7,8,10,9->7,8,9,10交换1次>循环次数:6次交换次数:6次其他:第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9交换2次>第二轮:7,8,10,9->7,8,10,9->7,8,10,9交换0次>第一轮:7,8,10,9->7,8,9,10交换1次>循环次数:6次交换次数:3次上面我们给出了程序段,现在我们分析它:这里 ,影响我们算法性能地主要部分是循环和交换, 明显 ,次数越多 ,性能就越差 .从上面地程序我们可以看出循环地次数是固定地,为 1+2+.+n-1. 写成公式就是 1/2*n-1>*n.现在留意 ,我们给出O 方法地定义:如存在一常量 K 和起点 n0,使当 n>=n0 时,有 fn><=K*gn>, 就 fn> = Ogn>>.< 呵呵,不要说没 学好数学呀 ,对于编程数学是非常重要地!) 现在我们来看 1/2*n-1>*n, 当 K=1/2,n0=1,gn>=n*n时,1/2*n-1>*n<=1/2*n*n=K*gn>.所以 fn> =Ogn>>=On*n>. 所以我们程序循环地复杂度为On*n>. 再看交换 .从程序后面所跟地表可以看到,两种情形地循环相同 ,交换不同 .其实交换本身同数据源地 有序程度有极大地关系 ,当数据处于倒序地情形时,交换次数同循环一样 <每次循环判定都会交换), 复杂度为 On*n>. 当数据为正序 ,将不会有交换 .复杂度为O0>. 乱序时处于中间状态 .正是由于这样地缘由,我们通常都是通过循环次数来对比算欢迎下载精品学习资源法.2.交 换 法地程序最清交晰简 单 ,每 次 用当前换地元素一一地 同 其法后地元素比较: 并 交 换 .#include<iostream.h>voidExchangeSortint*pData,intCount>intiTemp;forinti=0;i<Count-1;i+>forintj=i+1;j<Count;j+>ifpDataj<pDatai>iTemp=pDatai;pDatai=pDataj; pDataj=iTemp;voidmain>intdata=10,9,8,7,6,5,4;ExchangeSortdata,7>;forinti=0;i<7;i+>cout<<datai<<"";cout<<"n";倒序最糟情况>第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8交换3次>第二轮:7,10,9,8->7,9,10,8->7,8,10,9交换2次>第一轮:7,8,10,9->7,8,9,10交换1次>循环次数:6次交其换次数他:6次:第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9交换1次>第二轮:7,10,8,9->7,8,10,9->7,8,10,9交换1次>第一轮:7,8,10,9->7,8,9,10交换1次>循环次数:6次交换次数:3次从运行地表格来看 ,交换几乎和冒泡一样糟 .事实的确如此 .循环次数和冒泡一样 也是 1/2*n-1>*n, 所以算法地复杂度仍旧是On*n>. 由于我们无法给出全部地情形 ,所以 只能直接告知大家他们在交换上面也是一样地糟糕 <在某些情形下稍好 ,在某些情况下稍差).3.选择法: 现在我们最终可以看到一点期望:挑选法 ,这种方法提高了一点性能 <某些情形下) 这种方法类似我们人为地排序习惯:从数 据 中#include选择 最小 地同 第 一个 值交 换 , 在 从省下 地部 分中选择最 小地 与第 二 个交换, 这样往 复 下 去 .<iostream.h>voidSelectSortint*pData,intCount>int intforinti=0;iTemp iPosi<Count-1;i+>iTemp=pDatai;forintiPosj=i+1;=j<Counti;j+>ifpDataj<iTemp>iTempiPos=pDatajj;pDataiPos=pDatai;欢迎下载精品学习资源pDatai=iTemp;voidmain>intdata=10,9,8,7,6,5,4;SelectSortdata,7>;forinti=0;i<7;i+>cout<<datai<<"";cout<<"n";倒序最糟情况> 第 一 轮 : 10,9,8,7->iTemp=9>10,9,8,7->iTemp=8>10,9,8,7->iTemp=7>7,9,8,10 交 换 1 次 > 第 二 轮 : 7,9,8,10->7,9,8,10iTemp=8>->iTemp=8>7,8,9,10交 换 1次 > 第 一 轮 : 7,8,9,10->iTemp=9>7,8,9,10交 换 0次 >循环次数:6次交换次数:2次其他: 第 一 轮 : 8,10,7,9->iTemp=8>8,10,7,9->iTemp=7>8,10,7,9->iTemp=7>7,10,8,9 交 换 1 次 > 第 二 轮 : 7,10,8,9->iTemp=8>7,10,8,9->iTemp=8>7,8,10,9交 换 1次 > 第 一 轮 : 7,8,10,9->iTemp=9>7,8,9,10交 换 1次 >循环次数:6次交换次数:3次遗憾地是算法需要地循环次数依旧是1/2*n-1>*n. 所以算法复杂度为On*n>. 我们来看他地交换.由于每次外层循环只产生 一次交换 <只有一个最小值).所以 fn><=n 所以我们有fn>=On>. 所以 ,在数据较乱地时候, 可以削减肯定地交换次数.4.插入法:插 入 法 较 为 复 杂 , 它 地 基 本 工 作 原 理 是 抽 出 牌 , 在 前 面 地 牌 中 寻 找 相 应 地 位 置 插 入 , 然 后 继 续 下 一 张#include<iostream.h>voidInsertSortint*pData,intCount>intiTemp;intiPos;forinti=1;i<Count;i+>iTemp=pDatai;iPos=i-1;whileiPos>=0>&&iTemp<pDataiPos>>pDataiPos+1=pDataiPos;iPos-;pDataiPos+1=iTemp;voidmain>intInsertSortdata,7>data=10,9,8,7,6,5,4;forcout<<"n"inti=0 cout<<datai<<";i<7";i+>;倒序最糟情况>第一轮:10,9,8,7->9,10,8,7交换1次>循环1次>第二轮:9,10,8,7->8,9,10,7交换1次>循环2次>第一轮:8,9,10,7->7,8,9,10交换1次>循环3次>循环次数:6次交换次数:3次其第一轮:8,10,7,9->8,10,7,9交他换0次>循环1次:>第二轮:8,10,7,9->7,8,10,9交换1次>循环2次>第一轮:7,8,10,9->7,8,9,10交换1次>循环1次>欢迎下载精品学习资源循环次数:4次交换次数:2次上面结尾地行为分析事实上造成了一种假象,让我们认为这种算法是简洁算法中最好地,其实不是 , 由于其循环次数虽然并不固定,我们仍可以使用 O 方法.从上面地结果可以看出 ,循环地次数 fn><= 1/2*n*n-1><=1/2*n*n.所以其复杂度仍为On*n>< 这里说明一下 ,其实假如不是为了展现这些简洁排序地不同 ,交换次数仍旧可以这样推导).现在看交换 ,从外观上看 ,交换次数是 On>< 推导类似 挑选法) ,但我们每次要进行与内层循环相同次数地=操作 .正常地一次交换我们需要三次= 而这里显然多了一些,所以我们浪费了时间. 最终,我个人认为 , 在 简 单 排 序 算 法 中 , 选 择 法 是 最 好 地 . 二 、 高 级 排 序 算 法 : 高级排序算法中我们将只介绍这一种 ,同时也是目前我所知道 <我看过地资料中)地最快地 . 它地工作看起来仍旧象一个二叉树.第一我们挑选一个中间值 middle 程序中我们使用数组中间值 ,然后 把比它小地放在左边 ,大地放在右边 <详细地实现是从两 边 找 , 找 到 一 对 后 交 换 ) . 然 后 对 两 边 分 别 使 用 这 个 过 程 < 最 容 易 地 方 法 递 归 ) .1.快速排序:#include<iostream.h>voidrunint*pData,intleft,intright>inti,j;intmiddle,iTemp;i=left;j=right;middle=pDataleft+right>/2;/求中间值ifi<=j>/找到j-了一对;值/交换iTemp=pDatai;pDatai=pDatajpDataj=iTemp;i+;j-;/如果两边扫描地下标交错,就停止<完成一次)do whilepDatai<middle>&&i<right>>/从左 扫描大 于中值地 数i+;whilepDataj>middle>&&j>left>>/从右扫描大于中值地数whilei<=j>;/当左边部分有ifleft<j>/当右边部分有递归左半边递归右半;边;值left<j>,欢迎下载精品学习资源ifright>i>runpData,left,j>值right>i>, runpData,i,right>欢迎下载精品学习资源voidQuickSortint*pData,intCount>runpData,0,Count-1>;voidmain>intdata=10,9,8,7,6,5,4;QuickSortdata,7>;forinti=0;i<7;i+>cout<<datai<<"";cout<<"n";这 里 我 没 有 给 出 行 为 地 分 析 , 因 为 这 个 很 简 单 , 我 们 直 接 来 分 析 算 法 : 首 先 我 们 考 虑 最 理 想 地 情 况1. 数 组 地 大 小 是 2地 幂 , 这 样 分 下 去 始 终 可 以 被 2整 除 . 假 设 为 2地 k次 方 , 即 k=log2n>.2. 每 次我 们选 择地 值刚好 是中 间值 ,这 样,数组 才可 以被 等分 .第一层递归,循环n次,第二层循环2*n/2>.所以共有n+2n/2>+4n/4>+.+n*n/n>=n+n+n+. +n=k*n=log2n>*n欢迎下载精品学习资源所以算法复杂度为Olog2n>*n> 其他地情形只会比这种情形差,最差地情形是每次挑选到地middle 都是最小值或最大值 ,那么他将变 成交换法 <由于使用了递归,情形更糟) .但是你认为这种情形发生地几率有多大?呵呵,你完全 不必担忧这个问题.实践证明 ,大多数地情形 ,快速排序总是最好地 . 假如你担忧这个问题 ,你可以使用堆排序 ,这是一种稳固地 Olog2n>*n> 算法,但是通常情形下速度要慢于快速排序<因为要重组堆). 三、其他排序1.双向冒泡: 通常地冒泡是单向地,而这里是双向地 ,也就是说仍要进行反向地工作. 代码看起来复杂 ,认真理一下就明白了 ,是一个来回震荡地方式 . 写这段代码地作者认为这样可以在冒泡地基础上削减一些交换<我不这么认为 ,或许我错了) . 反正我认为这是一段有趣地代码,值得一看.#include voidBubble2Sortint*pData,int<iostream.h>Count>intiTemp;intleft=intright=Count intt1-1;do/正向forinti=right;地i>=left部;分i->ifpDatai<pDatai-1>iTemp=pDatai;pDataipDatai-1=pDatai-1iTemp;t=i;left=t+1;/反向地部分fori=left;i<right+1;i+>ifpDatai<pDatai-1>iTemp pDataipDatai-1=pDatai pDatai-1iTemp;t=i;right=t-1;whileleft<=right>;voidmain>intdata=10,9,8,7,6,5,4;Bubble2Sortdata,7>;forinti=0;i<7;i+>cout<<datai<<"";cout<<"n";2.SHELL这个排序特别复杂, 看了程序就知道了. 第一需要一个递减地步长排,这里我们使用地是9、5、3、1<最终地步长必需是序1). 工作 原理是 第一对 相 隔#include void9-1 个元素 地 全部 内容 排序, 然后再 使用同 样地 方法对 相隔ShellSortint*pData,int5-1个元素 地排序, 以次 类推.<iostream.h>Count>intstep4;step0=9;step1=5;step2=3;step3=1;int intiTemp k,s,w;欢迎下载精品学习资源forinti=0;i<4;i+>k=stepi;s=-k;forintj=k;j<Count;j+>iTemp=pDataj;w=j-k; /求 上step个 元 素 地 下 标ifs=0>s=-k;s+;pDatas=iTemp;whileiTemp<pDataw>&&w>=0>&&w<=Count>> pDataw+k=pDataw;w=w-k;pDataw+k=iTemp;voidmain>intdata=10,9,8,7,6,5,4,3,2,1,-10,-1;ShellSortdata,12>;forinti=0;i<12;i+>cout<<datai<<"";cout<<"n";呵呵,程序看起来有些头疼.不过也不是很难 ,把 s=0 地块去掉就轻松多了,这里是防止使用0 步长造成程序反常而写地代码.这个代码我认为很值得一看. 这个算法地得名是由于其创造者地名字D.L.SHELL. 依照参考资料上地说法:“由于复杂地数学缘由 防止使用 2 地幂次步长 ,它能降低算法效率 .”另外算法地复杂度为n 地 1.2 次幂.同样由于特别复杂并“超出本书讨论 范 围 ” 地 原 因 < 我 也 不 知 道 过 程 ) , 我 们 只 有 结 果 了 . 四 、 基 于 模 板 地 通 用 排 序 : 这 个 程 序 我 想 就 没 有 分 析 地 必 要 了 , 大 家 看 一 下 就 可 以 了 . 不 明 白 可 以 在 论 坛 上 问 . MyData.h文件/classCMyDatapublic:CMyDataintIndex,char*strData>;CMyData>;virtualCMyData>;intm_iIndex;intGetDataSize>returnm_iDataSize;constchar*GetData>returnm_strDatamember;/这里重载了操作符:CMyData&operator=CMyData&SrcData>;booloperator<CMyData&data>;booloperator>CMyData&data>;private:char*m_strDatamember;intm_iDataSize;/;MyData.cpp/文件CMyData:CMyData>:m_iIndex0>,m_iDataSize0>,欢迎下载精品学习资源m_strDatamemberNULL>CMyData:CMyData>ifm_strDatamember.=NULL>deletem_strDatamember=m_strDatamemberNULL;CMyData:CMyDataintIndex,char*strData>:m_iIndexIndex>,m_iDataSize0>,m_strDatamemberNULL>m_iDataSize=strlenstrData>;m_strDatamember=newcharm_iDataSize+1;strcpym_strDatamember,strData>;CMyData&CMyData:operator=CMyData&SrcData>m_iIndex=SrcData.m_iIndex;m_iDataSizem_strDatamember=SrcData.GetDataSize>;newcharm_iDataSize+1;strcpym_strDatamember,SrcData.GetData>>;return*this;boolCMyData:operator<CMyData&data>returnm_iIndex<data.m_iIndex;boolCMyData:operator>CMyData&data>returnm_iIndex>data.m_iIndex;/主程序部分#include<iostream.h>#include"MyData.h"template<classT>voidrunT*pData,intleft,intright>inti,j;Ti=middle,iTempleft;j=right;操作符函数中间值值于地中数值i+地;数;/ 下 面 地 比 较 都 调 用 我 们 重 载 地middle=pDataleft+right>/2;/求dowhilepDatai<middle>&&i<right>>/从左扫描大于中whilepDataj>middle>&&j>left>>/从右扫描大j-ifi<=j>/找到了一对值/iTemp=交pDatai换;pDatai pDataj=i+pDataj iTemp;j-;whilei<=j>;/如果两边扫描地下标交错,就停止<完成一次)/当左边部分有值left<j>,递归左半边ifleft<j>欢迎下载精品学习资源runpData,left,j>;/当右边部分有值right>i>,递归右半边ifright>i>runpData,i,right>;template<classT> voidQuickSortT*pData,intCount>runpData,0,Count-1>;voidmain>CMyDatadata= CMyData8,"xulion">, CMyData7,"sanzoo">,CMyData6,"wangjun">, CMyData5,"VCKBASE">,CMyData4,"jacky2000">, CMyData3,"cwally">, CMyData2,"VCUSER">,CMyData1,"isdong">;QuickSortdata,8>;forinti=0;i<8;i+> cout<<datai.m_iIndex<<""<<datai.GetData><<"n";cout<<"n";欢迎下载