详解排序算法--堆排序

作者: 六尺帐篷 | 来源:发表于2017-08-08 14:44 被阅读262次

    选择排序

    选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
    选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

    ![Uploading Selection_sort_animation_154868.gif . . .] Selection_sort_animation.gif
    • 最坏时间复杂度 О(n²)
    • 最优时间复杂度 О(n²)
    • 平均时间复杂度 О(n²)
    • 空间复杂度 О(n) total, O(1) auxiliary

    Java实现:

    
    package cc;
    
    public class Select {
    
        public static void selectSort(int[] a) 
        {
            int N = a.length;
            for(int i=0;i<N;i++)
            {
                /* 从A[i]到A[N–1]中找最小元,并将其位置赋给MinPosition */
                int min = i;
                for(int j=i+1;j<N;j++)
                {
                    if(a[j]<a[min])
                        min=j;
                }
                /* 将未排序部分的最小元换到有序部分的最后位置 */
                int t = a[i];
                a[i] = a[min];
                a[min] = t;
            }
        }
    }
    
    

    想要进一步改进选择排序,就在于

    如何快速找到最小元???

    如果读者已经对于堆较为熟悉的话,很容易就想到这里可以利用堆实现。
    这就是堆排序的由来

    堆排序

    堆排序(Heapsort)是指利用这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆节点的访问

    通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

    • 父节点i的左子节点在位置(2*i+1);
    • 父节点i的右子节点在位置(2*i+2);
    • 子节点i的父节点在位置floor((i-1)/2);

    堆的操作

    在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作:

    • 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
    • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
    • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

    按照选择排序的思想,我们先实现一个简单的堆排序

    void Heap_Sort ( ElementType A[], int N )
    { BuildHeap(A); /* O(N) */
    for ( i=0; i<N; i++ )
    TmpA[i] = DeleteMin(A); /* O(logN) */
    for ( i=0; i<N; i++ ) /* O(N) */
    A[i] = TmpA[i];
    }
    

    T ( N ) = O ( N log N )
    缺点在于:
    需要额外O(N)空间,并且复制元素需要时间。

    原地堆排序

    基于以上相关的操作,我们可以很容易的定义堆排序。例如,假设我们已经读入一系列数据并创建了一个堆,一个最直观的算法就是反复的调用del_max()
    函数,因为该函数总是能够返回堆中最大的值,然后把它从堆中删除,从而对这一系列返回值的输出就得到了该序列的降序排列。

    真正的原地堆排序使用了另外一个小技巧。堆排序的过程是:

    • 创建一个堆H[0..n-1]
    • 把堆首(最大值)和堆尾互换
    • 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
    • 重复步骤2,直到堆的尺寸为1

    伪码

    void Heap_Sort ( ElementType A[], int N )
    { for ( i=N/2-1; i>=0; i-- )/* BuildHeap */
    PercDown( A, i, N );
    for ( i=N-1; i>0; i-- ) {
    Swap( &A[0], &A[i] ); /* DeleteMax */
    PercDown( A, 0, i );
    }
    }
    
    • 最坏时间复杂度
    Sorting_heapsort_anim.gif

    Java实现

    package cc;
    
    public class HeapSort {
        
        private static int leftChild(int i) {
            return 2*i+1;
        }
        
        private static void percDown(int[] a, int i, int n) {
            int child;
            int temp;
            
            for(temp = a[i]; leftChild(i) < n;i = child) {
                child = leftChild(i);
                if(child != n-1 && a[child] < a[child+1])
                    child++;
                if(temp < a[child])
                    a[i] = a[child];
                else
                    break;
            }
            a[i] = temp;
        }
    
        public static void heapsort(int[] a) {
            
            for(int i=a.length/2-1;i>=0;i--) {
                percDown(a, i, a.length);
            }
            
            for(int i=a.length-1;i>0;i--) {
                swap(a, 0, i);
                percDown(a, 0, i);
            }
        }
        
        private static void swap(int[] a, int i, int j) {
            
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            
        }
    }
    

    相关文章

      网友评论

        本文标题:详解排序算法--堆排序

        本文链接:https://www.haomeiwen.com/subject/ywytrxtx.html