template <typename T>
T 函數(shù)名(T 參數(shù)1, T 參數(shù)2) {
    // 函數(shù)體
}

// 交換模板
template<typename T>
void swap_T(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}
// 加法模板
template<class T>
T add_T(T a, T b) {
    return a + b;
}

template<typename T>
void test_T() {
    T temp{};        // 值初始化，int為0，double為0.0，自定義類(lèi)調(diào)用默認(rèn)構(gòu)造
    T temp1{0};      // 安全
    // T temp2{0.5}; // 編譯錯(cuò)誤：窄化轉(zhuǎn)換（若T為int）
    temp = 1.5;      // 隱式轉(zhuǎn)換，int會(huì)截?cái)?
}

// 通用模板
template<typename T>
void printArr(T arr[], int len) { ... }
// 針對(duì) int 類(lèi)型的特化 (分隔符變?yōu)?" / ")
template<>
void printArr<int>(int arr[], int len) {
    for (int i = 0; i < len; i++) cout << arr[i] << " / ";
}
// 針對(duì) MyPoint 類(lèi)型的特化 (優(yōu)雅輸出坐標(biāo))
template<>
void printArr(MyPoint arr[], int len) {
    for (int i = 0; i < len; i++) {
        cout << "(" << arr[i].getX() << "," << arr[i].getY() << ")";
    }
}

// 普通函數(shù) (打印int數(shù)組使用逗號(hào)分隔)
void printArr(int arr[], int len) { ... }
// 調(diào)用時(shí)：
printArr(int_arr, num);    // 匹配普通函數(shù) (優(yōu)先級(jí)最高)
printArr<>(int_arr, num);  // 空模板列表強(qiáng)制調(diào)用函數(shù)模板版本 (跳過(guò)普通函數(shù))

template<typename T>
void mySelectionSort_T(T arr[], int len) {
    for (int i = 0; i < len-1; i++) {
        int max = i;
        for (int j = i+1; j < len; j++)
            if (arr[max] < arr[j]) max = j;   // 降序
        if (max != i) swap_T(arr[max], arr[i]);
    }
}

