IT培训机构|91免费精品视频|专注编程培训|91免费精品|软件开发培训_91免费国产视频_华清远见教育

當前位置: > 華清遠見教育科技集團 > 嵌入式學習 > 講師博文 > 算法基礎(一)
算法基礎(一)
時間:2016-12-14作者:華清遠見

排序:

我們為何要研究排序?
        1. 有時候應用程序本身需要對信息進行排序。
        2. 許多程序把排序程序作為關鍵子程序。
        3. 排序是我們學習編程的基本的訓練,對于程序的優化有很重要的作用。

我們之前已經學過簡單排序法和冒泡排序法。接下來我們介紹一下插入排序和合并排序。
        1. 插入排序
        輸入:n個數(a 1 ,a 2 ,.....a n)
        輸出:輸入序列的一個排序(b1,b2....bn),使得b1 <= b2 <=....<=bn

插入排序的機制和打牌時整理手中的牌做法差不多。摸牌的時候,需要將摸到的牌插入到手中一把牌中的正確的位置上。為了要找到這張牌的位置,我們需要將它與手中每張牌從右到左進行比較。無論何時,左手中的牌都是排好序的。

這個算法中,所有的元素都是原地排序(sorted in place),就意味著這些數字就是在數組本身中重新排序的。

算法如下:
        1、數組被分為兩部分,一部分為排好序的,一部分為未排好序。
        2、選取一個key值,就是將要排序的元素,通過比較方式,將其插入到已排好順序的部分。
        3、循環處理,直到該數組全部排好序。

偽代碼:

代碼(c語言實現):

//a 是一個數組,size_a是這個數組的元素個數
        void insertion_sort( int * a, int size_a){

                int i,j;
                int key = 0 ;

                for (j = 1 ;j < size_a;j ++ ){

                        key = a[j];
                        i = j - 1 ;
                        while (i > = 0 << a[i] > key){
                                a[i + 1 ] = a[i];
                                i = i - 1 ;
                        }
                        a[i + 1 ] = key;
                }

                return ;
        }

插入排序算法的時間復雜度是O(n 2 ) 。當然算法的執行速度,和n的大小(輸入規模)以及樣本的結構有關系?紤]壞的情況,就是輸入的n個數為逆序排列,此時插入排序算法,隨著n的增大,運算時間的增長與 n 2 同數量級。

2.分治法策略
        很多算法在結構上是遞歸的:為了解決一個給定的問題,算法要一次或多次地遞歸調用其自身來解決相關的子問題。這些算法通常采用分治策略:將原問題劃分為n個規模較小而結構與原問題相似的子問題;遞歸地解決這些子問題,然后再合并其結果,就得到原問題的解。         分治模式在每一層遞歸上都有三個步驟:

分解(divide):講原有問題分解成為一系列子問題;
        解決(Conquer):遞歸地解各子問題。若子問題足夠小,則直接求解;
        合并(Combine):講子問題的結果合并成原問題的解。

合并排序
        合并排序的關鍵步驟在于合并步驟中的合并兩個已排序子序列。為做合并,引入一個輔助過程merge(a,p,q,r),其中a是一個數組,p,q和r是下標,滿足p <=q< r。該過程的子數組 a[p...q]和a[q+1.... r] 都已排好序,并將他們合并成一個已排好的子數組代替當前子數組a[p.....r]。

merge過程的代價是O(n)。其中n = r - p + 1是待合并的元素個數。
        以下為合并的偽代碼:

為了能檢查兩個子數組是否是空,其想法是在每一個數組底部放一個“哨兵”,它包含了特殊值,用于簡化代碼。

具體來說,merge過程是這樣工作的:第一行計算子數組a[p...q]的長度n1,第二行計算子數組a[q+1...r]的長度n2.在第三行中,創建了數組L和R,長度各位n1 +1,n2 + 1.第四到第五行中的for循環將子數組a[p...q]復制到L[1....n1]中去。 第六到第七行中的for循環將子數組a[q+1...r]復制到R[1....n2]中去。第八九行講哨兵置于L和R的末尾。第十到第十七行,是合并的具體過程。通過比較,將兩子數組按照從小到大的方式合并,存入數組A中。

c語言描述如下所示

