常见的排序算法即排序时间长短（提升版）

痛定思痛。 2023-02-25 07:10 35阅读 0赞

### 文章目录 ###

*  排序算法
 *  归并排序
 *   *  动态图解
     *  算法实现
 *  核心代码
 *  运行结果

# 排序算法 #

排序算法我之前总结过一篇文章，写的也挺详细的`点击链接`[排序算法][Link 1]  
学习了STL之后，再次学习一下排序算法，以及它们的排序一串数所需要的时间大小。

# 归并排序 #

假设初始待排序数据有n个，可以将n个数据看成n个独立的子序列，因此每个子序列的长度为1，然后两两合并，得到\[n/2\]个长度为2或1(注意如果n为奇数时，就会出现多出一个元素无法与其他元素合并)的有序子序列;再两两合并，一种重复下去，直到得到一个长度为n的有序序列为止，这种排序方法为2路排序方法。

## 动态图解 ##

![在这里插入图片描述][20200710200324357.gif]

## 算法实现 ##

合并数组 \_merge  
`l 左边数组的首位置`  
`mid 左边边数组的尾部位置,mid+1 右边数组的首部位置`  
`r 右边数组的尾部`

void _merge(vector<int>& vec, int l, int mid, int r){
        
    	vector<int> tmp(vec.begin() + l, vec.begin() + r + 1);
    	int lk = l;		  //左边的下标位置
    	int rk = mid + 1;	  //右边数组的下标
    
    	for (int i = l; i <= r; i++)
    	{
        
    		//左边数组下标指向end
    		if (lk > mid){
        
    			vec[i] = tmp[rk - l];
    			rk++;
    		}
    		//右边数组下标指向end
    		else if (rk > r){
        
    			vec[i] = tmp[lk - l];
    			lk++;
    		}
    		//判断左右两个数组的大小
    		else if (tmp[lk - l] < tmp[rk - l])
    		{
        
    			vec[i] = tmp[lk - l];
    			lk++;	  //左边的下标归位,右移到下一个位置
    		}
    		else
    		{
        
    			vec[i] = tmp[rk - l];
    			rk++;	  //右边进行右移操作
    		}
    	}
    }
    void _resolve(vector<int>& vec, int l, int r){
        
    	if (l >= r)
    		return;
    	int mid = (l + r) / 2;	//中间分解的下标
    	_resolve(vec, l, mid);		  //递归左边的数据
    	_resolve(vec, mid + 1, r);  //递归右边的数据
    	//递归完了,进行合并
    	_merge(vec, l, mid, r);
    }
    void megerSort(vector<int>& vec){
        
    	_resolve(vec, 0, vec.size() - 1);
    }

# 核心代码 #

#include <functional>
    #include <ctime>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    //冒泡排序
    void bubbleSort(vector<int>& vec){
        
    	for (int i = 0; i < vec.size(); i++){
        
    		for (int j = i + 1; j < vec.size(); j++)
    		{
        
    			if (vec[i] > vec[j])
    			{
        
    				//交换两个变量
    				std::swap(vec[i], vec[j]);
    			}
    		}
    	}
    }
    
    //选择排序
    void selectSort(vector<int>& vec){
        
    	for (int i = 0; i < vec.size(); i++)
    	{
        
    		int min_nums = i;
    		for (int j = i + 1; j < vec.size(); j++)
    		{
        
    			if (vec[j] < vec[min_nums])
    			{
        
    				min_nums = j;
    			}
    		}
    		swap(vec[min_nums], vec[i]);
    	}
    }
    
    //插入排序
    void insertSort(vector<int>& vec){
        
    	for (int i = 0; i < vec.size(); i++)
    	{
        
    		for (int j = i; j > 0; j--)
    		{
        
    			if (vec[j] < vec[j - 1]){
        
    				swap(vec[j], vec[j - 1]);
    			}
    			else{
        
    				break;
    			}
    		}
    	}
    }
    
    ostream& operator<<(ostream& os, const vector<int>& vec){
        
    	for (auto e : vec){
        
    		cout << e << " ";
    	}
    	cout << endl;
    	return os;
    }
    bool sortTest(function<void(vector<int>&)> fn){
        
    	srand(666);	//让随机数是一致的
    	vector<int> vec(10);
    	for (auto& e : vec){
        
    		e = rand() % 20;
    		cout << e << " ";
    	}
    	cout << endl;
    	fn(vec);	//通过传进来的回调函数进行排序
    	cout << vec;
    
    
    	vector<int> big(1000);
    	for (auto& e : big){
        
    		e = (rand() + rand());
    	}
    	cout << "排序:" << big.size() << "大小的数据" << endl;
    	clock_t start = clock();	  //获取程序运行的时间
    
    	fn(big);	  //测试排序时间
    
    
    	clock_t end = clock();	//再次获取程序运行的时间
    	cout << "排序所用时间" << (double)(end - start) / 1000 << "s" << endl;
    	cout << "-------------------------------------------------" << endl;
    	return true;
    }
    void _merge(vector<int>& vec, int l, int mid, int r){
        
    	vector<int> tmp(vec.begin() + l, vec.begin() + r + 1);
    	int lk = l;		  //左边的下标位置
    	int rk = mid + 1;	  //右边数组的下标
    
    	for (int i = l; i <= r; i++)
    	{
        
    		//左边数组下标指向end
    		if (lk > mid){
        
    			vec[i] = tmp[rk - l];
    			rk++;
    		}
    		//右边数组下标指向end
    		else if (rk > r){
        
    			vec[i] = tmp[lk - l];
    			lk++;
    		}
    		//判断左右两个数组的大小
    		else if (tmp[lk - l] < tmp[rk - l])
    		{
        
    			vec[i] = tmp[lk - l];
    			lk++;	  //左边的下标归位,右移到下一个位置
    		}
    		else
    		{
        
    			vec[i] = tmp[rk - l];
    			rk++;	  //右边进行右移操作
    		}
    	}
    }
    
    //stl 库提供的排序算法
    void stl_sort(vector<int>& vec){
        
    	sort(vec.begin(), vec.end());
    }
    //分解数组
    //l  左边的下标
    //r  右边的下标
    void _resolve(vector<int>& vec, int l, int r){
        
    	if (l >= r)
    		return;
    	int mid = (l + r) / 2;	//中间分解的下标
    	_resolve(vec, l, mid);		  //递归左边的数据
    	_resolve(vec, mid + 1, r);  //递归右边的数据
    
    	//递归完了,进行合并
    	_merge(vec, l, mid, r);
    }
    
    //归并排序
    void megerSort(vector<int>& vec){
        
    	_resolve(vec, 0, vec.size() - 1);
    }
    int main()
    {
        
    	cout << "冒泡排序" << endl;
    	sortTest(bubbleSort);	//测试冒泡排序
    
    	cout << "选择排序" << endl;
    	sortTest(selectSort);
    
    	cout << "插入排序" << endl;
    	sortTest(insertSort);
    
    	cout << "归并排序" << endl;
    	sortTest(megerSort);
    
    	cout << "STL排序" << endl;
    	sortTest(stl_sort);
    	system("pause");
    	return 0;
    }

# 运行结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODkzOTk5_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/qq_45893999/article/details/106346438?utm_source=app
[20200710200324357.gif]: /images/20230209/ce2281a2886d492a953c8d787159b223.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODkzOTk5_size_16_color_FFFFFF_t_70]: /images/20230209/aa6fc0db416d4d5398f0b69d45b989c6.png