template<typename T>
void myBubbleSort_T(T arr[], int len) {
    for (int i = 0; i < len-1; i++) {
        bool swapped = false;
        for (int j = 0; j < len-1-i; j++) {
            if (arr[j] < arr[j+1]) {  // 降序排列
                swap_T(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

// 1. 泛型交換
template<typename T> void mySwap(T& a, T& b) { T t = a; a = b; b = t; }
// 2. 泛型打印數(shù)組（通用）
template<typename T>
void printArray(const T arr[], size_t len) {
    for (size_t i = 0; i < len; ++i) cout << arr[i] << " ";
}
// 3. 針對(duì)int的特化
template<> void printArray(const int arr[], size_t len) {
    for (size_t i = 0; i < len; ++i) cout << arr[i] << " | ";
}
// 4. 泛型排序算法框架（選擇排序）
template<typename T>
void genericSelectionSort(T arr[], int n) {
    for (int i = 0; i < n-1; ++i) {
        int minIdx = i;
        for (int j = i+1; j < n; ++j)
            if (arr[j] < arr[minIdx]) minIdx = j;
        if (minIdx != i) mySwap(arr[i], arr[minIdx]);
    }
}

// 傳統(tǒng)比較函數(shù)
bool compareInts(int a, int b) {
    return a < b;  // 從小到大
}
// 仿函數(shù)比較器
class CompareInts {
public:
    bool operator()(int a, int b) const {
        return a < b;  // 從小到大
    }
};

template<typename T>
void mySelectionSort_T(T arr[], int len, bool ascending = true) {
    for (int i = 0; i < len-1; i++) {
        int targetIdx = i; // 目標(biāo)位置應(yīng)存放的元素索引
        for (int j = i + 1; j < len; j++) {
            bool condition = ascending ? (arr[j] < arr[targetIdx]) : (arr[j] > arr[targetIdx]);
            if (condition) {
                targetIdx = j;
            }
        }
        if (targetIdx != i) {
            swap_T(arr[targetIdx], arr[i]);
        }
    }
}

mySelectionSort_T(arr, len, SortOrder::DESCENDING);

template<typename T, typename Compare = std::less<T>>
void mySelectionSort_T(T arr[], int len, Compare comp = Compare()) {
    for (int i = 0; i < len-1; i++) {
        int targetIdx = i;
        for (int j = i + 1; j < len; j++) {
            if (comp(arr[j], arr[targetIdx])) { // 使用比較器
                targetIdx = j;
            }
        }
        if (targetIdx != i) {
            swap_T(arr[targetIdx], arr[i]);
        }
    }
}

template<typename T>
concept HasLessThan = requires(const T& a, const T& b) {
    { a < b } -> std::convertible_to<bool>;
};

template <HasLessThan T> // 或者 template <std::totally_ordered T>
void mySelectionSort_T(T arr[], int len) {
    // ... 函數(shù)體內(nèi)部可以安全地使用 arr[j] < arr[targetIdx] ...
}

/// 查找數(shù)組中最大元素的索引
/// @param arr 數(shù)組指針
/// @param len 數(shù)組長(zhǎng)度
/// @return 最大元素的索引，如果數(shù)組為空(len<=0)則返回-1
template<typename T>
int findMax(T arr[], int len) {
    if (len <= 0) return -1; // 處理邊界情況

    int maxIdx = 0; // 假設(shè)第一個(gè)元素最大
    for (int i = 1; i < len; ++i) {
        if (arr[maxIdx] < arr[i]) { // 如果發(fā)現(xiàn)更大的元素
            maxIdx = i; // 更新最大元素索引
        }
    }
    return maxIdx;
}

template<typename T, typename Compare = std::less<T>>
int findMax(T arr[], int len, Compare comp = Compare()) {
    if (len <= 0) return -1;
    int extremeIdx = 0;
    for (int i = 1; i < len; ++i) {
        if (comp(arr[extremeIdx], arr[i])) { // 如果當(dāng)前“極值”排在 arr[i] 之前
            extremeIdx = i; // 更新為新的“極值”
        }
    }
    return extremeIdx;
}
// 使用：findMax(arr, len) 找最大， findMax(arr, len, std::greater<int>()) 找最小。

#include <iostream>
/// <summary>
/// 表示平面坐標(biāo)系中的點(diǎn)的類(lèi)
/// </summary>
class MyPoint {
    double x;
    double y;
public:
    MyPoint(double x, double y) { this->x = x; this->y = y; }
    double getX()const { return x; }
    double getY()const { return y; }
    void show()const { std::cout << '(' << x << ',' << y << ')'; }
};
/// <summary>
/// 打印數(shù)組函數(shù)（模板函數(shù)）
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
/// <param name="len"></param>
template<typename T>
void printArr(T arr[], int len) {
    for (int i = 0; i < len; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}
/// <summary>
/// 打印整型數(shù)組函數(shù)（模板特化）
/// </summary>
/// <param name="arr"></param>
/// <param name="len"></param>
template<>
void printArr<int>(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        std::cout << arr[i] << " / ";
    }
    std::cout << std::endl;
}
/// <summary>
/// 打印坐標(biāo)點(diǎn)數(shù)組函數(shù)（模板特化）
/// 模板的通用性并不是萬(wàn)能的,比如兩個(gè)數(shù)組直接賦值或者自定義數(shù)據(jù)類(lèi)型操作，所以需要特化
/// 有參數(shù)可以自動(dòng)推導(dǎo)為MyPoint類(lèi)型，調(diào)用這個(gè)特化版本來(lái)打印坐標(biāo)點(diǎn)數(shù)組
/// 也可以顯式指定模板參數(shù)為MyPoint，void printArr<MyPoint>(MyPoint arr[], int len)
/// </summary>
/// <param name="arr"></param>
/// <param name="len"></param>
template<>
void printArr(MyPoint arr[], int len) {
    for (int i = 0; i < len; i++) {
        std::cout << "(" << arr[i].getX() << "," << arr[i].getY() << ")";
    }
    std::cout << std::endl;
}
/// <summary>
/// 打印數(shù)組函數(shù)，連接符自定義（模板函數(shù)）
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
/// <param name="len"></param>
/// <param name="hyphen"></param>
template<typename T>
void printArr(T arr[], int len, char hyphen) {
    for (int i = 0; i < len; i++) {
        std::cout << arr[i] << hyphen;
    }
    std::cout << std::endl;
}
/// <summary>
/// 打印數(shù)組函數(shù)，連接符固定為逗號(hào)（普通函數(shù)）
/// 如果函數(shù)模板和普通函數(shù)都可以實(shí)現(xiàn)，優(yōu)先調(diào)用普通函數(shù)
/// 但是提供了函數(shù)模板，最好就不要提供普通函數(shù)，否則容易出現(xiàn)二義性
/// </summary>
/// <param name="arr"></param>
/// <param name="len"></param>
void printArr(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        std::cout << arr[i] << ",";
    }
    std::cout << std::endl;
}
/// <summary>
/// 交換整型函數(shù)
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
void swapInt(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
/// <summary>
/// 整型加函數(shù)
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
int addInt(int a, int b) {
	return a + b;
}
/// <summary>
/// 交換浮點(diǎn)型函數(shù)
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
void swapDouble(double& a, double& b) {
    double temp = a;
    a = b;
    b = temp;
}
/// <summary>
/// 交換函數(shù)（模板函數(shù)）
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
template<typename T>
void swap_T(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}
/// <summary>
/// 加函數(shù)（模板函數(shù)）
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
template<class T>
T add_T(T a, T b)
{
    return a + b;
}
/// <summary>
/// 無(wú)參數(shù)模板函數(shù)測(cè)試
/// </summary>
/// <typeparam name="T"></typeparam>
template<typename T>
void test_T() {
	//初始化T類(lèi)型的變量，使用{}值初始化
    //1. 安全性第一：防止未初始化變量
    //2. 防止窄化轉(zhuǎn)換（編譯時(shí)錯(cuò)誤）
    //3. 統(tǒng)一性：一套語(yǔ)法適用于所有類(lèi)型
    //4. 區(qū)分函數(shù)聲明和對(duì)象構(gòu)造
    //5. 清晰的語(yǔ)義表達(dá)
    //6. 模板的通用性：適用更多類(lèi)型（例如自定義類(lèi)、指針、僅有 explicit構(gòu)造函數(shù)的類(lèi)型等）
    T temp{};
    std::cout << "測(cè)試：" << temp << std::endl;
    T temp1{0};
    std::cout << "測(cè)試：" << temp << std::endl;
    //T temp2{0.5};//從“double”轉(zhuǎn)換到“int”需要收縮轉(zhuǎn)換
	//T的類(lèi)型由顯示指定，而不是自動(dòng)類(lèi)型推導(dǎo)，所以T的類(lèi)型不是浮點(diǎn)型，而是int類(lèi)型
    temp = 1.5;
    std::cout << "測(cè)試：" << temp << std::endl;
}
/// <summary>
/// 測(cè)試函數(shù)
/// </summary>
void test1() {
    std::cout << "==============================================================" << std::endl;
    std::cout << "函數(shù)模板封裝交換函數(shù)測(cè)試：" << std::endl;
    int a = 10;
    int b = 20;
    char c = 'c';//'c' 對(duì)應(yīng) ASCII碼 99
    double d = 0.5;
	std::cout << "交換前：a = " << a << ", b = " << b << ", c = " << c << ", d = " << d << std::endl;
    std::cout << "=== 普通函數(shù) ===" << std::endl;
	//普通函數(shù)交換
    swapInt(a, b);
	std::cout << "交換后：a = " << a << ", b = " << b << std::endl;
	//隱式轉(zhuǎn)換允許不同類(lèi)型的變量交換
    //swapInt(a, c);// 引用傳遞 - 不允許隱式類(lèi)型轉(zhuǎn)換，引用應(yīng)該對(duì)原變量的直接操作，而轉(zhuǎn)換會(huì)產(chǎn)生臨時(shí)變量
    //但是const引用允許隱式轉(zhuǎn)換,const引用是只讀的，綁定到臨時(shí)變量是安全的，因?yàn)椴粫?huì)修改它。
    std::cout  << a << "+ " <<c << "= " << addInt(a, c) << std::endl;// 值傳遞 - 允許隱式類(lèi)型轉(zhuǎn)換
    std::cout << "=== 有參數(shù)版本（可以自動(dòng)推導(dǎo)）===" << std::endl;
	//模板函數(shù)交換
    swap_T(a, b);
	std::cout << "交換后：a = " << a << ", b = " << b << std::endl;
	//顯示指定類(lèi)型
    swap_T<int>(a, b);
	std::cout << "交換后：a = " << a << ", b = " << b << std::endl;
    //swap_T<int>(a, d);//引用傳遞同樣不允許隱式類(lèi)型轉(zhuǎn)換
    //隱式轉(zhuǎn)換
    std::cout << "相加：a = " << a << ", d = " << d << std::endl;
    std::cout << a << "+ " << d << "= " << add_T<int>(a, d) << std::endl;//顯式指定，可以隱式轉(zhuǎn)換
    //std::cout << a << "+ " << d << "= " << add_T(a, d) << std::endl;//自動(dòng)推導(dǎo)，不可以隱式轉(zhuǎn)換
	//自動(dòng)類(lèi)型推導(dǎo)不允許不同類(lèi)型的變量
    // 推導(dǎo)過(guò)程：
    //1. 看第一個(gè)參數(shù)a → T必須與a類(lèi)型匹配 → T = int
    //2. 看第二個(gè)參數(shù)d → T必須與d類(lèi)型匹配 → T = double
    //3. 矛盾！T不能既是int又是double
    //4. 推導(dǎo)失敗，編譯錯(cuò)誤
    //swap_T(a, d);
    std::cout << "=== 無(wú)參數(shù)版本（必須顯式指定）===" << std::endl;
	//必須顯式指定類(lèi)型
    //test_T();
    test_T<int>();
    std::cout << "==============================================================" << std::endl;
}
/// <summary>
/// 選擇排序函數(shù)（模板函數(shù)）
/// 不穩(wěn)定排序，可能改變相同元素相對(duì)順序，因?yàn)闀?huì)遠(yuǎn)距離交換
/// 時(shí)間復(fù)雜度：始終O(n2)
/// 空間復(fù)雜度：O(1)原地排序
/// 比較次數(shù)?：固定：n(n - 1) / 2
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
/// <param name="len"></param>
template<typename T>
void mySelectionSort_T(T arr[],int len) {
    // 外層循環(huán)：控制放置位置
    for (int i = 0; i < len-1; i++) {
        int max = i;
        // 內(nèi)層循環(huán)：從前往后在未排序部分尋找最大值
        for (int j = i + 1; j < len; j++) {
            if (arr[max] < arr[j]) {
                max = j;
            }
        }
        std::cout << "i = " << i << ", max = " << max << std::endl;
        // 內(nèi)層循環(huán)結(jié)束后，交換一次，每次都挑出最大值
        if (max != i) {
            swap_T(arr[max], arr[i]);
            std::cout << "交換：" << std::endl;
            printArr(arr, len);
        }
    }
}
/// <summary>
/// 冒泡排序函數(shù)（模板函數(shù)）
/// 穩(wěn)定排序，不改變相同元素相對(duì)順序，因?yàn)橹粫?huì)相鄰交換
/// 時(shí)間復(fù)雜度：平均O(n2)，最優(yōu)O(n)
/// 空間復(fù)雜度：O(1)原地排序
/// 比較次數(shù)?：平均n(n-1)/2，最優(yōu)n-1
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
/// <param name="len"></param>
template<typename T>
void myBubbleSort_T(T arr[], int len) {
    // 外層循環(huán)：控制冒泡輪數(shù)
    for (int i = 0; i < len-1; i++) {
        bool swapped = false;//退出邏輯優(yōu)化
        // 內(nèi)層循環(huán)：從后往前每輪減少比較范圍執(zhí)行相鄰比較
        for (int j = 0; j < len-1-i; j++) {
            //每輪內(nèi)循環(huán)：讓一個(gè)小氣泡上浮到水面（從大到小排序）
            std::cout << "i = " << i << ", j = " << j << std::endl;
            if (arr[j] < arr[j+1]) {
                //立即交換
                swap_T(arr[j], arr[j+1]);
                swapped = true;
                std::cout << "交換：" << std::endl;
                printArr(arr, len);
            }
        }
        if (!swapped) {
            break;//如果沒(méi)有交換，說(shuō)明已經(jīng)有序，提前退出
            std::cout << "已經(jīng)有序，提前退出" << std::endl;
        }
    }
}
/// <summary>
/// 測(cè)試函數(shù)
/// </summary>
void test2() {
    std::cout << "==============================================================" << std::endl;
    std::cout << "函數(shù)模板封裝選擇排序函數(shù)，char數(shù)組測(cè)試："<< std::endl;
	char char_arr[] = "hello world";//雙引號(hào)括起的字符串會(huì)自動(dòng)在末尾添加空字符'\0'，所以長(zhǎng)度12
    int num = sizeof(char_arr) / sizeof(char);
    std::cout << "輸入數(shù)組元素?cái)?shù)量：" << num << std::endl;
    //函數(shù)模板重載測(cè)試
    printArr(char_arr, num);
    printArr(char_arr, num,'-');
    mySelectionSort_T(char_arr, num);
    printArr(char_arr, num);
    std::cout << "==============================================================" << std::endl;
}
/// <summary>
/// 測(cè)試函數(shù)
/// </summary>
void test3() {
    std::cout << "==============================================================" << std::endl;
    std::cout << "函數(shù)模板封裝選擇排序函數(shù)，int數(shù)組測(cè)試：" << std::endl;
    //int int_arr[] = {7,5,3,1,5,9,4,5,6,8,5,2 };
    int int_arr[] = { 1,2,3,4 };
    int num = sizeof(int_arr) / sizeof(int);
    std::cout << "輸入數(shù)組元素?cái)?shù)量：" << num << std::endl;
    printArr<>(int_arr, num);//空模板參數(shù)列表來(lái)強(qiáng)制調(diào)用函數(shù)模板
    mySelectionSort_T(int_arr, num);
    printArr(int_arr, num);
    std::cout << "==============================================================" << std::endl;
}
/// <summary>
/// 測(cè)試函數(shù)
/// </summary>
void test4() {
    std::cout << "==============================================================" << std::endl;
    std::cout << "函數(shù)模板封裝冒泡排序函數(shù)，int數(shù)組測(cè)試：" << std::endl;
    //int int_arr[] = {7,5,3,1,5,9,4,5,6,8,5,2 };
    int int_arr[] = { 1,2,3,4 };
    int num = sizeof(int_arr) / sizeof(int);
    std::cout << "輸入數(shù)組元素?cái)?shù)量：" << num << std::endl;
    printArr(int_arr, num);
    myBubbleSort_T(int_arr, num);
    printArr(int_arr, num);
    std::cout << "==============================================================" << std::endl;
}
/// <summary>
/// 測(cè)試函數(shù)
/// 函數(shù)調(diào)用優(yōu)先級(jí)：
/// 1.完全匹配的普通函數(shù)（最高優(yōu)先級(jí)）
/// 2.模板特化
/// 3.函數(shù)模板
/// 4.隱式轉(zhuǎn)換的普通函數(shù)（最低優(yōu)先級(jí)）
/// </summary>
void test5() {
    std::cout << "==============================================================" << std::endl;
    std::cout << "函數(shù)調(diào)用優(yōu)先級(jí)測(cè)試：" << std::endl;
    int int_arr[] = { 1,2,3,4 };
    int num1 = sizeof(int_arr) / sizeof(int);
    std::cout << "輸入數(shù)組元素?cái)?shù)量：" << num1 << std::endl;
    printArr(int_arr, num1);
    printArr<>(int_arr, num1);//空模板參數(shù)列表來(lái)強(qiáng)制調(diào)用函數(shù)模板
	MyPoint point_arr[] = { MyPoint(1,2), MyPoint(3,4), MyPoint(5,6) };
    int num2 = sizeof(point_arr) / sizeof(MyPoint);
    std::cout << "輸入數(shù)組元素?cái)?shù)量：" << num2 << std::endl;
    printArr(point_arr, num2);
    std::cout << "==============================================================" << std::endl;
}
int main()
{
	//調(diào)用測(cè)試函數(shù)
    test1();
    test2();
    test3();
    test4();
    test5();
	//等待用戶(hù)輸入
    system("pause");
	//返回0表示程序正常結(jié)束
    return 0;
}