排序算法备忘录（二） 这是排序算法备忘录的第二篇。这一篇是关于插入排序。
插入排序的原理类似于日常生活中排序的方法，先找到一个有序的数列，把一个数按照一定的顺序与有序数列中的数字进行比较，找到所在的位置，放入其中，构成一个新的有序列表。
具体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import randomn = 1000 lst = [] for i in range (n): lst.append(i) random.shuffle(lst) for i in range (1 , n): j = i - 1 current = lst[i] while j >= 0 and lst[j] > current: lst[j + 1 ] = lst[j] j -= 1 lst[j + 1 ] = current print (lst)
在最初自己实现插入排序的过程中，我也写出了如下的代码：
1 2 3 4 5 6 7 for i in range (1 , n): for j in range (i): if lst[i] < lst[j]: lst[i], lst[j] = lst[j], lst[i]
在当前条件下，这样的实现在速度上会慢两倍左右。
我认为主要有两个原因：
我之前的写法循环次数是固定的，前一半循环用来寻找数据，后一半循环用来挪动位置，所以总的循环次数是
count 1 = n ( n − 1 ) 2 \text{count}_1 = \frac{n(n-1)}{2}
count 1 = 2 n ( n − 1 )
这相当于最坏的情况。而第一种写法同时实现了插入位置的查找和位置的挪动，所以更加高效
由于插入的位置平均下来位于有序数列的中间，所以单从循环次数看，大约比第二种写法少了一半，这在数据量大时更加明显。而且，第二种写法挪动位置时需要进行交换操作，而第一种只是进行一次复制，这也是效率更高的原因
对于插入排序，最好的情况下，循环次数是
count 2 = n − 1 \text{count}_2 = n-1
count 2 = n − 1
所以平均的情况下
count ‾ = n 2 + n − 2 4 ≈ n 2 \overline{\text{count}} = \frac{n^2+n-2}{4} \approx n^2
count = 4 n 2 + n − 2 ≈ n 2
从实验结果来看，当数据量较大时，循环结果比较接近平均情况下的循环次数。
而且，对于插入位置来说，由于在我的实验条件下，每次取到的随机数据的大小是均匀的，大小交错的，所以每次插入的位置要么靠前，要么靠后，平均结果是相当于插入在了中间的位置，在这种假设下，循环次数应该是
count 3 = n 2 − n 4 ≈ n 2 \text{count}_3=\frac{n^2-n}{4} \approx n^2
count 3 = 4 n 2 − n ≈ n 2
当 n 足够大时，这与平均情况下的结果是十分接近的。所以平均情况相当于每次都插入中间位置。
以下是我用 1-1000 的随机数列进行实验的结果：
这是 1000 次实验下对于数据容量为 1000 的插入位置与中间位置的偏差以及循环次数与平均情况的偏差
Position error 平均值为 1.95%，Count error 平均值为 1.73%
可以看到，误差集中在 0.005 到 0.025，即 0.5% 到 2.5%，说明在数据规模为 1000 时，由 Count error 可以看出，每次结果都比较接近平均情况，由 Position Error 可以看出，在平均的情况下，插入位置比较接近中间位置，这验证了之前的假设。
这是不同数据规模下插入位置与中间位置的偏差和循环次数与平均情况的偏差(每种规模 50 次实验)
从这张图可以看到，当数据规模逐渐变大时，这种平均情况更加显著。
以下是进行测试的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 import randomimport matplotlib.pyplot as pltdef insertion (n ): lst = [] lst1 = [] for i in range (n): lst1.append(i) random.shuffle(lst1) count = 0 for i in range (1 , n): j = i - 1 current = lst1[i] while j >= 0 and lst1[j] > current: lst1[j + 1 ] = lst1[j] j -= 1 count += 1 lst1[j + 1 ] = current lst.append(j / i) position = sum (lst) / (n - 1 ) position_err = abs (position - 0.5 ) / 0.5 half_count = n * (n - 1 ) / 4 + n / 2 - 1 / 2 count_err = abs (count - half_count) / half_count return {'position' :position_err,'count' :count_err} pos = [] counts = [] for i in range (1000 ): res = insertion(1000 ) position = res['position' ] count = res['count' ] pos.append(position) counts.append(count) print (f'[{i} ]:position error is {position:.2 %} , count error is {count:.2 %} ' ) print (f'Position error in average is {sum (pos) / len (pos):.2 %} , count error in average is {sum (counts) / len (counts):.2 %} ' )aver_pos = [] aver_count = [] for i in (10 , 50 , 100 , 500 , 1000 , 5000 ): pos_ = [] counts_ = [] for _ in range (50 ): res = insertion(i) position = res['position' ] count = res['count' ] pos_.append(position) counts_.append(count) aver_pos.append(sum (pos_) / len (pos_)) aver_count.append(sum (counts_) / len (counts_)) for i in range (6 ): print (f'Data size:{i} , position error is {aver_pos[i]:.2 %} , count error is {aver_count[i]:.2 %} ' ) x1 = range (1000 ) x2 = range (1000 ) x3 = range (6 ) plt.plot(x1, pos, label = 'Position error' , marker = 'o' ) plt.plot(x2, counts, label = 'Count error' , marker = 'x' ) plt.xlabel('Experiment' ) plt.ylabel('Error' ) plt.title('Position Error and Count Error among 1000 Experiments' ) plt.legend() plt.show() plt.plot(x3, aver_pos, label = 'Position error' , marker = 'o' ) plt.plot(x3, aver_count, label = 'Count error' , marker = 'x' ) plt.xlabel('Experiment' ) plt.xticks(x3, ['10' , '50' , '100' , '500' , '1000' , '5000' , ]) plt.ylabel('Error' ) plt.title('Position Error and Count Error among Different Data Sizes' ) plt.legend() plt.show()
