数据结构基础(1) --Swap & Bubble-Sort & Select-Sort

简介: Swap的简单实现//C语言方式(by-pointer):template bool swapByPointer(Type *pointer1, Type *pointer2)...

Swap的简单实现

//C语言方式(by-pointer):
template <typename Type>
bool swapByPointer(Type *pointer1, Type *pointer2)
{
    //确保两个指针不会指向同一个对象
    if (pointer1 == NULL || pointer2 == NULL)
    {
        return false;
    }

    if (pointer1 != pointer2)
    {
        Type tmp = *pointer1;
        *pointer1 = *pointer2;
        *pointer2 = tmp;
    }

    return true;
}

//C++特有方式(by-reference):
template <typename Type>
void swapByReference(Type &value1, Type &value2)
{
    if (value2 != value1)
    {
        Type tmp = value1;
        value1 = value2;
        value2 = tmp;
    }
}

小结:

虽然我们自己实现了swap,但我们还是比较推荐使用C++ STL已经实现好的std::swap()函数,其存在于命名空间std中,使用实例如下面的<冒泡排序>.

  

冒泡排序(Bubble-Sort)

算法思想:

从左到右扫描数据,找出最大的元素,将其放到数组右边;

过程:

循环比较相邻的两个数,如果左边的数比右边的大,则交换两个数;

//实现:注意代码中的三个注意点(x):
template <typename Type>
void bubbleSort(Type *begin, Type *end)
{
    if ((begin == end) || (begin == NULL) || (end == NULL))
        return ;

    int length = end - begin;
    //注意点(1):保证一旦数组有序, 则会直接停止排序, 不会在继续进行无用的循环
    bool isOrder = false;

    //外层循环控制扫描次数(length-1)
    //注意点(2):N个元素其实只需N-1次扫描
    for (int i = 0; !isOrder && i < length-1; ++i)
    {
        //首先假定这次数组已经有序
        isOrder = true;
        //注意点(3):确保能够从0扫描到最后一个未排序的元素
        for (Type *iter = begin; iter < end-i-1; ++iter)
        {
            //如果前面的左边的元素>右边的元素
            if (*iter > *(iter+1))
            {
                //交换
                std::swap(*iter, *(iter+1));
                isOrder = false;
            }
        }
    }
}

template <typename Type>
void bubbleSort(Type *array, int length)
{
    return bubbleSort(array, array+length);
}

选择排序(Select-Sort)

思想:

从当前尚未排序的序列中选择一个最小的元素, 将之放到已排序的序列的队列的末尾;

要点:

1.注意三个指针(inner, outer, miner)所代表的含义;

2.同时注意是从未排序的序列中进行查找最小元素!

//实现
template <typename Type>
void selectSort(Type *begin, Type *end)
{
    if ((begin == end) || (begin == NULL) || (end == NULL))
        return ;

    //只要循环到最后一个元素的前一个就行了,因为剩下的那个肯定是最大的
    for (Type *outer = begin; outer < end-1; ++outer)
    {
        //注意:是从尚未排序的序列中查找(miner = outer, inner = outer+1)
        Type *miner = outer;
        //从miner+1开始遍历数组, 寻找一个元素值小于*miner的
        for (Type *inner = outer+1; inner < end; ++inner)
        {
            if (*inner < *miner)
                miner = inner;
        }

        if (miner != outer)
            std::swap(*miner, *outer);
    }
}

//为了能够让STL的标准容器如vector使用
template <typename Iterator>
void selectSort(Iterator iter1, Iterator iter2)
{
    return selectSort(&(*iter1), &(*iter2));
}

template <typename Type>
void selectSort(Type *array, int length)
{
    return selectSort(array, array+length);
}

小结:

虽然我们自己实现了Bubble-Sort和Select-Sort,但我们在实际软件开发中一般是不会用到的,因为的它的效率为O(N^2),效率太慢^_^, 因此我们还是推荐使用C++ STL中已经实现了的std::sort(), 其内部原理使用了快速排序, 效率为O(logN)速度非常快.

 

附-测试程序

int main()
{
    srand(time(NULL));
    vector<double> dVec;
    int count = 10;
    while (count --)
    {
        dVec.push_back((rand()%1000)/100.0);
    }

    selectSort(dVec.begin(), dVec.end());
    for (vector<double>::iterator iter = dVec.begin(); iter < dVec.end(); ++iter)
    {
        cout << *iter << endl;
    }

    return 0;
}

目录
相关文章
|
存储 人工智能 算法
【数据结构基础】之树的介绍,生动形象,通俗易懂,算法入门必看
【数据结构基础】之树的介绍,生动形象,通俗易懂,算法入门必看
【数据结构基础】之树的介绍,生动形象,通俗易懂,算法入门必看
|
存储 Java
Java基础数组模仿栈数据结构案例
Java基础数组模仿栈数据结构案例
Java基础数组模仿栈数据结构案例
|
存储 算法
常见数据结构-红黑树(上)基础
常见数据结构-红黑树(上)基础
130 0
|
PyTorch 算法框架/工具 异构计算
Pytorch 基础-tensor 数据结构
Pytorch 基础-tensor 数据结构
277 0
|
算法 C++
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(下)
本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(下)
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(中)
本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(中)
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(上)
本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。
算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(上)
算法与数据结构全阶班-左程云版(二)基础阶段之3.归并排序和快速排序(下)
本文主要介绍了两种排序,归并排序和快速排序,归并排序有递归和非递归2种方式实现,快速排序的升级版为荷兰国旗问题。
算法与数据结构全阶班-左程云版(二)基础阶段之3.归并排序和快速排序(下)
算法与数据结构全阶班-左程云版(二)基础阶段之3.归并排序和快速排序(上)
本文主要介绍了两种排序,归并排序和快速排序,归并排序有递归和非递归2种方式实现,快速排序的升级版为荷兰国旗问题。
算法与数据结构全阶班-左程云版(二)基础阶段之3.归并排序和快速排序(上)
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(下)
本文主要介绍了一些常用的数据结构,包括链表、栈、队列、递归、哈希表和有序表。
算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(下)