void merge( int * a, int p, int q, int r){

                int n1 = q - p + 1 ;
                int n2 = r - q;
                //為左數組和右數組分配空間,為max預留空間。
                //max為哨兵,標志數組的結束。
                int * L = ( int * )malloc( sizeof ( int ) * (n1 + 1 ));
                int * R = ( int * )malloc( sizeof ( int ) * (n2 + 1 ));

                for ( int i = 0 ;i < n1;i ++ ){
                        L[i] = a[p + i];
           &nnbsp;    }

                for ( int i = 0 ;i < n2;i ++ ){
                        R[i] = a[q + i + 1 ];
                }

                L[n1] = MAX;
                R[n2] = MAX;
                //從小到大將左數組和友數組合并。
                int i,j,k;
                for (i = 0 ,j = 0 ,k = p;k < = r;k ++ ){
                        if (L[i] < = R[j]){
                                a[k] = L[i];
                                i ++ ;
                        } else {
                                a[k] = R[j];
                                j ++ ;
                        }
                }
                free(L);
                L = NULL;
                free(R);
                R = NULL;
                return ;
        }

合并merge過程就可以作為合并排序中的一個子程序來使用。偽代碼如下:

c語言描述過程為:

void merge_sort( int * a, int p, int r){
                int q = 0 ;

                if (p < r){
                         q= (p + r) / 2 ;
                        merge_sort(a,p,q);
                      &nbsnbsp; merge_sort(a,q + 1 ,r);
                        merge(a,p,q,r);
                }
                return ;
        }

合并程序的具體圖示:

關于分治法排序的簡要分析:

我們將一個規模為n的問題,拆分成n個規模為1的子問題。拆分的過程經歷了 lg n + 1層,在合并時,每一層的問題規模為n,則總代價為O (n * lg n + n ) ,忽略低階項和常數項,因此合并排序法的時間復雜度為O(n lg n )。

接下來會介紹一下堆排序和快速排序。以上的所有排序方法,都是比較排序。也就是說,他們通過對數組元素比較來實現排序。比較排序法是有極限的,從壞的輸入情況,比較排序法的時間復雜度是 O(n lg n )。我們介紹的合并排序以及快速排序,都是漸進優的比較排序方式。我們還會介紹可以突破比較排序極限的排序方式——計數排序。

