# Basics Sorting - 基礎排序算法 # 算法復習——排序 時間限制為1s時，大O為10000000時勉強可行，100,000,000時很懸。 ### 算法分析 1. 時間復雜度-執行時間(比較和交換次數) 1. 空間復雜度-所消耗的額外內存空間 - 使用小堆棧或表 - 使用鏈表或指針、數組索引來代表數據 - 排序數據的副本 對具有重鍵的數據(同一組數按不同鍵多次排序)進行排序時，需要考慮排序方法的穩定性，在非穩定性排序算法中需要穩定性時可考慮加入小索引。 穩定性：如果排序后文件中擁有相同鍵的項的相對位置不變，這種排序方式是穩定的。 常見的排序算法根據是否需要比較可以分為如下幾類： - Comparison Sorting 1. Bubble Sort 1. Selection Sort 1. Insertion Sort 1. Shell Sort 1. Merge Sort 1. Quck Sort 1. Heap Sort - Bucket Sort - Counting Sort - Radix Sort 從穩定性角度考慮可分為如下兩類： - 穩定 - 非穩定 ### Reference - [常用排序算法總結（性能+代碼） - SegmentFault](http://segmentfault.com/a/1190000002595152#articleHeader15) - [Sorting algorithm - Wikipedia, the free encyclopedia](http://en.wikipedia.org/wiki/Sorting_algorithm) - 各類排序算法的「平均、最好、最壞時間復雜度」總結。 - [經典排序算法總結與實現 | Jark's Blog](http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/) - 基于 Python 的較為清晰的總結。 - [【面經】硅谷前沿Startup面試經驗-排序算法總結及快速排序算法代碼_九章算法](http://blog.sina.com.cn/s/blog_eb52001d0102v1k8.html) - 總結了一些常用常問的排序算法。