587-希尔&快排&归并&堆排-性能测试

喜欢ヅ旅行 2022-08-28 13:56 182阅读 0赞

## 希尔&快排&归并&堆排-性能测试 ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    //堆的下沉调整
    void siftDown(int arr[], int i, int size)
    {
        
    	int val = arr[i];
    	while (i < size / 2)
    	{
        
    		int child = 2 * i + 1;
    		if (child + 1 < size && arr[child + 1] > arr[child])
    		{
        
    			child = child + 1;
    		}
    
    		if (arr[child] > val)
    		{
        
    			arr[i] = arr[child];
    			i = child;  // i继续指向它的孩子，继续调整
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	arr[i] = val;
    }
    
    //堆排序
    void HeapSort(int arr[], int size)
    {
        
    	int n = size - 1;
    	//从第一个非叶子节点
    	for (int i = (n - 1) / 2; i >= 0; i--)
    	{
        
    		siftDown(arr, i, size);
    	}
    
    	//把堆顶元素和末尾元素进行交换，从堆顶开始进行下沉操作
    	for (int i = n; i > 0; i--)
    	{
        
    		int tmp = arr[0];
    		arr[0] = arr[i];
    		arr[i] = tmp;
    
    		siftDown(arr, 0, i);//第三个参数，参与调整的元素的个数
    	}
    }
    
    //归并过程函数  O(n)
    void Merge(int arr[], int l, int m, int r, int *p)
    {
        
    	int idx = 0;
    	int i = l;
    	int j = m + 1;
    
    	while (i <= m && j <= r)
    	{
        
    		if (arr[i] <= arr[j])
    		{
        
    			p[idx++] = arr[i++];
    		}
    		else
    		{
        
    			p[idx++] = arr[j++];
    		}
    	}
    
    	while (i <= m)
    	{
        
    		p[idx++] = arr[i++];
    	}
    
    	while (j <= r)
    	{
        
    		p[idx++] = arr[j++];
    	}
    
    	//再把合并好的大段有序的结果，拷贝到原始arr数组[l,r]区间内
    	for (i = l, j = 0; i <= r; i++, j++)
    	{
        
    		arr[i] = p[j];
    	}
    }
    
    //归并排序递归接口
    void MergeSort(int arr[], int begin, int end, int *p)
    {
        
    	//递归结束的条件
    	if (begin >= end)
    	{
        
    		return;
    	}
    
    	int mid = (begin + end) / 2;
    	// 先递
    	MergeSort(arr, begin, mid, p);
    	MergeSort(arr, mid + 1, end, p);
    	// 再归并  [begin, mid]  [mid+1, end] 把两个小段有序的序列，合并成大段有序的序列
    	Merge(arr, begin, mid, end, p);
    }
    
    //归并排序
    void MergeSort(int arr[], int size)
    {
        
    	int* p = new int[size];  // O(n)
    	MergeSort(arr, 0, size - 1, p);
    	delete[]p;
    }
    
    //快排分割处理函数
    int Partation(int arr[], int l, int r)
    {
        
    	//选择基准数的优化：“三数取中”法   arr[l]   arr[r]   arr[(l+r)/2]  
    	//记录基准数
    	int val = arr[l];
    
    	//一次快排处理   时间：O(n) * O(logn) = O(nlogn)    空间：O(logn) 递归的深度所占用的栈内存
    	while (l < r)
    	{
        
    		while (l < r && arr[r] > val)
    		{
        
    			r--;
    		}
    
    		if (l < r)
    		{
        
    			arr[l] = arr[r];
    			l++;
    		}
    
    		while (l < r && arr[l] < val)
    		{
        
    			l++;
    		}
    
    		if (l < r)
    		{
        
    			arr[r] = arr[l];
    			r--;
    		}
    	}
    
    	//l == r的位置，就是放基准数的位置
    	arr[l] = val;
    	return l;
    }
    
    //快排的递归接口
    void QuickSort(int arr[], int begin, int end)
    {
        
    	if (begin >= end)//快排递归结束的条件
    	{
        
    		return;
    	}
    
    	//优化一：当[begin, end]序列的元素个数小到指定数量，采用插入排序
    	//if (end - begin <= 50)
    	//{
        
    		// InsertSort(arr, begin, end);
    		//return;
    	//}
    
    	//在[begin, end]区间的元素做一次快排分割处理
    	int pos = Partation(arr, begin, end);
    
    	//对基准数的左边和右边的序列，再分别进行快排
    	QuickSort(arr, begin, pos - 1);
    	QuickSort(arr, pos + 1, end);
    }
    
    //快速排序
    void QuickSort(int arr[], int size)
    {
        
    	return QuickSort(arr, 0, size - 1);
    }
    
    //希尔排序
    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)
    		{
        
    			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;
    		}
    	}
    }
    
    int main()
    {
        
    	cout << RAND_MAX << endl;
    
    	const int COUNT = 100000000;
    	int* arr = new int[COUNT];
    	int* brr = new int[COUNT];
    	/*int* crr = new int[COUNT];
    	int* drr = new int[COUNT];*/
    
    	srand(time(NULL));
    
    	//0 - 32767    32768 - 32768+32767 
    	for (int i = 0; i < COUNT; i++)
    	{
        
    		int val = rand() % COUNT;  // 0 - 32767
    		arr[i] = val;
    	}
    
    	clock_t begin, end;
    
    	memcpy(brr, arr, COUNT * sizeof(int));
    
    	begin = clock();
    	QuickSort(brr, COUNT);//快排 
    	end = clock();
    	cout << "QuickSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    
    	memcpy(brr, arr, COUNT * sizeof(int));
    
    	begin = clock();
    	MergeSort(brr, COUNT);//归并 
    	end = clock();
    	cout << "MergeSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    
    	memcpy(brr, arr, COUNT * sizeof(int));
    
    	begin = clock();
    	ShellSort(brr, COUNT);//希尔 
    	end = clock();
    	cout << "ShellSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    	
    	memcpy(brr, arr, COUNT * sizeof(int));
    
    	begin = clock();
    	HeapSort(brr, COUNT);//堆排 
    	end = clock();
    	cout << "HeapSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
我们测出：  
**快排的速度是最快的，其次是归并排序，然后是希尔排序，最后是堆排序**

**我们堆排和快排的差距怎么大呢？平均时间复杂度都一样呢**

**归并和快排的处理操作很相似**，但是归并要开辟额外的内存空间，存放当前合并的有序的序列，然后拷贝到原始的序列中，这就是归并比快排慢一点点的地方。快排的最坏时间复杂度是O(n^2)，但是场景是有序的序列，现实中数据量很大，有序的概率是非常低的。  
**希尔排序是对插入排序的优化**，尤其是序列趋于有序的情况下，效率很高，但是在乱序的场景下，效率低于快排和归并排序。

**堆排排序的在最坏最好和平均，时间复杂度都是O(nlogn）**  
但是排序是不稳定的。  
**但是它和快排差很多，为什么？**  
因为  
![在这里插入图片描述][d8b7372de97e4517ab6aa1e7fcd6172c.png]  
CPU在从内存上加载数据的时候，并不是指令操作什么数据，它就加载什么数据。往往是根据程序的局部性运行原理，当你不管是访问指令，还是访问数据，访问当前这一条指令或者数据，接下来很有可能访问相邻的指令或者数据，所以，当CPU从内存上加载指令或者数据的时候，它会把这个指令或者数据以及相邻的指令或者数据都加载到CPU里面，当前用到的会放入CPU寄存器或者直接进入CPU的逻辑运算单元进行运算，马上会用到的都会放到CPU的缓存里，当下一次再去取相应指令或者数据的时候，如果缓存中有，就直接从缓存取，不用去内存取，缓存取的效率高于内存取。

![在这里插入图片描述][f308c2e727ef438dbf4a54ab0ca2b48c.png]  
**也就是说，进行加载的时候，堆排更多是从内存取，而快排和归并排序是更多从缓存取。**  
缓存只是内存连续的一段数据，加载到CPU上。

**大根堆的末尾节点本来值就比较小，然后每一趟都和堆顶元素交换，然后因为值本身就小，然后下沉肯定很多，要进行很多次的比较，要进行很多次的交换**  
![在这里插入图片描述][581df2a3f10d4e31a37279756380926a.png]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f9a9e43c755c4cb7b3108de9a50b41c0.png
[d8b7372de97e4517ab6aa1e7fcd6172c.png]: /images/20220828/43905f7c4294475c9bb5dfc73c632ede.png
[f308c2e727ef438dbf4a54ab0ca2b48c.png]: /images/20220828/7fe9398a15d647a386fc77d1b4b75cfb.png
[581df2a3f10d4e31a37279756380926a.png]: /images/20220828/6ae162c95fd6434eb29328a8f7c9a369.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9e353bce157f4cc08bb1c74d6ea81bfb.png