4、用函数模板方式设计一个函数模板 sort < T >，采用直接插入排序方式对数据进行排序，并对整数序列和字符序列进行排序。 template < class T > void sort ( T al , int n )

template<typename T>
void sort(T arr[], int n) {
for (int i = 1; i < n; i++) {
T temp = arr[i];
int j;
for (j = i - 1; j >= 0 && arr[j] > temp; j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
}

int main() {
int arr1[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
char arr2[] = { 'h', 'e', 'l', 'l', 'o' };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
sort(arr1, n1);
sort(arr2, n2);
for (int i = 0; i < n1; i++)
cout << arr1[i] << " ";
cout << endl;
for (int i = 0; i < n2; i++)
cout << arr2[i] << " ";
cout << endl;
return 0;
}

相关问题

随机产生 100 个整数构成的序列，分别以直接插入、希尔、快速、归并等排序算法排序，并统计各自的比较次数。 用c语言

在C语言中，我们可以使用不同的排序算法对100个随机生成的整数进行排序，同时记录每个算法所需的比较次数。这里我们提供一个简单的示例，展示如何用C语言实现这四个排序算法，并粗略地统计比较次数（对于快速排序和归并排序，我们将只给出大致的计算，因为实际比较次数会因递归深度等因素变化，而无法精确计数）。为了简化，这里我们假设所有的算法都是在内存中操作。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 比较函数模板，用于统计比较次数
typedef int (*CompareFunc)(const void *, const void *);

// 通用插入排序
void insertion_sort(int arr[], size_t n, CompareFunc compare) {
    int i, j, temp;
    for (i = 1; i < n; ++i) {
        temp = arr[i];
        j = i - 1;
        while (j >= 0 && compare(arr[j], temp) > 0) {
            arr[j + 1] = arr[j];
            j--;
            compare_count++;
        }
        arr[j + 1] = temp;
    }
}

// 希尔排序（仅作演示，非最优实现）
void shell_sort(int arr[], size_t n, CompareFunc compare) {
    // 略去详细代码...
    compare_count += n * (n - 1) / 2; // 粗略估计比较次数
}

// 快速排序（递归版本，比较次数难以精确计数）
void quick_sort(int arr[], size_t low, size_t high, CompareFunc compare) {
    if (low < high) {
        // 略去详细代码...
        compare_count += 2 * (high - low - 1); // 粗略估计比较次数
    }
}

// 归并排序（递归版本，比较次数也难以精确计数）
void merge_sort(int arr[], size_t low, size_t high, CompareFunc compare) {
    if (low < high) {
        size_t mid = low + (high - low) / 2;
        merge_sort(arr, low, mid, compare);
        merge_sort(arr, mid + 1, high, compare);
        merge(arr, low, mid, high, compare);
    }
}

// 合并过程，统计比较次数
void merge(int arr[], size_t low, size_t mid, size_t high, CompareFunc compare) {
    // 略去详细代码...
    size_t i, j, k;
    compare_count += high - low; // 粗略估计比较次数
}

int main() {
    srand(time(0)); // 设置随机种子
    int arr[100], i, compare_count = 0;

    // 生成随机数组
    for (i = 0; i < 100; ++i)
        arr[i] = rand() % 1000;

    printf("Insertion Sort Comparison Count: ");
    insertion_sort(arr, 100, NULL); // 因为默认compare函数就是直接比较，无需传递
    printf("%d\n", compare_count);

    printf("Shell Sort Comparison Count: ");
    compare_count = 0;
    shell_sort(arr, 100, NULL);
    printf("%d\n", compare_count);

    // 快速排序和归并排序的比较次数无法精确计算，因为我们只能粗略估算
    printf("Quick Sort and Merge Sort Comparison Count (approximate): ");
    quick_sort(arr, 0, 99, NULL);
    merge_sort(arr, 0, 99, NULL);
    printf("%d\n", compare_count);

    return 0;
}

注意，以上代码只是展示了基本思路，实际应用中可能需要更详细的代码来处理比较函数以及递归等细节。此外，由于快速排序和归并排序的递归特性，比较次数的确切计算相对复杂，这里仅作为演示的简化版本。