选择排序和插入排序(三十)

发布时间:2020-07-20 23:36:26 作者:上帝之子521
来源:网络 阅读:280

        今天我们来看下排序,那么什么是排序呢?排序是计算机内部经常进行的一种操作,其目的是将一组“无序”的数据元素调整为“有序”的数据元素。那么排序的数学定义时什么呢?如下

选择排序和插入排序(三十)

        下来我们来看一个概念:排序的稳定性。什么是排序的稳定性呢?它是指如果在序列中有两个数据元素 r[i] r[j],它们的关键字 k[i]  == k[j] ,且在排序之前,对象 r[i] 排在 r[j] 前面;如果在排序之后,对象 r[i] 仍在 r[j] 的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。

        下来我们来看看多关键字排序。这个就是在排序时需要比较的关键字多余一个,那么是什么意思呢?就是当排序结果首先按关键字 1 进行排序,当关键字 1 相同时按关键字 2 进行排序;...;当关键字 n-1 相同时按关键字 n 进行排序。对于多关键字排序,我们只需要在比较操作时同时考虑多个关键字即可。下来我们通过一个示例代码来进行分析

#include <iostream>
#include "Object.h"

using namespace std;
using namespace DTLib;

struct Test : public Object
{
    int key1;
    int key2;

    Test(int k1, int k2)
    {
        key1 = k1;
        key2 = k2;
    }

    bool operator ==(const Test& t)
    {
        return (key1 == t.key1) && (key2 == t.key2);
    }

    bool operator !=(const Test& t)
    {
        return !(*this == t);
    }

    bool operator >(const Test& t)
    {
        return (key1 > t.key1) || ((key1 == t.key1) && (key2 > t.key2));
    }

    bool operator <=(const Test& t)
    {
        return !(*this > t);
    }

    bool operator <(const Test& t)
    {
        return (key1 < t.key1) || ((key1 == t.key1) && (key2 < t.key2));
    }

    bool operator >=(const Test& t)
    {
        return !(*this < t);
    }
};

int main()
{
    Test t1(3, 4);
    Test t2(3, 5);
    
    Test t3(2, 4);
    Test t4(1, 2);

    cout << "t1 < t2 : " << (t1 < t2) << endl;
    cout << "t3 > t4 : " << (t3 > t4) << endl;

    return 0;
}

        下来我们来看看输出结果

选择排序和插入排序(三十)

        在上面的示例中,我们看到排序中的关键操作:比较和交换。比较是指任意两个数据元素通过比较操作确定先后次序;交换是指数据元素之间需要交换才能得到预期结果。那么我们在进行排序的时候怎么进行判断这个排序是优是劣呢?从下面三个方面来进行判断。1、时间性能:关键性能差异体现在比较和交换的数量;2、辅助存储空间:为完成排序操作所需要额外的存储空间,必要时可以“空间换时间”;3、算法的实现复杂性:过于复杂的排序法可能影响可读性和可维护性。

        下来我们来看看 DTLib 库中的排序类的设计,如下

选择排序和插入排序(三十)

        我们来基于上面的排序类来进一步实现选择排序和插入排序。

        1、选择排序:它的基本思想是每次(例如第 i 次,i = 0, 1, ..., n-2)从后面 n-i 个待排的数据元素中选出关键字最小的元素,作为有序元素序列第 i 个元素。第 i 次选择排序示例如下

选择排序和插入排序(三十)

        我们来看看具体是怎么实现的,如下所示

选择排序和插入排序(三十)

选择排序和插入排序(三十)

        我们看到是从第一个开始,选出最小的数据元素,后面以此类推,直至最后全部排序完毕。下来我们来具体看看源码是怎样实现的

#ifndef SORT_H
#define SORT_H

#include "Object.h"

namespace DTLib
{

class Sort : public Object
{
private:
    Sort();
    Sort(const Sort&);
    Sort& operator= (const Sort&);

    template <typename T>
    static void Swap(T& a, T& b)
    {
        T c(a);
        a = b;
        b = c;
    }
public:
    template < typename T >
    static void Select(T array[], int len, bool min2max = true)
    {
        for(int i=0; i<len; i++)
        {
            int min = i;

            for(int j=i+1; j<len; j++)
            {
                if(min2max ? (array[min] > array[j]) : (array[min] < array[j]))
                {
                    min = j;
                }
            }

            if( min != i )
            {
                Swap(array[i], array[min]);
            }
        }
    }
};

}

#endif // SORT_H

        测试代码如下

#include <iostream>
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{
    int array[] = {3, 2, 4, 1, 5};

    Sort::Select(array, 5);

    for(int i=0; i<5; i++)
    {
        cout << array[i] << endl;
    }
}

        我们来看看运行结果

选择排序和插入排序(三十)

        我们在代码中默认是从小到大的进行排序,我们在选择排序时,再输入第三个参数 false,看看它是否是从大到小进行排序的

选择排序和插入排序(三十)

        通过上面的排序可知,在排完序后,数据元素的位置已经改动。因此,选择排序是不稳定排序

        2、插入排序:它的基本思想是当插入第 i(i >= 1) 个数据元素时,其那面的 V[0], V[1], ..., V[i-1] 已经排好序;这时,用 V[i] 的关键字与 V[i-1],V[i-2],...,V[0] 的关键字进行比较,找到位置后将 V[i] 插入,原来位置上的对象向后顺移。第 i 次插入排序示例如下

选择排序和插入排序(三十)

        我们来看看具体是怎么实现的,如下所示

选择排序和插入排序(三十)

选择排序和插入排序(三十)

        最后的结果为

选择排序和插入排序(三十)

        我们看到它是通过比较来得出具体位置的。那么我们在下面的代码中直接从后向前来进行比较,具体源码如下

template < typename T >
static void Insert(T array[], int len, bool min2max = true)
{
    for(int i=1; i<len; i++)
    {
        int k = i;
        T e = array[i];

        for(int j=i-1; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j--)
        {
            array[j+1] = array[j];
            k = j;
        }

        if( k != i )
        {
            array[k] = e;
        }
    }
}

        我们来看看使用 Insert 排序方法是否和之前使用 Select 排序方法实现的效果是一样的,结果如下(还是加上 false 参数)

选择排序和插入排序(三十)

        我们看到效果是完全一样的。那么根据上面的方法可知,在进行插入排序时,数据元素的相对顺序不需要改动,因此插入排序是稳定排序。通过对选择排序和插入排序的学习,总结如下:1、排序是数据元素从无序到有序的过程;2、排序具有稳定性,是选择排序算法的因素之一;3、比较和交换是排序的基本操作,多关键字排序与单关键字排序无本质区别;4、排序的时间性能是区分排序算法好坏的主要因素;5、选择排序每次选择未排元素中的最小元素,插入排序每次将第 i 个元素插入前面 i-1 个已排元素中;6、选择排序是不稳定的排序法,插入排序是稳定的排序方法;7、选择排序和插入排序的时间复杂度为 O(n2)。

推荐阅读:
  1. Python3 基本排序算法之冒泡排序,插入排序,选择排序
  2. 插入排序

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

排序 选择排序 插入排序

上一篇:Python 条件语句

下一篇:C#获取应用名称和版本号

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》