-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2019-05-08
来源 ：
阅读 925
评论 0
摘要：本文主要向大家介绍了C/C++知识点之数据结构(11)_排序，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之数据结构(11)_排序，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
定义：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据调整为“有序”的数据元素。
数学定义：假设含有n个数据元素的序列为{R1,R2...Rn},其相应的关键字序列为：{K1,K2...Kn};这些关键字相互之间进行比较，即：在他们之间存在着这样的一个关系：Kp1 <= Kp2 <= ... <= Kpn按此固有关系将上式重新排列为：{Rp1, Rp2, ... Rpn}的操作称为排序。
问题：什么按照总评排序后张无忌的排名比郭靖靠前呢？
排序的稳定性：
如果序列中有两个数据元素Ri和Rj,他们关键字的Ki == Kj，且排序之前，对象Ri排在Rj之前，但排序之后两者的顺序交互，则称这个排序方案是不稳定的。
排序时需要比较的关键字有多个，排序结果首先按照关键字1进行，当关键字1相同，按照关键字2进行排序...
多关键字的排序并不比单关键字复杂，只需要在定义比较操作时，同时考虑多个关键字即可!
多关键字排序实例：
class MulitKeySort : public Object
{protected: int key1; int key2;public:
MulitKeySort(int k1, int k2)
{
key1 = k1;
key2 = k2;
} bool operator ==(const MulitKeySort& m)
{ return ( (key1==m.key1) && (key2==m.key2));
} bool operator !=(const MulitKeySort& m)
{ return !(*this == m);
} bool operator <(const MulitKeySort& m)
{ return ( (key1<m.key1) || ((key1==m.key1) && (key2<m.key2)));
} bool operator >=(const MulitKeySort& m)
{ return !(*this < m);
} bool operator >(const MulitKeySort& m)
{ return ( (key1>m.key1) || ((key1==m.key1) && (key2>m.key2)));
} bool operator <=(const MulitKeySort& m)
{ return !(*this > m);
}
};//测试代码：void test_1(){ MulitKeySort m1(3, 4); MulitKeySort m2(3, 3); cout << (m1 > m2) << endl;
}排序中的关键操作
比较：任意两个数据元素通过比较操作确定先后次序。
交换：数据元素之间需要交换才能得到预期的结果。
排序的选择依据：
时间性能，关键性能差异体现在比较和交换的数量
辅助存储空间：完成排序操作需要额外的存储空间，必要时可以“空间换时间”
算法的实现复杂度：过于复杂的排序算法可能影响可读性和可维护性。
继承自顶层父类Object，并且私有化所有构造途径，将各种排序算法设计为静态成员函数。
class DTSort : public Object
{private:
DTSort();
DTSort(const DTSort&);
DTSort& operator =(const DTSort&);template < typename T >static void Swap(T& a, T& b){ T c(a);
a = b;
b = c;
}
}；基本思想：每次（例如第i次，i=0，1，2...,n-2）从后面n-1个待排列的的数据元素中选出关键字最新的元素，左右有序元素序列的i个元素。
template < typename T >static void SelectSort(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[j]<array[min] : array[j]>array[min])
{
min = j;
}
} if(i != min)
{
Swap(array[i], array[min]);
}
}
}当插入第i(i>=1)个数据元素时，前面的V[0],V[1],...,V[i-1]已经排好序，这时用V[i]的关键字与前i-1个关键字进行比较，找到位置后将V[i]插入，原来位置上的对象向后顺移。
template < typename T >static void InsertSort(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;
}
}
}基本思想：每次从后向前进行（假设为第i次），j=n-1, n-2, ...i, 两两比较V[j-1]和V[j]的关键字；如果发生逆序，则交换V[j-1]和V[j]。
template < typename T >static void BubbleSort(T array[], int len, bool min2max = true) // 稳定， O(n^2){ bool exchange = true; for(int i=0; (i<len) && exchange; i++)
{
exchange = false; for(int j=len-1; j>i; j--)
{ if(min2max ? array[j] < array[j-1] : array[j] > array[j-1])
{
Swap(array[j], array[j-1]);
exchange = true;
}
}
}
}基本思想：将待排序划分为若干组，在每一组进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。
例如:将n个数据元素分成d个子序列：
其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。
template < typename T >static void ShellSort(T array[], int len, bool min2max = true) // 不稳定， O(n^2/3){ int d = len; do
{
d = d / 3 +1; cout << ""d = "" << d << endl; for(int i=d; i<len; i+=d)
{ int k = i;
T e = array[i]; for(int j=i-d; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j-=d) // ...
{ array[j+d] = array[j];
k = j;
} if(k != i)
{ array[k] = e;
}
}
}while(d>1);
}基本思想：将两个或者两个以上的有序序列合并成一个新的有序序列。
这种方法称为二路归并。同理，将N个有序序列归并未一个新有序序列称为N路归并。
template <typename T>static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max){ int i = begin; int j = mid + 1; int k = begin; //辅助空间的起始位置 while( (i<=mid) && (j<=end) )
{ if(min2max ? src[i]<src[j] : src[i]>src[j])
{
helper[k++] = src[i++];
} else
{
helper[k++] = src[j++];
}
} while(i <= mid) // 左路数据有剩余，直接合并入最终序列
{
helper[k++] = src[i++];
} while(j <= end) // ...
{
helper[k++] = src[j++];
} for(int i=begin; i<=end; i++)
{
src[i] = helper[i]; // 将数据拷贝回原来空间
}
}template <typename T>static void Merge(T src[], T helper[], int begin, int end, bool min2max){ if(begin < end) //递归出口
{ int mid = (begin + end) / 2; // 左路数据合并
Merge(src, helper, begin, mid, min2max); // 右路数据合并
Merge(src, helper, mid+1, end, min2max); // 二路归并
Merge(src, helper, begin, mid, end, min2max);
}
}template < typename T >static void MergeSort(T array[], int len, bool min2max = true){ // 申请辅助堆空间
T* helper = new T[len]; cout << ""help: "" << helper <<endl; if(helper != NULL)
{
Merge(array, helper, 0, len-1, min2max);
} delete[] helper;
}基本思想：
任取序列中的某个数据元素作为基准将整个序列划分为左右两个子序列。
左侧子序列中所有数据元素都小于或等于基本元素；
右侧子序列中所有数据元素都大于基准数据元素；
基准元素排列在这两个子序列中间；
分别对这两个子序列重复进行划分，直到所有的数据元素都排在相应的位置上为止。
template <typename T>static int Partion(T array[], int begin, int end, bool min2max){
T pv = array[begin]; while(begin < end)
{ while( (begin<end) && (min2max ? (array[end]>pv) : (array[end]<pv)) )
{
end--;
}
Swap(array[begin], array[end]); while( (begin<end) && (min2max ? (array[begin]<=pv) : (array[begin]>=pv)) )
{
begin++;
}
Swap(array[begin], array[end]);
} return begin;
}template <typename T>static void Quick(T src[], int begin, int end, bool min2max){ if(begin < end) //递归出口
{ //对序列进行区域划分,返回基准元素的位置 int pivot = Partion(src, begin, end, min2max); //对基准左侧的数据元素进行排序
Quick(src, begin, pivot-1, min2max); //对基准右侧的数据元素进行排序
Quick(src, pivot+1, end, min2max);
}
}template < typename T >static void QuickSort(T array[], int len, bool min2max = true){
Quick(array, 0, len-1, min2max);
}快速排序通过递归的方式对排序问题进行划分，时间复杂度为O（n*logn），是一种不稳定的排序法。
在前面的章节中，我们实现了自己的数组类，排序类DTSrot和数组类Array之间存在什么关系？
排序类的实现，不单要考虑对元素数据的排序，也应该支持自定义数据的排序。
新增成员函数：
数组中类中需要提供一个返回元素数据的成员函数函数；
排序类中增加可以实现数组类的成员函数(应该作为之前原生数组排序类的重载版本)；
//使排序算法支持自定义数组类的排序template < typename T >static void SelectSort(Array<T>& array, bool min2max = true){
SelectSort(array.array(), array.length(), min2max);
}template < typename T >static void InsertSort(Array<T>& array, bool min2max = true){
InsertSort(array.array(), array.length(), min2max);
}template < typename T >static void BubbleSort(Array<T>& array, bool min2max = true){
BubbleSort(array.array(), array.length(), min2max);
}template < typename T >static void ShellSort(Array<T>& array, bool min2max = true){
ShellSort(array.array(), array.length(), min2max);
}template < typename T >static void MergeSort(Array<T>& array, bool min2max = true){
MergeSort(array.array(), array.length(), min2max);
}template < typename T >static void QuickSort(Array<T>& array, bool min2max = true){
QuickSort(array.array(), array.length(), min2max);
}问题：当待排序数据元素为体积庞大的对象时，如何提高排序效率？
譬如对下面的对象使用冒泡排序算法进行排序，必然涉及大量的数据交换，严重影响效率。
问题分析：
1.排序过程中不可避免的要进行交换操作，交换操作的本质为数据元素的复制，当数据元素体积较大时，交换操作耗时巨大。
代理模式：
1.为待排序数据元素设置代理对象；
2.对代理对象所组成的序列进行排序
3.需要访问有序数据元素时，通过访问代理序列完成。
struct Test :public Object
{ int id; int data1[1000]; double data2[500]; bool operator < (const Test& obj)
{ return id < obj.id;
} bool operator <= (const Test& obj)
{ return id <= obj.id;
} bool operator >= (const Test& obj)
{ return id >= obj.id;
} bool operator > (const Test& obj)
{ return id > obj.id;
}
};class TestProxy : public Object
{protected:
Test* pTest;public: int id()const { return pTest->id;
} int* data1()const { return pTest->data1;
} double* data2()const { return pTest->data2;
} Test& test()const { return *pTest;
} bool operator >(const TestProxy& obj)
{ return test() > obj.t"本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
