581-冒泡&选择&插入&希尔算法性能统计

柔光的暖阳◎ 2022-09-12 00:59 120阅读 0赞

## 性能测试代码 ##

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    
    
    //希尔排序
    void ShellSort(int arr[], int size)
    {
        
    	for (int gap = size / 2; gap > 0; gap /= 2)//100W 19 1000W 24
    	{
        
    		for (int i = gap; i < size; i++)//O(n)i++:所有组都是要处理的 
    		{
        
    			int val = arr[i]; 
    			int j = i - gap;
    			for (; j >= 0; j-=gap)//O(n) 
    			{
        
    				if (arr[j] <= val)
    				{
        
    					break;
    				}
    				arr[j + gap] = arr[j];
    			}
    			arr[j + gap] = val;
    		}
    	}
    }   
    
    //插入排序算法  时间复杂度: 最坏、平均 O(n^2)  最好：O(n)  空间：O(1)  稳定性：稳定的
    void InsertSort(int arr[], int size)
    {
        
    	for (int i = 1; i < size; i++)//O(n) <size，因为最后一个元素也是要处理的 
    	{
        
    		int val = arr[i];
    		//此趟未排序序列的首位置的值，因为每一趟处理，无序序列少1个元素 ，前面的有序序列多1个元素 
    		int j = i - 1;//前面有序序列的末尾元素的下标 
    		for (; j >= 0; j--)//O(n)
    		{
        
    			if (arr[j] <= val)//找第一个小于等于val的值 
    			{
        
    				break;
    			}
    			arr[j + 1] = arr[j];//把当前元素往后挪动 
    		}
    		arr[j + 1] = val;//放到第一个小于等于val的元素的后面 
    	}
    }
    
    //选择排序算法 O(n) * O(n) = O(n^2) 空间复杂度： O(1)   稳定性：不稳定    
    //5 5 3
    void ChoiceSort(int arr[], int size)
    {
        
    	for (int i = 0; i < size - 1; i++)//O(n) 趟数 
    	{
        
    		int min = arr[i];//min初始化为当前序列的首位置元素
    		int k = i;//当前序列的首位置初始化为当前序列的最小值的下标 
    		for (int j = i+1; j < size; j++)//O(n) 遍历当前序列 
    		{
        
    			if (arr[j] < min)
    			{
        
    				min = arr[j];//更新当前序列的最小值min 
    				k = j;//更新当前序列的最小值的下标 
    			}
    		}
    		//如果k=i，说明当前序列的首位置的元素就是最小的，就不用交换了 
    		if (k != i)//k!=i，当前序列的最小值和当前序列的首位置元素交换 
    		{
        
    			int tmp = arr[i];
    			arr[i] = arr[k];
    			arr[k] = tmp;
    		}
    	}
    }
    
    //冒泡排序算法
    void BubbleSort(int arr[], int size)
    {
        
    	for (int i = 0; i < size-1; i++)//趟数  O(n) * O(n) = O(n^2)
    	{
        
    		bool flag = false;
    		//一趟的处理   
    		for (int j = 0; j < size - 1 - i; j++)//O(n)//size-1，是因为是j和j+1比较 
    		{
        
    			if (arr[j] > arr[j + 1])
    			{
        
    				int tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = tmp;
    				flag = true;
    			}
    		}
    
    		if (!flag)//冒泡排序算法的优化之处 
    		{
        
    			//如果没有做任何的数据交换，那么说明数据已经有序了，就不用继续走后面的趟了 
    			return;
    		}
    	}
    }
    
    int main()
    {
        
    	const int COUNT = 100000;
    	int* arr = new int[COUNT];
    	int* brr = new int[COUNT];
    	int* crr = new int[COUNT];
    	int* drr = new int[COUNT];
    
    	srand(time(NULL));
    
    	for (int i = 0; i < COUNT; i++)
    	{
        
    		int val = rand() % COUNT;
    		arr[i] = val;
    		brr[i] = val;
    		crr[i] = val;
    		drr[i] = val;
    	}
    
    	clock_t begin, end;//返回大致的程序运行时所消耗的CPU的时间 
    
    	begin = clock();//记录当前的时间戳 
    	BubbleSort(arr, COUNT);//冒泡排序 
    	end = clock();//记录当前的时间戳 
    	cout << "BubbleSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    
    	begin = clock();
    	ChoiceSort(brr, COUNT);//选择排序 
    	end = clock();
    	cout << "ChoiceSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    
    	begin = clock();
    	InsertSort(crr, COUNT);//插入排序 
    	end = clock();
    	cout << "InsertSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    
    	begin = clock();
    	ShellSort(drr, COUNT);//希尔排序 
    	end = clock();
    	cout << "ShellSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    }

## 性能测试结果 ##

![在这里插入图片描述][5b57e16754b945c99ee7aaacc5659ec6.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

[5b57e16754b945c99ee7aaacc5659ec6.png]: /images/20220828/48b77c3faefb446fb7e5b8ff23902cee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f823c02c0f734539bde1c90521284b70.png