什么是算法絮缅？
算法（Algorithm）是指解題方案的準確而完整的描述鲤竹，是一系列解決問題的清晰指令蕉汪，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說封字，能夠對一定規(guī)范的輸入黔州，在有限時間內獲得所要求的輸出。不同的算法可能用不同的時間阔籽、空間或效率來完成同樣的任務流妻。一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。
算法（Algorithm）：一個計算過程笆制，解決問題的方法绅这。
算法復雜度分為時間復雜度和空間復雜度。其作用： 時間復雜度是指執(zhí)行算法所需要的計算工作量在辆；而空間復雜度是指執(zhí)行這個算法所需要的內存空間证薇。（算法的復雜性體現在運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器資源匆篓，因此復雜度分為時間和空間復雜度）浑度。當然，不作特殊說明鸦概，我們一般討論的是該算法的最壞時間復雜度和最壞空間復雜度箩张，即分析最壞情況以估算算法的執(zhí)行時間的上界。
1. 時間復雜度
我們一般采用大O漸進表示法描述一個算法的時間復雜度窗市。時間復雜度主要討論的是算法執(zhí)行的次數先慷。****時間復雜度是用來估計算法運行時間的一個式子（單位）。一般來說咨察，時間復雜度高的算法比復雜度低的算法慢论熙。
一般算法時間復雜度O(n)的表示方法：
（1）用常數1取代運行時間中的所有加法常數 ；
（2）在修改后的運行次數函數中摄狱，只保留最高階項赴肚；（大單位后面不掛小單位）
（3）如果最高階項系數存在且不是1素跺，則去除與這個項相乘的常數；（去掉系數）
（4）遞歸算法的時間復雜度 ==** 遞歸總次數每次遞歸的次數*
空間復雜度 == 遞歸的深度（即樹的高度）
（5）常見的時間復雜度（按效率排序）
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
（6）不常見的時間復雜度（看看就好）
O(n!) O(2n) O(nn) …
如何一眼判斷時間復雜度誉券？
- 沒有循環(huán)O(1)指厌；
- 循環(huán)減半的過程?O(logn)；
- 幾層循環(huán)就是n的幾次方的復雜度（舍棄小項）踊跟；
復雜度通稱為O(n)
T(n)：時間復雜度Time
S(n)：空間復雜度Space
名詞解釋:
n:問題的規(guī)模,重復執(zhí)行的次數
T(n):一段程序運行,各種操作代碼所執(zhí)行的總次數
f(n): 存在的某個函數,使得T(n)/f(n)=非零常數, 那么f(n)稱為T(n)的同數量級函數
O:大O符號,一種符號,表示漸進于無窮的行為穿起來:
算法中各種代碼操作所執(zhí)行的總次數用T(n)表示,存在某個函數f(n),使得T(n)/f(n)=非零常數,那么f(n)稱為T(n)的同數量級函數(類想一下,在坐標軸中,當入參n趨于無窮時,兩條曲線的商為常數),即:T(n)=O(f(n)),O(f(n))就是時間復雜度.O符號表示一個漸進常數. 在這個函數中可以忽略低階項和首項系數,中文例二解釋.
時間復雜度只是估計踩验，結果O(n2) 相同，不一定時間相同規(guī)模商玫，計算機運算速度箕憾。
O(logn)是非常快的一種算法拳昌，以上面64為例袭异，更接近O（1）。所以炬藤，一個算法如果能優(yōu)化成O(logn)御铃，是非常快的沈矿。
注意：循環(huán)減半和數值減一的區(qū)別
# 循環(huán)減半上真，每次運行，循環(huán)次數就減掉一半log2n
while n > 1:
print(n)
n = n // 2
# 數值減一羹膳。因為步長為2睡互，所以，是減掉了1陵像，時間復雜度為1/2n就珠，不要系數，所以時間復雜度為O(n)
for i in range(0,n,2):
print('Hello World')
# 時間復雜度O(n3logn)
for i in range(n):
for i in range(n):
for i in range(n):
print('Hello World') # 到這是三層
while n:
n = n // 2
for i in range(n):
for i in range(n):
print('Hello World') # 到這是四層
解釋：while的時間復雜度是O(nlogn),比O(1)大
2. 空間復雜度
空間復雜度：即程序中變量的個數
3. 排序的穩(wěn)定性
穩(wěn)定性
① 定義：能保證兩個相等的數醒颖，經過排序之后妻怎，其在序列的前后位置順序不變。（A1=A2图贸，排序前A1在A2前面蹂季，排序后A1還在A2前面）
② 意義：穩(wěn)定性本質是維持具有相同屬性的數據的插入順序冕广，如果后面需要使用該插入順序排序疏日，則穩(wěn)定性排序可以避免這次排序。
比如撒汉，公司想根據“能力”和“資歷”（以進入公司先后順序為標準）作為本次提拔的參考沟优，假設A和B能力相當，如果是穩(wěn)定性排序睬辐，則第一次根據“能力”排序之后挠阁，就不需要第二次根據“”資歷
排序了宾肺，因為“資歷”排序就是員工插入員工表的順序。如果是不穩(wěn)定排序侵俗，則需要第二次排序锨用，會增加系統(tǒng)開銷。
分類
① 穩(wěn)定性排序：冒泡排序隘谣，插入排序增拥、歸并排序、基數排序
② 不穩(wěn)定性排序：選擇排序寻歧、快速排序掌栅、希爾排序、堆排序
例析
（1）穩(wěn)定性排序
① 冒泡排序
冒泡排序本質是码泛，從左到右開始不斷把大的元素往后調（或者猾封，從右往左開始不斷把小的元素往前調）。比較是比較相鄰的兩個元素噪珊，交換也是發(fā)生在這兩個元素之間晌缘。所以，如果兩個元素相等卿城，你總不會無聊地把它倆交換一下吧枚钓。如果兩個相等元素沒有相鄰，那么也會經過一波兩兩交換使他們相鄰瑟押，此時也不會發(fā)生交換搀捷。
② 插入排序
插入排序本質是，在一個已經有序的小序列基礎上多望，通過從右往左比較嫩舟，一次插入一個元素。剛開始這個小序列只有一個元素怀偷。比較是從有序序列的末尾開始家厌，想插入的元素和已經有序的最大者開始比較，如果比它大則直接插在其后面椎工，否則一直往前比較饭于，直到找到比它小的或與它相等的，然后插在其后面维蒙。
③ 歸并排序
歸并排序本質是掰吕，把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(此時認為直接有序)或者2個序列(1次比較和交換)颅痊，然后把各個有序的短序列合并成一個有序的長序列殖熟，不斷合并直到原序列全部排好序。當存在1個或2個元素時斑响，1個元素不會交換菱属，2個元素如果大小相等也沒有人故意交換钳榨，因此不會破壞穩(wěn)定性。那么在短的有序序列合并的過程中纽门，穩(wěn)定是否受到破壞薛耻？沒有。合并過程中當兩個當前元素相等時赏陵，處在前面序列的元素依然保存在結果序列的前面昭卓。
④ 基數排序
基數排序本質是，按照低位先排序瘟滨，然后收集候醒，再按照高位排序，然后再收集杂瘸，依次類推倒淫，直到最高位。比如序列“171(1),331,171(2)”败玉，低位排序（個位）結果是“171(1),331,171(2)”敌土，高位排序（十位）結果是“331171(1),171(2)”，高位排序（百位）結果是“171(1),171(2),331”运翼。
（2）不穩(wěn)定性排序
① 選擇排序
選擇排序本質是返干，給每個位置選擇剩下元素中最小的。比如給第一個位置選擇最小的血淌，給第二個位置選擇剩余元素里面第二小的矩欠，依次類推。例如序列“5(1),8,5(2),2,9”悠夯，5(1)會和2交換癌淮，破壞穩(wěn)定性。
② 快速排序
快速排序本質是沦补，選取第一個元素為中樞元素a[center_index]（index=0）乳蓄。從兩個方向入手，首先左邊的i下標一直往右走夕膀，當a[i] > a[center_index]停止虚倒，由右邊的j下標開始往左走，當a[j] <= a[center_index]停止产舞，由左邊i下標開始剛才的表演魂奥，重復上面的過程，直到i>j庞瘸，交換a[j]和a[center_index]捧弃，完成一趟快速排序赠叼。在中樞元素和a[j]交換的時候擦囊，很有可能把前面的元素的穩(wěn)定性打亂违霞，比如序列為 “5,3(1),4,3(2),8,11,9”， 現在中樞元素5和3(2)交換就會把元素3的穩(wěn)定性打亂瞬场。不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻买鸽。
③ 希爾排序
希爾排序本質是，按照不同步長對元素進行插入排序贯被，當剛開始元素很無序的時候眼五，步長最大，所以插入排序的元素個數很少彤灶，速度很快看幼；當元素基本有序了，步長很小幌陕，插入排序對于有序的序列效率很高诵姜。所以，希爾排序的時間復雜度會比o(n^2)好一些搏熄。由于多次插入排序棚唆，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序心例，但在不同的插入排序過程中宵凌，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂止后，所以shell排序是不穩(wěn)定的瞎惫。
④ 堆排序
堆排序本質是，我們知道堆的結構是節(jié)點i的孩子為2i和2i+1節(jié)點译株，大頂堆要求父節(jié)點大于等于其2個子節(jié)點微饥，小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為n的序列古戴，堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩(wěn)定性欠橘。但當為n/2-1, n/2-2, ...1這些個父節(jié)點選擇元素時，就會破壞穩(wěn)定性现恼。有可能第n/2個父節(jié)點交換把后面一個元素交換過去了肃续，而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了叉袍。所以始锚，堆排序不是穩(wěn)定的排序算法。
排序算法時間的復雜度和空間復雜度
