【C++】通过模板实现一个通用的冒泡排序

左手的ㄟ右手 2022-06-06 08:56 200阅读 0赞

如果让你写一个冒泡法，对一个数组进行排序，你会怎么写呢？

相信你很快就会写出这样的程序

void BubbleSort(int* arr, int size)
    {
    	int i = 0;
    	int j = 0;
    	for (i = 0; i < size - 1; i++)
    	{
    		for (j = 0; j < size - 1 - i; j++)
    		{
    			if (arr[j] > arr[j + 1])
    				swap(arr[j], arr[j + 1]);
    		}
    	}
    }

这是对int类型的数据，进行升序的排列。但是今天我们要实现一个通用的冒泡排序，我们可以让它排序int，排序float, double, string，也可以让它升序或者降序。

template<class T>
    struct Less//降序
    {
    	bool operator()(const T& left, const T& right)
    	{
    		if (left < right)
    			return true;
    		return false;
    	}
    };
    template<>
    struct Less<char*>
    {
    	bool operator()(const char* left, const char* right)
    	{
    		if (strcmp(left,right)<0)
    			return true;
    		return false;
    	}
    };
    template<class T>
    struct Greater//升序
    {
    	bool operator()(const T& left, const T& right)
    	{
    		if (left > right)
    			return true;
    		return false;
    	}
    };
    template<>
    struct Greater<char*>
    {
    	bool operator()(const char* left, const char* right)
    	{
    		if (strcmp(left, right)>0)
    			return true;
    		return false;
    	}
    };
    template <typename T, class Compare>
    void BubbleSort(T* arr, int size)
    {
    	if (arr == NULL)
    		return;
    	bool IsChange = false;//定义一个布尔变量，如果一轮当中没有交换时，说明顺序已将是排好的，直接跳出去
    	for (int i = 0; i < size - 1; i++)
    	{
    		IsChange = false;
    		for (int j = 0; j < size - 1 - i; j++)
    		{
    			if (Compare()(arr[j], arr[j+1]))//升序
    			{
    				IsChange = true;
    				swap(arr[j], arr[j + 1]);
    			}
    		}
    		if (!IsChange)
    			return;
    	}
    }

在上述代码中，我们用模板函数实现了一个通用的冒泡程序，在实现升序和降序的模板类时，我们对char\*类型进行了特化。这是因为，在实现的过程中，我发现通用模板对于string类也是可以完成排序的，这是因为在string类，对大于号和小于号进行了重载，所以我们可以使用大于号和小于号比较两个字符串；而对于char\* 类型，大于号小于号则不能比较字符串了，因此，我对char\*类型进行了特写（虽然可能没什么用，毕竟在C++中，定义一个字符串用string就可以了）。

除此之外，我们还可以不对类特化，而是对排序函数进行特化

template<>
    void BubbleSort<char*, Less<char*>>(char* arr[], int size)
    {
    	if (arr == NULL)
    		return;
    	char* tmp = 0;
    	bool IsChange = false;
    	for (int i = 0; i < size - 1; i++)
    	{
    		IsChange = false;
    		for (int j = 0; j < size - 1 - i; j++)
    		{
    			if (strcmp(arr[j], arr[j + 1]) < 0)
    			{
    				IsChange = true;
    				swap(arr[j], arr[j + 1]);
    			}
    		}
    		if (!IsChange)
    			return;
    	}
    }
    template<>
    void BubbleSort<char*, Greater<char*>>(char* arr[], int size)
    {
    	if (arr == NULL)
    		return;
    	char* tmp = 0;
    	bool IsChange = false;
    	for (int i = 0; i < size - 1; i++)
    	{
    		IsChange = false;
    		for (int j = 0; j < size - 1 - i; j++)
    		{
    			if (strcmp(arr[j], arr[j + 1]) > 0)
    			{
    				IsChange = true;
    				swap(arr[j], arr[j + 1]);
    			}
    		}
    		if (!IsChange)
    			return;
    	}
    }

以下是我的测试函数及测试结果：

void FunTest()
    {
    	string arr1[] = { "aaa", "bbb", "ccc" };
    	BubbleSort<string, Less<string>>(arr1, 3);
    	for (int i = 0; i < 3; i++)
    		cout << arr1[i] << " ";
    	cout << endl;
    
    	char* arr2[] = { "abc", "bbb", "ccc" };
    	BubbleSort<char*, Greater<char*>>(arr2, 3);
    	for (int i = 0; i < 3; i++)
    		cout << arr2[i] << " ";
    	cout << endl;
    
    	double arr3[] = { 7, 4, 1, 8, 5, 2, 9, 6, 3 };
    	BubbleSort<double, Greater<double>>(arr3, 9);
    	for (int i = 0; i < 9; i++)
    		cout << arr3[i] << " ";
    	cout << endl;
    }

![SouthEast][]

[SouthEast]: /images/20220606/15bbe9e7fdd64a748d6ddbbe236d4e75.png