一种基于堆的快速排序算法

A Heap-based Quick Sorting Algorithm

堆排序算法具有低时间复杂度和低空间复杂度的优点;但对原始序列的有序性不敏感。快速排序算法是在平均情况下公认的高速算法;但有较高空间复杂度。对两个算法扬长避短,设计了一种新的排序算法HQSort;并从理论和实例两个角度分析了该算法的效率,在不同量级的数据集上对该算法和三种经典排序算法进行了对比运行和测试,验证了该算法不仅在时间效率上优于其他算法,而且在辅助存储空间上比快速排序算法减少约50%。

The advantage of heap sorting algorithm is lower complexity of time and space, but it is insensitive to the ordering of original array. Quick sorting algorithm is accepted high speed in average case, but it has higher space complexity. A new sorting algorithm named HQSort is designed, it combines advantages of the above two al- gorithms in this paper. The validity of HQSort is proved from two aspects of theory and instance. And a comparison study with other classical sorting algorithms is presented. The comparison is done on different data groups. This study shows that HQSort algorithm has the best performance relative to other three classical sorting algorithms, and only need less than half additional spaces of quick sorting algorithm.