您好,登录后才能下订单哦!
今天我们来看下排序,那么什么是排序呢?排序是计算机内部经常进行的一种操作,其目的是将一组“无序”的数据元素调整为“有序”的数据元素。那么排序的数学定义时什么呢?如下
下来我们来看一个概念:排序的稳定性。什么是排序的稳定性呢?它是指如果在序列中有两个数据元素 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)。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。