1. 什么是排序？
排序是把無序的資料整理為有序的資料，
2. 排序種類劃分？
根據排序中，資料的移動方式劃分為：直接移動和邏輯移動兩種，
根據排序排序中所使用的存盤器劃分為：內部排序和外部排序，
內部排序就是資料操作只需要借助記憶體來完成，
外部排序就是需要借助外部存盤設備，如硬碟，u盤，軟盤等等，適用于資料量龐大的場景，
3.排序演算法優劣劃分依據？
（1）是否穩定，也就是考慮在存在資料相等時，排序后是否會引起相等資料位置的不確定，可以確定相對位置的就是穩定排序，反之，就是不穩定排序，
（2）時間復雜度，用于衡量程式運行時間的函式，
（3）空間復雜度，用于衡量排序所用空間的函式，
4.常用的內部排序演算法有哪些？
（1）冒泡排序，
冒泡排序如同氣泡，自下而上浮出水面，
原理：將每一個元素和其他元素相比較，如果這個元素小于其他元素，就進行調換位置，因此需要 (n-1)+(n-2)+...+(n-(n-1))=1+2+3+...+(n-1)=(n-1)n/2
因此時間復雜度為O(n^2),并且是穩定排序，排序程序只需要一個額外的空間，
另外，冒泡排序在其中一個元素沒有發生交換位置時，就已經是一個有序的資料，回圈可以提前結束，是一個優化的方案，
（2）選擇排序
選擇排序是遍歷資料將每個最小的元素變換位置，而達到最終的有序，有點兒類似于冒泡排序，但是選擇排序不會進行頻繁的位置交換，只會從第一個元素開始，查找最小的元素，次小的等等，最多只會有n-1次交換位置，
從執行次數來講和冒泡排序一樣，時間復雜度也是O(n^2)，
注意：選擇排序不是穩定排序，因為如果有和位置0相等的其他元素，交換為之后，相對順序會發生改變，因此不是穩定的，
空間上只需要1個額外空間，
（3）插入排序
就是依次取一個元素，直至取完，將每一個元素插入，直至最后一個元素，
需要的執行次數為：1+2+...+（n-1）= n(n-1)/2,時間復雜度為O(n^2),并且是穩定排序，需要空間為一個額外的空間，
會進行大量的資料移動，建議在鏈表上使用，
（4）希爾排序
排序原理：分組拆（注意：相反的可以分組合，另一種排序演算法）
就是先分成幾個區塊，再減小間距，直至間距為1，進行最后依次排序，完成！！！
時間復雜度為O(n^3/2),穩定排序，只需要一個額外的空間，
（5）合并排序
由小集合到大集合的程序，就相當于是分多個隊伍，各自排好自己的順序，再合到一起，
時間復雜度為O(n*logn),穩定排序，需要一個與檔案大小相同的空間，
（6）快速排序法
又叫做分割交換排序法，是目前公認最佳的排序法，
原理：固定一個基準點，確定一個基準點，使左邊的資料都小于右邊的資料，各自再進行排序，
時間復雜度為O(nlog2N),不是穩定排序法，因為會進行位置交換，空間復雜度最差為O(n)
，最佳情況為O(log2N)
(7)堆積排序法
運用二叉樹的技巧，樹根大于等于左右子樹，將資料轉換為堆積樹，然后依次從最大的樹根處移除資料，
時間復雜度為O(nlogN)，不是穩定排序，需要一個額外的存盤空間，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121140.html
標籤：其他
上一篇：分治法之棋盤覆寫
下一篇：7-1 0-1背包 (20 分)