發表評論
評論列表(網友評論僅供網友表達個人看法,并不表明本站同意其觀點或證實其描述)
主站蜘蛛池模板: 上海喷涂厂|上海喷漆厂|粉末喷涂|平湖喷涂厂|平湖喷漆厂-平湖华梦金属科技有限公司 | 永磁变频空压机-无油空压机-螺杆式空压机热能回收-空压机配套-空压机合同能源管理-维修保养-北京斯特兰压缩机有限公司 | 一体化净水器设备-浸没式膜水处理设备-智慧水务-超滤膜-模块化净水设备-浙江华晨环保有限公司 | 开关柜无线测温_电缆接头测温系统_六氟化硫sf6气体泄漏报警监测_卫星同步时钟-山东正瑞电子有限公司 | 喷涂机器人|自动喷涂生产线|自动喷涂设备|自动化生产线-深圳市荣德机器人科技有限公司 | 山东优科机械设备有限公司,养鸡设备,湿帘设备,通风降温加湿设备,山东养鸡设备,山东湿帘设备 | 上海增晨贸易有限公司-PC端| 强德防盗门-防盗门厂家-中国防盗门十大品牌-强德门业 - 浙江臻品工贸有限公司 | 植绒布工厂,植绒布现货批发-深圳市金峰盛植绒制品有限公司 | 制沙机,反击式破碎机,重锤破碎机,泥石分离机,圆锥破碎机厂家-昆明德鑫机械 | 山东啤酒箱塑料提手_注塑产品加工_手提绳厂家-淄博浩晨包装制品有限公司 | 太阳能光伏发电_太阳能热水器_空气能热水器_直饮净水器_深圳市大兴节能环保科技有限公司 | 宁波公司注册_宁波注册公司_宁波代理记账_宁波做内账|安隆会计专业服务机构 | -盐城市精工阀门有限公司 | 青砖厂家,青瓦价格-河北祥庆烧结瓦有限公司 | 淄博润裕机械设备有限公司-搅拌器,搅拌桨叶,反应釜,机械密封,化工搅拌 | 陕西筱润智能科技有限公司 干部人事智能档案柜 智能密集架 智能档案柜 部队选层文件智能柜 智能枪弹柜 财务智能档案柜 边防武警智能密集架 医院智能档案柜 部队选层文件智能柜智能枪弹柜 学校医院文件柜 企事业单位公检法智能文件柜 生产厂家-筱润智能科技有限公司 RFID射频智能密集架 全自动智能选层档案柜 智能密保柜 枪柜部队营房营具床桌椅办公家具 办公用品档案盒设备货架 全自动智能选层柜生产厂家-筱润智能科技有限公司 | 景县泉兴永塔业有限公司-广播电视塔、通信塔、电力塔、交通设施、监控杆塔、气象塔、森林防火瞭望塔、避雷塔、烟筒塔、训练塔 | 南京货架|仓库货架|货架公司|仓储货架工厂批发定做-南京苏正科技实业公司 | 亿企商贸-亿万企业的商务贸易平台-B2B企业产品发布供求信息平台,一带一路中国企业及产品展示平台,免费企业智能自助建站网络营销推广平台,打造B2B企业黄页产品信息发布推广专业综合电子商务平台! | 无尘布_乳胶手套_防静电手环_口罩-苏州迈思德超净科技有限公司 | 郑州课桌椅|学生课桌椅|升降课桌椅批发|厂家|价格-新科教育用品 郑州井盖雨水篦子厂家-建联建材 | 宿迁市华泰交通设施有限公司,上海第四代路名牌,天津仿罗马柱路名牌,标准路名牌,路名牌灯箱,公交站台,户外广告灯箱, 交通标志牌,社区阅报栏 | 洁净无尘棚_万级洁净棚_昆山风淋室-昆山市海兴净化设备 | 泰安led显示屏-泰安户外裸眼3D显示屏-扩声系统-舞台灯光机械-电子屏-肥城宁阳新泰东平-泰安市奇美特电子有限公司 | 河南反渗透设备,河南纯净水设备,河南软化水设备,郑州EDI超纯水设备,郑州水处理设备厂家_河南江宇环保科技有限公司 | 氢能-燃料电池-电堆-中国氢能与燃料电池网企业最佳宣传推广平台 轻质隔墙板厂家-加气隔墙板_grc轻质隔墙板_空心实心复合隔墙板_水泥混凝土轻质隔墙板批发价格 | 云南自考网_云南自学考试网| 深圳办公室装修_办公室设计_写字楼装修设计_深圳市加洲建设集团有限公司 | 立式离心泵_不锈钢自吸泵_液下泵_变频无负压供水设备-大东海泵业无锡有限公司 | 首页-南德电气集团-电能质量产品解决方案|能源数字化系统解决方案|新能源检测评估服务|电力/光伏/储能EPC工程总承包 | 全棉帆布厂家_加工帆布_涤棉帆布价格_染色帆布定制_广州美丽华皮革帆布-广州美丽华皮革帆布 | 耐磨工业软管,PTFE耐腐蚀软管,耐磨喷砂胶管,超耐磨软管厂家,漯河利通液压管利通科技-耐磨工业软管,PTFE耐腐蚀软管,耐磨喷砂胶管,超耐磨软管厂家,漯河利通液压管利通科技 | 粮食加工设备_玉米_大米_面粉_燕麦_豆类杂粮加工设备-华豫万通 | 呼吸家官网|肺功能检测仪生产厂家|国产肺功能仪知名品牌|肺功能检测仪|肺功能测试仪|婴幼儿肺功能仪|弥散残气肺功能仪|肺功能测试系统|广州红象医疗科技有限公司|便携式肺功能仪|大肺功能仪|呼吸康复一体机|儿童肺功能仪|肺活量计|医用简易肺功能仪|呼吸康复系统|肺功能仪|弥散肺功能仪(大肺)|便携式肺功能检测仪|肺康复|呼吸肌力测定肺功能仪|肺功能测定仪|呼吸神经肌肉刺激仪|便携式肺功能 | 齐东汽车-提供抑尘车|洒水车|压缩垃圾车|餐厨垃圾车|垃圾转运车|清洗吸污车|扫路车价格,图片及视频 | 郑州冷却塔_河南冷却塔-河南金创制冷设备有限公司 | 色差宝ColorReader「3nh三恩时」专业版色差宝APP | 上海恩计仪器首页-微生物限度检测仪-微生物限度仪厂家 | 输送机电动滚筒_山东电动滚筒_输送机滚筒_皮带输送机-山东中输输送机械有限公司 | 郑州环球重工机械有限公司建筑垃圾处理专题网站 |