使用模版完成不同数据类型的数组的选择排序

6.模版(167-263)

6.1函数模板

6.1.1函数模版注意事项

6.1.2函数模版案例--选择排序

1. 比较排序的基本概念

2. 决策树

3. 决策树的深度

4. 结论

5.选择排序示例:

6.模版(167-263)

(项目先跳过)

模板不能直接使用,它只是一个框架.
模板不是万能的.

6.1函数模板

建立一个通用函数,其函数返回值类型和形参类型可以不具体指定,用一个虚拟的类型来表示.

语法:

template<typename T>//template声明创建模版 typename表明一种数据类型
其中typename可以用class代替 T可以替换为其他大写字母 但是通常用T
//如果不使用函数模版
void swap(int& a,int &b)
{
int temp = a;
a = b;
b = temp;
}
void swap(double& a,double& b)
{
double temp =a;
a = b;
b = temp;
}
//使用函数模板
template<typename T>
void MySwap(T& a,T& b)
{T temp = a;a = b;b = temp;
}
//使用函数模版的方法
//1.自动类型推导
//2.显示指定类型
MySwap(a,b);
MySwap<int>(a,b);

总结:

模版的目的是为了提高复用性,将类型参数化.

6.1.1函数模版注意事项

自动类型推导,必须推导出一致的数据类型T,才可以使用
模板必须要确定T的数据类型,才可以使用.

6.1.2函数模版案例--选择排序

#include<iostream>
template<typename T>
void chooseSort()
{}

(O(n \log n)) 是比较排序算法（如快速排序、归并排序和堆排序）在最坏情况下时间复杂度的一个理论上限。下面详细解释它是怎么计算出来的：

1. 比较排序的基本概念

在比较排序中，排序过程依赖于比较操作（如大小比较）来确定元素的相对顺序。每次比较只能得出两个元素之间的大小关系，因此我们可以将所有可能的排序视为一个决策树。

2. 决策树

决策树的构建：

每个节点代表一次比较。

每条边代表比较结果（如左边较小，右边较大）。

叶子节点表示一种可能的排序结果。

叶子节点的数量：假设有 (n) 个元素，所有可能的排序方式有 (n!) 种。这意味着决策树必须至少包含 (n!) 个叶子节点。

3. 决策树的深度

树的深度与比较次数：决策树的深度对应于最坏情况下可能需要的比较次数。由于树的每一层最多有 (2) 个分支，如果树的高度为 (h)，那么节点的数量不超过 (2^h)。因此，可以得到：

$2^h \geq n!$

使用斯特灵近似：通过斯特灵近似可以近似估计 (n!)：

$n! \approx \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n$

取对数：为了解决这个不等式，可以取对数： [

$h \cdot \log(2) \geq \log(n!)$

] 结合斯特灵近似： [

$\log(n!) \approx n \log(n) - n$

]

最终得出比较次数：所以，将 (h) 进行估算： [

$h \geq \frac{n \log(n)}{\log(2)} - O(n)$

] 这表明，最坏情况下的比较次数（以及对应的时间复杂度）为： [

$\Theta(n \log n)$

]

4. 结论

综上所述，因为决策树的深度反映了需要的最坏情况下的比较次数，而叶子节点的数量等于 (n!)（所有可能的排序），最终得到的结论是：任何基于比较的排序算法在最坏情况下的时间复杂度不能低于 (O(n \log n))。

5.选择排序示例:

#include <iostream> 
using namespace std;
//利用函数模版实现不同类型的选择排序,将数组中的元素改为从大到小排序
template<typename T>
void Myswap(T& a,T&b)
{T temp = a;a = b;b = temp;
}
template<typename T>
void sort(T arr[],int length)
{for (int i = 0; i < length; i++){T max = arr[i];//think twice before coding. T代表一种数据类型 不能是T[],而是用数组名arr[].for (int j = i + 1; j < length; j++){if (arr[j] > max){max = arr[j];//arr[j] = arr[i];//arr[i] = max;//实际上,也可以这么写:   //i键快速切换搜狗输入法皮肤//但是使用swap会有很多重载函数 推荐使用不和swap重名的函数Myswap(arr[i],arr[j]);}}}
}void test01()
{//注:或者使用sizeof(数组名)/sizeof(数组的数据类型) 得到长度//对int数组进行排序  int a[5] = { 1,3,2,8,4 };sort(a, 5);for (int i = 0; i < 5; i++){cout << a[i] << " " ;}cout << endl;//对字符数组进行排序char b[5] = { 'a','v','d','y','i'};//"awaf";//注意:写成后者的形式最后要加上'\0'的空间sort(b, 5);for (int i = 0; i < 5; i++){cout << b[i] << " ";}cout << endl;//对double进行排序double c[5] = {1.234,457457,23.54,23.33,56.54,};sort(c, 5);for (int i = 0; i < 5; i++){cout << c[i] << " ";}cout << endl;}int main() 
{//只需要开辟一个数组即可 结果存放在txt->excel中 当循环次数足够大时 消除全部重复的结果即可// 输出结果  //int* p = new int[16];//std::cout << "Total unique configurations: "  << std::endl;//delete [] p;test01();return 0;
}

输出结果: