百万数据排序：优化的选择排序（堆排序）

时间：2014-07-22 22:46:45 阅读：440 评论：0 收藏：0 [点我收藏+]

前一篇给大家介绍了《必知必会的冒泡排序和快速排序（面试必知）》，现在继续介绍排序算法

本博文介绍首先介绍直接选择排序，然后针对直接选择排序的缺点改进的“堆排序”，堆排序非常适合：数组规模非常大（数百万或更多） + 严格要求辅助空间的场景。

直接选择排序

(一)概念及实现

直接选择排序的原理：将整个数组视为虚拟的有序区和无序区，重复的遍历数组，每次遍历从无序区中选出一个最小（或最大）的元素，放在有序区的最后，每一次遍历排序过程都是有序区元素个数增加，无序区元素个数减少的过程，直到无序区元素个数位0。

具体如下（实现为升序）：

设数组为a[0…n-1]。

1. 将原序列分成有序区和无序区。a[0…i-1]为有序区，a[i…n-1]为无序区。初始化有序区为0个元素。

2. 遍历无序区元素，选出最小元素，放在有序区序列最后（即与无序区的第一个元素交换）

3. 重复步骤2，直到无序区元素个数为0。

实现代码：

        public static void Sort<T>(IList<T> arr) where T : IComparable<T>
        {
            if (arr == null)
                throw new ArgumentNullException("arr");

            int length = arr.Count();
            if (length > 1)
            {
                int minValueIndex = 0;
                T minValue = default(T);

                // 循环length - 2次，最后一个元素无需再比较
                for (int i = 0; i < length - 1; i++)
                {
                    minValueIndex = i;
                    minValue = arr[i];

                    // 内部循环，查找本次循环的最小值
                    for (int j = i + 1; j < length; j++)
                    {
                        if (minValue.CompareTo(arr[j]) > 0)
                        {
                            minValueIndex = j;
                            minValue = arr[j];
                        }
                    }

                    if (minValueIndex == i)
                        continue;

                    // 交换：将本次循环选出的最小值，顺序放在有序区序列的最后（即与无序区的第一个元素交换）
                    arr[minValueIndex] = arr[i];
                    arr[i] = minValue;
                }

            }
        }

示例：

89,-7,999,-89,7,0,-888,7,-7

排序的过程：

[-888] [-7 999 -89 7 0 89 7 -7]

[-888 -89] [999 -7 7 0 89 7 -7]

[-888 -89 -7] [999 7 0 89 7 -7]

[-888 -89 -7 -7] [7 0 89 7 999]

……

[-888 -89 -7 -7 0 7 7 89 999] []

(二)算法复杂度

1. 时间复杂度：O(n^2)

直接选择排序耗时的操作有：比较 + 交换赋值。时间复杂度如下：

1) 最好情况：序列是升序排列，在这种情况下，需要进行的比较操作需n(n-1)/2次。交换赋值操作为0次。即O(n^2)

2) 最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。交换赋值n-1 次（交换次数比冒泡排序少多了），直接选择排序的效率比较稳定，最好情况和最坏情况差不多。即O(n^2)

3) 渐进时间复杂度（平均时间复杂度）：O(n^2)

2. 空间复杂度：O(1)

从实现原理可知，直接选择插入排序是在原输入数组上进行交换赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)

(三)稳定性

直接选择排序是不稳定的。

因为每次遍历比较完后会使用本次遍历选择的最小元素和无序区的第一个元素交换位置，所以如果无序区第一个元素后面有相同元素的，则可能会改变相同元素的相对顺序。

(四)优化改进

1. 相同元素：如果数组元素重复率高，可以考虑使用辅助空间在每一次循环的时候，将本次选择的数及相同元素的索引记录下来，一起处理。

2. 堆排序：直接选择排序中，为了从a[0..n-1]中选出关键字最小的记录，必须进行n-1次比较，然后在a[1..n-1]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构保存部分比较结果，可减少比较次数。（这种效果在数组规模越大越能体现效果）

堆排序

(一)概念及实现

堆排序(Heapsort)的原理：是指利用“二叉堆”这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

1. 二叉堆

是完全二叉树或者是近似完全二叉树，它有两种形式：最大堆（大顶堆、大根堆）和最小堆（小顶堆、小根堆）。

2. 二叉堆满足二个特性

1) 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2) 每个结点的左子树和右子树都是一个二叉堆（最大堆或最小堆）。

3. 二叉堆一般用数组来表示

如果根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2，其父节点的下标是 (n-1)/2 。

4. 示例

原数组：

初始化为最大堆：

具体如下（实现为升序）：

