python-sort-algorithm

python实现一些排序算法，包括冒泡、选择、插入、希尔、归并、快排、计数以及其中一些的逐步优化过程。（这里均为从小到大排序）

1. sort_bubble

经典的冒泡排序，从前往后两层循环，一一比较。

2. sort_bubble_2

在sort_bubble的基础上添加一个标记，标记最后发生交换的位置，后面的排序过程中不考虑这之后的数据。

3. sort_select

选择排序，同冒泡两层循环，每一次选择最小的放前面。

4. sort_insert

插入排序，每次循环将当前数字添加到已经有序的数组中。

5.sort_insert_2

第二层循环中j修改为从i往前判断。

6.sort_insert_3

增加哨兵机制，减少操作次数。

（其中涉及到一个python与C很大区别的地方）

7.sort_shell

希尔排序，插入排序的进阶版，先按照间隔k排序、再按间隔k/2排序、再按间隔k/4排序……

8.sort_merge

归并排序（自顶向下），典型的分治。

9.sort_merge_2

归并排序（自底向上），效率相比自顶向下略差，但优势在于可以通过修改合并过程达到对链表进行

$n\log_{}{n} $ 级别的排序。

10.sort_quick

快速排序，以第一个数字作为标准，从后面找小的往前放，从前找大的往后放。

11.sort_quick_bobo

以第一个数字作为标准，从前往后遍历，碰到小的就与前面交换，否则遍历下一个数。

缺点：对于近乎有序的数据将退化成 $n ^{2}$ 级别。

12.sort_quick_bobo_2

为了解决近乎有序时退化的问题而随机选取标准（此时变成一种随机算法）。

缺点：数组内存在大量重复元素时效率极差。

13.sort_quick_bobo_3

为了解决大量重复元素的问题，类比sort_quick从前找大，从后找小，最终将数组分成$\le$ 和 $\ge$两部分，也称双路快排。

14.sort_quick_bobo_4

进一步优化存在大量重复元素时的效率。

数组被分为<、=、>三部分，也称三路快排。

15.sort_conut

计数排序，典型的空间换时间。

遍历统计从最小值到最大值之间每个数字各出现了多少次，然后按从小到大的顺序依次输出。

---

对于随机生成的1000个元素

['bubble']        	True: 0.1466073989868164s
['bubble_2']      	True: 0.09474635124206543s
['select']        	True: 0.034906625747680664s
['insert']        	True: 0.05086350440979004s
['insert_2']      	True: 0.0967416763305664s
['insert_3']      	True: 0.041889190673828125s
['merge']         	True: 0.0029909610748291016s
['merge_2']       	True: 0.004987001419067383s
['quick']         	True: 0.001994609832763672s
['quick_bobo']    	True: 0.001994609832763672s
['quick_bobo_2']  	True: 0.003989696502685547s
['quick_bobo_3']  	True: 0.0029921531677246094s
['quick_bobo_4']  	True: 0.002991199493408203s
['shell']         	True: 0.008976936340332031s
['conut']         	True: 0.0s

而随机生成10000个元素后

['bubble']        	True: 16.706886768341064s
['bubble_2']      	True: 10.982130289077759s
['select']        	True: 3.6802918910980225s
['insert']        	True: 5.544185638427734s
['insert_2']      	True: 9.753081560134888s
['insert_3']      	True: 4.579997777938843s
['merge']         	True: 0.042885541915893555s
['merge_2']       	True: 0.056848764419555664s
['quick']         	True: 0.030918121337890625s
['quick_bobo']    	True: 0.04287409782409668s
['quick_bobo_2']  	True: 0.05186104774475098s
['quick_bobo_3']  	True: 0.04089093208312988s
['quick_bobo_4']  	True: 0.05585145950317383s
['shell']         	True: 0.700127124786377s
['conut']         	True: 0.004986763000488281s