美文网首页
排序算法

排序算法

作者: wshxj123 | 来源:发表于2017-08-15 17:42 被阅读8次

    选择排序

    每次找到最小,与第一个元素交换位置。
    大约需要N2/2次比较和N次交换,运行时间和输入无关,数据移动是最少的。

    void selection_sort(int a[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            int min = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[min])
                    min = j;
            swap(a[min], a[i]);
        }
    }
    

    插入排序

    左边是有序的,每个元素往前面查找位置。
    平均情况:~ N2/4次比较和~ N2/4次交换。平均情况下,每个元素向后移动半个数组位置。
    最坏情况:~ N2/2次比较和~ N2/2次交换。每个元素都要移动到最前面(倒序?)
    最好情况:N-1次比较和0次交换。本来就是有序的。

    void insert_sort(int a[], int n)
    {
        for (int i = 1; i < n; i++)
            for (int j = i; j > 0; j--)
                if (a[j] < a[j-1])
                    swap(a[j], a[j - 1]);
                else break;
    }
    

    希尔排序

    基于插入排序,使得任意相隔为h的元素都是有序的。代码量小,不需要额外的空间,如果们需要解决一个排序问题而又没有系统函数可用,可以先用希尔排序,再考虑是否值得替换为更加复杂的排序算法。

    归并排序

    优点:保证任意长度为N的数组排序所需时间与NlgN成正比
    缺点:所需的额外空间和N成正比

    void merge(int a[], int aux[], int lo, int mid, int hi)
    {
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
    
    void merge_sort(int a[], int aux[], int lo, int hi)
    {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        merge_sort(a, aux, lo, mid);
        merge_sort(a, aux, mid+1, hi);
        if(a[mid + 1] > a[mid]) return;
        merge(a, aux, lo, mid, hi);
    }
    
    

    快速排序

    优点:实现简单,适用于各种不同的输入数据,且在一般应用中比其他排序算法要快得多。它是原地排序,所需时间和NlgN成正比
    缺点:非常脆弱。如果每次取最左边,反而是有序的时候需要~ N2/2次比较。

    可求第k大问题

    int partition(int a[], int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while(true)
        {
            while (a[++i] < a[lo])
                if (i == hi) break;
            while (a[lo] < a[--j])
                if (j == lo) break;
            if (i >= j) break;
            swap(a[i], a[j]);
        }
        swap(a[lo], a[j]);
        return j;
    }
    
    
    void quick_sort(int a[], int lo, int hi)
    {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        quick_sort(a, lo, j-1);
        quick_sort(a, j+1, hi);
    }
    

    堆排序

    用数组表示,不用第一个0
    k的结点的父结点的 k/2向下取整 ,子结点是2k和2k+1
    一棵大小为N的完全二叉树的高度为 lgN向下取整
    优点:唯一能够同时最有地利用空间和时间的方法,在最坏的情况下也能保证使用~2NlgN次比较和恒定的额外空间。当空间十分紧张时(例如在嵌入式系统或者低成本的移动设备中)它很流行,因为它只用几行就能实现比较好的性能。
    缺点:现代系统的很多应用很少使用它,因为无法利用缓存,因为很少和相邻的其他元素进行比较。

    相关文章

      网友评论

          本文标题:排序算法

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