设数组为a[0…n-1]。

1. 将原序列分成有序区和无序区。a[0…i-1]为无序区，a[i…n-1]为有序区。初始化有序区为0个元素。

2. （从下往上）从数组最后一个根节点开始 (maxIndex - 1)/2 ，将原数组初始化为最大堆。（如上图）

3. （从上往下）将堆顶元素与无序区的最后一个元素交换（即插入有序区的第一个位置），将剩余的无序区元素重建最大堆。

4. 重复步骤3，每一次重复都是有序区元素个数增加，无序区元素个数减少的过程，直到无序区元素个数位0

实现代码：

    /// <summary>
    /// 堆排序
    /// </summary>
    public class Heap
    {
        public static void Sort<T>(IList<T> arr) where T : IComparable<T>
        {
            if (arr == null)
                throw new ArgumentNullException("arr");

            int length = arr.Count();
            if (length > 1)
            {
                // 1、初始化最大堆
                InitMaxHeap<T>(arr, length - 1);

                // 2、堆排序
                // 将堆顶数据与末尾数据交换，再将i=N-1长的堆调整为最大堆；不断缩小待排序范围直到，无序区元素为0。
                for (int i = length - 1; i > 0; i--)
                {
                    // 2.1 将堆顶数据与末尾数据交换
                    Swap<T>(arr, 0, i);
                    // 2.2 缩小数组待排序范围 i - 1 ，重新调整为最大堆
                    AdjustMaxHeap<T>(arr, 0, i - 1);
                }
            }
        }

        /// <summary>
        /// 构建最大堆  （还未进行排序）
        /// </summary>
        /// <param name="arr">待排序数组</param>
        /// <param name="maxIndex">待排序数组最大索引</param>
        private static void InitMaxHeap<T>(IList<T> arr, int maxIndex) where T : IComparable<T>
        {
            // 从完全二叉树最后一个非叶节点 ：
            // 如果根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2，其父节点的下标是 (n-1)/2 。
            for (int i = (maxIndex - 1) / 2; i >= 0; i--)
            {
                AdjustMaxHeap<T>(arr, i, maxIndex);
            }
        }

        /// <summary>
        /// 调整指定父节点的二叉树为最大堆
        /// </summary>
        /// <param name="arr">待排序数组</param>
        /// <param name="parentNodeIndex">指定父节点</param>
        /// <param name="maxIndex">待排序数组最大索引</param>
        private static void AdjustMaxHeap<T>(IList<T> arr, int parentNodeIndex, int maxIndex)
            where T : IComparable<T>
        {
            if (maxIndex > 0)   // 只有堆顶一个元素，就不用调整了
            {
                int resultIndex = -1;
                // 下标为i的节点的子节点是2i + 1与2i + 2
                int leftIndex = 2 * parentNodeIndex + 1;
                int rightIndex = 2 * parentNodeIndex + 2;
                if (leftIndex > maxIndex)
                {
                    // 该父节点没有左右子节点
                    return;
                }
                else if (rightIndex > maxIndex)
                    resultIndex = leftIndex;
                else
                    // 比较左右节点。
                    resultIndex = Max<T>(arr, leftIndex, rightIndex);

                // 父节点与较大的子节点进行比较
                resultIndex = Max<T>(arr, parentNodeIndex, resultIndex);

                if (resultIndex != parentNodeIndex)
                {
                    // 如果最大的不是父节点，则交换。
                    Swap<T>(arr, parentNodeIndex, resultIndex);
                    // 交换后子树可能不是最大堆，所以需要重新调整交换元素的子树
                    AdjustMaxHeap<T>(arr, resultIndex, maxIndex);
                }
            }
        }

        /// <summary>
        /// 获取较大数的数组索引
        /// </summary>
        /// <param name="arr">待排序数组</param>
        /// <param name="leftIndex">左节点索引</param>
        /// <param name="rightIndex">右节点索引</param>
        /// <returns>返回较大数的数组索引</returns>
        private static int Max<T>(IList<T> arr, int leftIndex, int rightIndex) where T : IComparable<T>
        {
            // 相等，以左节点为大
            return arr[leftIndex].CompareTo(arr[rightIndex]) >= 0 ? leftIndex : rightIndex;
        }

        /// <summary>
        /// 数组元素交换
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr">数组</param>
        /// <param name="i">交换元素1</param>
        /// <param name="j">交换元素2</param>
        private static void Swap<T>(IList<T> arr, int i, int j)
        {
            T temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

示例：

89,-7,999,-89,7,0,-888,7,-7

排序的过程：

初始化最大堆