几种常见的排序算法分析

摘要:
选择排序选择排序是一种非常直观且简单的排序算法。对待排序的数组用插入排序,在排序过程中可以看做两部分数组,一个是已经排好序的部分,一个是未排序的部分。归并排序是稳定的排序算法,不是原地排序,时间复杂度为线性对数级别,空间复杂度为N。快速排序的核心和难点是切分。

选择排序

选择排序是一种非常直观且简单的排序算法。它工作的流程是这样的:

首先找出数组中最小的那个元素,将它和数组的第一个元素交换位置;然后在第二个到最后一个元素中间找到最小的那个元素与数组的第二个元素交换位置。

就这样依次遍历,直到将整个数组排序。

选择排序不是稳定排序,但是是原地排序,时间复杂度是平方级,空间复杂度为1。

C++代码实现如下:

#include<iostream>
#include<vector>

template<typename T>
class SelectSort
{
public:
    SelectSort(std::vector<T> &src)
    {
         items = src;
    }
    void sort()
    {
        int N = items.size();
        for(int i = 0; i < N; ++i)
        {   //第i小的元素
            int min = i;
            //从j到N为剩余没有排序的元素
            for(int j = i+1; j < N; ++j)
                if(less(j, min))
                    min = j;
            exchange(i, min);
        }
    }
    void display()
    {
        for(const T &item : items)
            std::cout << item << " ";
        std::cout << std::endl;
    }
private:
    // 默认的比较操作是<
    // 也可自定义
    bool less(int lhs, int rhs)
    {
        return items[lhs] < items[rhs];
    }
    void exchange(int lhs, int rhs)
    {
         T temp = items[lhs];
         items[lhs] = items[rhs];
         items[rhs] = temp;
    }
    std::vector<T> items;
};

插入排序

如果待排序的数据量非常小就可以用插入排序,并且性能非常高。

对待排序的数组用插入排序,在排序过程中可以看做两部分数组,一个是已经排好序的部分,一个是未排序的部分。排序的过程可以看作从未排序的数组中依次

抽取元素插入到已排序的数组中,当未排序的数组为空时数组排序完毕。

插入排序是稳定排序,并且是原地排序,时间复杂度介于线性级别和平方级别,空间复杂度为1。但插入排序的时间复杂度依赖于数据的输入情况,最好情况是

已经有序,时间复杂度为线性;最坏的情况是输入数据是逆序,时间复杂度为平方级别。

C++代码实现如下:

#include<iostream>
#include<vector>

template<typename T>
class InsertSort
{
public:
    InsertSort(std::vector<T> &src)
    {
        items = src;
    }
    void sort()
    {
        int size = items.size();
        // i之所以从1开始是因为把数组分成两份,前一部分有1个元素
        for(int i = 1; i < size; ++i)
            // 将j初始化为i,即排序操作只在前一部分进行
            for(int j = i; j > 0 && less(j, j-1); --j)
                exchange(j, j-1);
    }
    void Display()
    {
         for(const T &item : items)
             std::cout << item << " ";
         std::cout << std::endl;
    }
private:
    // 默认的比较操作是<
    // 也可自定义Less
    bool less(int lhs, int rhs)
    {
        return items[lhs] < items[rhs];
    }
    void exchange(int lhs, int rhs)
    {
        T temp = items[lhs];
        items[lhs] = items[rhs];
        items[rhs] = temp;
    }
    std::vector<T> items;
};

归并排序

归并排序是将待排序的数组分成两半分别排序,然后将这两个已经有序的数组归并起来。

归并排序是稳定的排序算法,不是原地排序,时间复杂度为线性对数级别,空间复杂度为N。

实现代码非常易懂,看一遍就会明白,C++代码实现如下:

#include<iostream>
#include<vector>

