前言
學習《演算法導論》第三版（機械工業出版社），分享一些個人所得以及記錄一些筆記，若有錯誤還請不吝指正，謝謝！
本章節通過分析插入排序，引入《演算法導論》中設計和分析演算法的一個框架
，分上下兩篇博文，一天一篇比較輕松
2.1插入排序
插入排序
通常適用于少量元素的排序，大體上為將一個混亂無序的陣列序列或其他序列，每一次將一個數與已排好序的其他數比較后放在其正確的位置，
例如(加粗字體為已排好序的數):
初始狀態：a[5]=5,2,1,3,6
排序一次：a[5]=5,2,1,3,6
排序兩次：a[5]=2,5,1,3,6
排序三次：a[5]=1,2,5,3,6
排序四次：a[5]=1,2,3,5,6
排序五次：a[5]=1,2,3,5,6
通常進行a.length次排序
回圈不變式
定義：對未進行回圈，但已按序排列陣列，我們稱為回圈不變式，其擁有三個性質：
初始化：回圈的第一次迭代前 ，為真，
保持：回圈的某次迭代之前為真，則下次迭代時仍為真，
終止：在回圈終止時，不變式為我們提供一個有用的性質，該性質有助于證明演算法是正確的，（不同于數學歸納法，數學歸納法可以無限歸納，終止性當回圈終止時便停止）
利用回圈不變式證明插入排序的正確性
初始化：若設陣列只有一個數的時候，很顯然第一次回圈迭代之前陣列已按序排列，為真，回圈不變式成立，
保持：即每一次回圈是否保持了陣列的真值，插入排序每一次將一個數與已排好序的其他數比較后放在其正確的位置，那么對回圈的下一次迭代將保持回圈不變式，
終止：對于插入排序，排序終止時陣列仍然由陣列中的元素組成，但已按序排列，因此演算法正確，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257456.html
標籤：其他