分别有5000,10000,15000,20000,25000个数,在关键字的比较次数和移动次数(关键字交换计为3次移动的情况下,冒泡排序、直接插入排序、简单选择排序、希尔排序、堆排序、归并排序、快速排序。分别需要移动和比较多少次
时间: 2023-06-23 15:09:49 浏览: 63
冒泡排序:
- 比较次数:5000^2 + 10000^2 + 15000^2 + 20000^2 + 25000^2 = 6,875,000,000
- 移动次数:5000^2 * 3 + 10000^2 * 3 + 15000^2 * 3 + 20000^2 * 3 + 25000^2 * 3 = 103,125,000,000
直接插入排序:
- 最好情况下比较次数:5000 - 1 + 10000 - 1 + 15000 - 1 + 20000 - 1 + 25000 - 1 = 74,998
- 最坏情况下比较次数:(5000^2 - 5000) / 2 + (10000^2 - 10000) / 2 + (15000^2 - 15000) / 2 + (20000^2 - 20000) / 2 + (25000^2 - 25000) / 2 = 1,562,437,500
- 最好情况下移动次数:5000 - 1 + 10000 - 1 + 15000 - 1 + 20000 - 1 + 25000 - 1 = 74,998
- 最坏情况下移动次数:(5000^2 - 5000) / 2 * 3 + (10000^2 - 10000) / 2 * 3 + (15000^2 - 15000) / 2 * 3 + (20000^2 - 20000) / 2 * 3 + (25000^2 - 25000) / 2 * 3 = 703,110,000
简单选择排序:
- 比较次数:5000^2 + 10000^2 + 15000^2 + 20000^2 + 25000^2 = 6,875,000,000
- 移动次数:5000 + 10000 + 15000 + 20000 + 25000 - 5 = 99,995
希尔排序:
- 比较次数:约为N^(3/2),即约为(5000^(3/2) + 10000^(3/2) + 15000^(3/2) + 20000^(3/2) + 25000^(3/2)) = 1,326,940,311
- 移动次数:不易计算,但比冒泡排序和插入排序少。
堆排序:
- 比较次数:约为NlogN,即约为(5000*log2(5000) + 10000*log2(10000) + 15000*log2(15000) + 20000*log2(20000) + 25000*log2(25000)) = 299,725
- 移动次数:约为2NlogN,即约为(5000*2*log2(5000) + 10000*2*log2(10000) + 15000*2*log2(15000) + 20000*2*log2(20000) + 25000*2*log2(25000)) = 13,353,200
归并排序:
- 比较次数:约为NlogN,即约为(5000*log2(5000) + 10000*log2(10000) + 15000*log2(15000) + 20000*log2(20000) + 25000*log2(25000)) = 299,725
- 移动次数:约为NlogN,即约为(5000*log2(5000) + 10000*log2(10000) + 15000*log2(15000) + 20000*log2(20000) + 25000*log2(25000)) = 299,725
快速排序:
- 最好情况下比较次数:约为NlogN,即约为(5000*log2(5000) + 10000*log2(10000) + 15000*log2(15000) + 20000*log2(20000) + 25000*log2(25000)) = 299,725
- 最坏情况下比较次数:约为N^2,即约为(5000^2 + 10000^2 + 15000^2 + 20000^2 + 25000^2) = 6,875,000,000
- 最好情况下移动次数:约为NlogN,即约为(5000*log2(5000) + 10000*log2(10000) + 15000*log2(15000) + 20000*log2(20000) + 25000*log2(25000)) = 299,725
- 最坏情况下移动次数:约为N^2,即约为(5000^2 + 10000^2 + 15000^2 + 20000^2 + 25000^2) * 3 = 20,625,000,000