template<typename T>
class MergeSort
{
public:
    MergeSort(std::vector<T> &src)
    {
        items = src;
    }
    void sort()
    {
        sort(0, items.size() - 1);
    }
    void display()
    {
         for(const T &item : items)
             std::cout << item << " ";
         std::cout << std::endl;
    }
private:
    void exchange(int lhs, int rhs)
    {
        T temp = items[lhs];
        items[lhs] = items[rhs];
        items[rhs] = temp;
    }
    void sort(int begin, int end)
    {
        if(end <= begin) return;
        int mid = begin + (end - begin) / 2;
        // 左半边排序
        sort(begin, mid);
        // 右半边排序
        sort(mid + 1, end);
        // 左右半边归并
        merge(begin, mid, end);
    }
    void merge(int begin, int mid, int end)
    {
        // i指向数组前半部分
        int i = begin;
        // j指向数组后半部分
        int j = mid + 1;
        // 归并辅助数组
        std::vector<T> aux = items;
        for(int k = begin; k <= end; ++k)
            // 下面四个条件判断不能反过来

            // 左半边用尽取右半边元素
            if(i > mid)
                items[k] = aux[j++];
            // 右半边用尽取左半边元素
            else if(j > end)
                items[k] = aux[i++];
            // 右边当前元素小于左边当前元素,取右半边元素
            else if(aux[i] < aux[j])
                items[k] = aux[i++];
            // 左半边当前元素小于右半边当前元素,取左半边元素
            else
                items[k] = aux[j++];
    }
    std::vector<T> items;
};

快速排序

快速排序是使用最为广泛的排序算法,它实现简单,适用于各种不同的输入数据且在一般情况下比其他算法更快。

快速排序是一种分治的排序算法,它将一个数组分成两个子数组,将两部分独立排序,快速排序和归并排序是互补的:归并排序将数组分成两个子数组分别排序,

并将有序的子数组归并以将整个数组排序;而快速排序将数组排序的方式是当两个子数组都有序时整个数组也就有序了。快速排序的核心和难点是切分。

快速排序不是稳定排序,不是原地排序,时间复杂度是线性对数级别,空间复杂度是lgN。但是快速排序对数据的输入情况有依赖,如果输入的数据本身是有序的

那么快速排序的时间复杂度为平方级别。

C++代码实现如下:

#include<iostream>
#include<vector>
#include<algorithm>

template<typename T>
class QuickSort
{
public:
    QuickSort(std::vector<T> &src)
    {
        items = src;
    }
    void sort()
    {
        // 随机打乱容器内的元素,以免影响排序,此函数定义在头文件algorithm中
        std::random_shuffle(items.begin(), items.end());
        sort(0, items.size() - 1);
    }
    void display()
    {
        for(const T &item : items)
            std::cout << item << " ";
        std::cout << std::endl;
    }
private:
    bool less(int lhs, int rhs)
    {
        return items[lhs] < items[rhs];
    }
    void exchange(int lhs, int rhs)
    {
        T temp = items[lhs];
        items[lhs] = items[rhs];
        items[rhs] = temp;
    }
    void sort(int begin, int end)
    {
        if(end <= begin) return;
        int mid = partition(begin, end);
        sort(begin, mid - 1);
        sort(mid + 1, end);
    }
    int partition(int begin, int end)
    {
        // 置左指针(也就是下标)
        int i = begin;
        // 置右指针
        int j = end + 1;
        // 待切分元素是下标为begin的元素
        while(true)
        {
            // 从左向右找到第一个大于等于待切分元素的元素
            while(less(++i, begin))
                if(i == end)
                    break;
            // 从右向左找到第一个小于等于待切分元素的元素
            while(less(begin, --j))
                if(j == begin)
                    break;
            if(i >= j)
                break;
            exchange(i, j);
        }
        // 交换元素,将待切分元素放入正确的位置
        // 使得待切分元素左边的元素都不比它大,右边的元素都不比它小
        exchange(begin, j);
        return j;
    }
    std::vector<T> items;
};

堆排序

堆排序是利用二叉堆的性质来将数组排序,分为两大步:

  1. 第一步构造堆,将数据构造成堆有序的状态(堆有序并不是元素有序)。

  2. 第二步依次取出最大元素,将元素变成有序状态。

堆排序不是稳定排序,不是原地排序,时间复杂度为线性对数级别,空间复杂度为1。

C++代码实现如下:

#include<iostream>

