排序算法比较

墨蓝 2022-06-04 09:24 208阅读 0赞

一、算法思想

排序即将一组数据按某一域值顺次排列起来。冒泡排序与快速排序都是交换排序的一种，交换排序的基本思想是两两比较待排序对象的关键码，如果发生逆序，即排列顺序与排序后的次序正好相反，则交换之，直到所有对象都排好序为止。

冒泡排序算法思想为：首先比较相邻元素。如果第一个比第二个大，就交换他们两个。然后对每一对相邻元素作同样的工作，从开始第一对到皆为的最后一对，因此最后的元素应该会是最大的数。再对所有元素重复以上步骤，除了最后一个。最后持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较，即排序完成。

快速排序算法思想为：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，因此整个排序过程可以地柜进行，进而达到整个数据变成有序序列。

堆排序的算法思想为：先将初始序列建成一个大根堆，此堆即初始的无序区。再将关键字最大的记录（即堆顶）和无序区的最后一个记录交换，由此得到两部分：新的无序区和有序区（最后一个记录）。由于交换后新的根可能违反堆性质，故应将无序区调整为堆。然后再次将此区中关键字最大的记录和该区间的最后一个记录交换，由此得到新的无序区和有序区。重复此过程。

二、设计思路

1.冒泡排序：设待排序对象序列中的对象个数为n。最多作 n-1趟，i=1，2，...， n-2。在第 i 趟中顺次两两比较v\[n-j-1\].Key和v\[n-j\].Key，j = n-1，n-2，...，i。如果发生逆序，则交换v\[n -j-1\]和v\[n-j\]。第i趟对待排序对象序列v\[i-1\]，v\[i\]，...，v\[n-1\]进行排序，结果将该序列中关键码最小的对象交换到序列的第一个位置(i-1)，其它对象也都向排序的最终位置移动。当然在个别情形下，对象有可能在排序中途向相反的方向移动。这样最多做n-1趟冒泡就能把所有对象排好序。

2.快速排序：从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，当然，这是最理想的情况。

3.堆排序：假设最大堆的第一个对象V\[0\]具有最大的关键码，将V\[0\]与V\[n-1\]对调，把具有最大关键码的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法，重新建立最大堆。结果具有次最大关键码的对象又上浮到堆顶，即V\[0\]位置。再对调V\[0\]和V\[n-1\]，调用堆的调整算法，对前n-2个对象重新调整。如此反复执行，最后得到全部排序好的对象序列。

一、程序代码

1.冒泡排序：

![Center][]

![Center 1][]

2.快速排序（递归）

![Center 2][]

![Center 3][]

3.快速排序非递归

![Center 4][]

![Center 5][]

4.堆排序

![Center 6][]

![Center 7][]

四、测试例

测试例为int型的数组score，其中序列为91, 69, 75, 87, 89, 90, 99, 100。

五、运行结果

1.冒泡排序

![Center 8][]

2.快速排序

![Center 9][]

3.堆排序

![Center 10][]

六、分析

利用堆及其运算，可以很容易地实现选择排序的思路，但堆排序是一种不稳定的排序算法，堆排序的时间复杂性为O(nlog2n)，堆排序算法的附加存储主要是在循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。

快速排序每层都需要一个栈来存放所使用的指针和参数，最大层数与递归树的深度一致，理想情况为log2(n+1)的上界，因此要求的存储开销为O(log2n)，最坏的情况下其排序速度退化到简单排序的水平，比直接插入排序还蛮，占用附加存储将达到O(n)。因此若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能接近，可以加速排序速度，但是由于对象的出师排列次序是随机的，这个要求很难办到。

冒泡排序中最好的情况是对象的初始排列已经按关键码从小到大排好序，此算法只执行一次冒泡，做n-1次关键码比较，不移动对象。而最坏的情况是算法执行了n-1趟冒泡，第i趟做了n-i次关键码比较，执行了n-i次对象交换。冒泡排序需要一个附加对象以实现对象值的对换，冒泡排序是一个稳定的排序方法。

[Center]: /images/20220604/c001483141b0411aa33fb37a87229caf.png
[Center 1]: /images/20220604/7eea8a72101d4ab5a21490c1cd92eca3.png
[Center 2]: /images/20220604/da21605ed7f74526b6f655c861bbc723.png
[Center 3]: /images/20220604/8e35b3a7e1444b5da3d141931cc10f83.png
[Center 4]: /images/20220604/3c783d61db3344e7a34e6bf37e42a74d.png
[Center 5]: /images/20220604/d7a52fd24d5a46afb7977f43f85c9b03.png
[Center 6]: /images/20220604/50dab2d2ed1041688b31f4bfa7a47d62.png
[Center 7]: /images/20220604/91370e7a64cb47e7be58db692c7836a1.png
[Center 8]: /images/20220604/3d0aaaacfd2e47e38f9642d5851efc3c.png
[Center 9]: /images/20220604/f2fd8c3e94654971b357e89fb6f8960d.png
[Center 10]: /images/20220604/fec8f2eec5944979886e673b68712ccb.png