美文网首页
排序算法

排序算法

作者: 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次比较和恒定的额外空间。当空间十分紧张时(例如在嵌入式系统或者低成本的移动设备中)它很流行,因为它只用几行就能实现比较好的性能。
缺点:现代系统的很多应用很少使用它,因为无法利用缓存,因为很少和相邻的其他元素进行比较。

相关文章

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • web开发需要知道的几个算法

    算法分类 快速排序算法 深度优先算法 广度优先算法 堆排序算法 归并排序算法

  • 算法学习(1)-排序算法

    八大排序算法九大排序算法再总结[经典排序算法][集锦][直观学习排序算法] 视觉直观感受若干常用排序算法 快速排序...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 前端算法学习-第一篇

    冒泡排序算法 冒泡排序算法是最慢的排序算法之一,也是最容易实现的排序算法。之所以叫冒泡排序是因为使用这种算法排序时...

  • 七大排序算法之冒泡排序

    七大排序算法之冒泡排序 @(算法笔记)[排序算法, 冒泡排序, C++实现] 冒泡排序介绍 冒泡排序是七大排序算法...

  • 算法-选择排序

    算 法:选择排序算法时间复杂度: 选择排序算法概述 选择排序伪代码 选择排序实现 选择排序算法概述 排序算法有许...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 算法4:插入排序和选择排序算法的比较

    排序算法列表电梯: 选择排序算法:详见 《算法4》2.1 - 选择排序算法(Selection Sort), Py...

网友评论

      本文标题:排序算法

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