template<typename ValueType>
class HeapSort
{
public:
    HeapSort(ValueType src[], int arraySize)
    {
        this->len = arraySize;
        items = new ValueType[len];
        for(int i = 0; i < len; ++i)
            items[i] = src[i];
    }
    ~HeapSort()
    {
        delete[] items;
    }
    void sort()
    {
        // 堆有序化
	    for (int i = len / 2 - 1; i >= 0; i--)
	    	sink(i, len - 1);
	    // 排序
	    for (int i = len - 1; i > 0; i--) {
	    	exchange(0, i);
	    	sink(0, i - 1);
	    }
    }
    void display()
    {
        for(int i = 0; i < len; ++i)
            std::cout << items[i] << " ";
        std::cout << std::endl;
    }
private:
    bool less(int lhs, int rhs)
    {
        return items[lhs] < items[rhs];
    }
    void exchange(int lhs, int rhs)
    {
        ValueType temp = items[lhs];
        items[lhs] = items[rhs];
        items[rhs] = temp;
    }
    // 元素下沉
    void sink(int start, int end) 
    {
	    int dad = start;
	    int son = dad * 2 + 1;
	    while (son <= end) 
        {
            // 选择较大的子节点
	    	if (son + 1 <= end && items[son] < items[son + 1])
	    		son++;
	    	if (items[dad] > items[son])
	    		return;
	    	else // 如果子节点大于父节点则交换两者位置
            {
	    		exchange(dad, son);
	    		dad = son;
	    		son = dad * 2 + 1;
	    	}
	    }
    }
    int len;
    ValueType *items;
};

各种排序算法的特点总结如下

算法是否稳定是否为原地排序时间复杂度空间复杂度备注
选择排序N^21
插入排序介于N和N^2之间1取决于输入元素的排序情况
归并排序NlogNN
快速排序NlogNlgN取决于输入元素的排序情况
堆排序NlogN1

免责声明:文章转载自《几种常见的排序算法分析》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Tomcat错误之java.lang.OutOfMemoryError:PermGen space解决方案ansible-任务控制tags下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

scala的多种集合的使用(5)之数组Array(ArrayBuffer)的操作

1.创建和更新数组的不同方式 1)定义一个数组的初始大小和类型,随后填充值。 scala> val array = new Array[String](3) array: Array[String] = Array(null, null, null) scala> array(0) = "abc" scala> array(1) =...

七、特征提取和转换

TF-IDF TF-IDF(Term frequency-inverse document frequency ) 是文本挖掘中一种广泛使用的特征向量化方法。TF-IDF反映了语料中单词对文档的重要程度。假设单词用t表示,文档用d表示,语料用D表示,那么文档频度DF(t, D)是包含单词t的文档数。如果我们只是使用词频度量重要性,就会很容易过分强调重负次数...

JS数组及其方法(slice,contact...)

JS数组的创建:     1,使用Array数组的方式:   var arrayObj = new Array(); //创建一个数组   var arrayObj = new Array([size]); //创建一个数组并指定长度,注意不是上限,是长度   var arrayObj = new Array([element0[, element1[,...

MySQL查询截取分析

一、查询优化 1,mysql的调优大纲 慢查询的开启并捕获 explain+慢SQL分析 show profile查询SQL在Mysql服务器里面的执行细节和生命周期情况 SQL数据库服务器的参数调优 2,小表驱动大表 mysql的join实现原理是,以驱动表的数据为基础,“嵌套循环”去被驱动表匹配记录。驱动表的索引会失效,而被驱动表的索引有效。 #假...

unity_数据结构(常见数据结构及适用场景)

常见的数据结构: 1.Array: 最简单的数据结构 特点:数组存储在连续的内存上。数组的内容都是相同类型。数组可以直接通过下标访问。优点:由于是在连续内存上存储的,所以它的索引速度非常快,访问一个元素的时间是恒定的也就是说与数组的元素数量无关,而且赋值与修改元素也很简单。缺点:由于是连续存储,所以在两个元素之间插入新的元素就变得不方便。声明一个新的数组时...

原创:python的requests.post()向后端传递数据,数组结构需将python数据结果转换成JSON

 针对采集来的数据,用requests.post()向后端传递 如果是python数据结构如数组,需要转换成为JSON对象,否则后端容易解析不成后端集合的对象结构 re 一:python做为前端请求requests.post() ''' 后台接收是数组 ''' dataInfoList = [...