C/C++数据结构与算法--快速排序

爱被打了一巴掌 2022-10-09 12:13 211阅读 0赞

# 数据结构与算法–快速排序&冒泡排序 #

\*\*导言：\*\*数据结构是算法的基础，可以说算法就是构建在数据结构上的一种程序员思想的体现。  
我们需要解决一个问题，首先就是将这个问题进行抽象，抽象成一种数据结构，之后用我们所学过的知识，来构建解决这个问题的步骤，也就是问题解决的算法，我们在学习数据结构与算法时最常见的算法有查找算法、排序算法，在排序算法中，最长用到的算法就是快速排序算法，下面我们来介绍排序算法，且使用一个随时间生成的随机矩阵来测试快速排序对不同数量的数组元素的排序时间。  
为了能够明显看出快速排序之快，我们来吊打一下冒泡排序

# 快速排序 #

## 代码 ##

#include <iostream>
    #include <ctime>
    #include <sys/timeb.h>
    using namespace std;
    
    
    class Sort { 
    public:
    	Sort() { }
    	~Sort() { }
    
    	//成员函数
    public:
    	void QuickSort( int* marray, int low, int high);
    private:
    	int Partition( int* marray, int low, int high);
    };
    
    //快速排序
    void Sort::QuickSort( int* marray, int low, int high)
    { 
    	if (low < high)
    	{ 
    		int tempIndex = Partition(marray, low, high);
    		QuickSort(marray, low, tempIndex - 1);//左边
    		QuickSort(marray, tempIndex + 1, high);//右边
    	}
    }
    
    
    int Sort::Partition(int* marray, int low, int high)
    { 
    	int temp = marray[low];//将左边第一个元素作为基准元素
    	while (low < high)
    	{ 
    		while (high > low && marray[high] >= temp)
    		{ 
    			high--;
    		}
    		marray[low] = marray[high];
    
    		while (low < high && marray[low] <= temp)
    		{ 
    			low++;
    		}
    		marray[high] = marray[low];
    	}
    
    	marray[low] = temp;
    	
    	return low;//返回当前基准元素的下标位置
    }
    
    
    //打印整个数组元素
    void PrintArray(int* marray, int nums)
    { 
    	//循环打印数组中的所有元素
    	for (int ix = 0; ix < nums; ix++)
    	{ 
    		cout << marray[ix] << " ";
    	}
    	cout << endl;
    }
    
    //创建一个随时间变化的随机数组
    void CreateRandomArray(int scale, int* mArray)
    { 
    	const int valScale = scale + 1;
    	srand((unsigned int)time(NULL));//生成一个随机数种子
    	for (int ix = 0; ix < scale; ix++)
    	{ 
    		mArray[ix] = rand() % valScale;
    	}
    }
    
    long int main()
    { 
    	const int capArray = 10000000;
    	int* myArray = new int[capArray];
    	Sort* mySort = new Sort;
    
    
    	time_t start = 0, end = 0;//此行以及下一行的变量是用来进行算法用时计算的
    	struct timeb startTime, endTime;
    
    	CreateRandomArray(capArray, myArray);
    
    	//cout << "待排序之前的数组中所有元素为：" << endl;
    	//Prlong intArray(myArray, capArray);
    
    	//进行快排
    	time(&start);
    	ftime(&startTime);
    
    	mySort->QuickSort(myArray, 0, capArray - 1);
    
    	time(&end);
    	ftime(&endTime);
    
    	//cout << "快排之后的数组为：" << endl;
    	//Prlong intArray(myArray, capArray);
    
    	cout << "整个快速排序用时：" << (end - start) << " s" << endl;
    	cout << "整个快速排序用时：" << (endTime.time - startTime.time)*1000 + (endTime.millitm - startTime.millitm) << " ms" << endl;
    
    	delete mySort;
    	delete [] myArray;
    	return 0;
    }

## 测试 ##

**对10个数据快排：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]  
**对1000个数据快排：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 1]  
**对100000个数据进行快排：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 2]  
**对10000000个数据进行快排：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 3]  
\*\*小结：\*\*从以上几组测试的结果中可以看出快速排序算法效率还是很高的，再多的数据测试我在这里就不做了，如果你的电脑内存够的话可以自己进行测试，，hhhhh。

# 冒泡排序 #

## 代码 ##

#include <iostream>
    #include <ctime>
    #include <sys/timeb.h>
    using namespace std;
    
    class BubbleSort { 
    public:
    	BubbleSort();
    	~BubbleSort();
    
    public:
    	void BSort(int* array, int nums);
    	void Swap(int& lhs, int& rhs);
    };
    
    //默认构造函数
    BubbleSort::BubbleSort(){ }
    //默认析构函数
    BubbleSort::~BubbleSort(){ }
    
    //交换两元素
    void BubbleSort::Swap(int& lhs, int& rhs)
    { 
    	int tempValue = 0;
    	tempValue = lhs;
    	lhs = rhs;
    	rhs = tempValue;
    }
    
    //冒泡排序
    void BubbleSort::BSort(int* myarray, int nums)
    { 
    	for (int ix = nums - 1; ix >= 0; ix--)
    	{ 
    		for (int iy = 0; iy < ix; iy++)
    		{ 
    			if (myarray[iy] > myarray[iy + 1])
    			{ 
    				Swap(myarray[iy], myarray[iy + 1]);
    			}
    		}
    	}
    }
    
    //打印
    void PrintArray(int* myarray, int nums)
    { 
    	cout << "--------------" << endl;
    	for (int ix = 0; ix < nums; ix++)
    	{ 
    		cout << myarray[ix] << " ";
    	}
    	cout << "--------------" << endl;
    }
    
    //创建一个随时间变化的随机数组
    void CreateRandomArray(int scale, int* mArray)
    { 
    	const int valScale = scale + 1;
    	srand((unsigned int)time(NULL));//生成一个随机数种子
    	for (int ix = 0; ix < scale; ix++)
    	{ 
    		mArray[ix] = rand() % valScale;
    	}
    }
    
    int main()
    { 
    	const int scale = 10000000;
    	int* myArray = new int[scale];
    	BubbleSort* myBS = new BubbleSort;
    
    	CreateRandomArray(scale, myArray);
    
    	//查看算法执行时间
    	time_t start = 0, end = 0;
    	struct timeb timeStart, timeEnd;
    
    	time(&start);
    	ftime(&timeStart);
    
    	myBS->BSort(myArray, scale);
    
    	time(&end);
    	ftime(&timeEnd);
    
    	//PrintArray(myArray, scale);
    
    	cout << "对 " << scale << " 个元素进行冒泡排序的时间为：" << endl;
    	cout << (end - start) << " s" << endl;
    	cout << (timeEnd.time - timeStart.time) * 1000 + (timeEnd.millitm - timeStart.millitm) << " ms" << endl;
    
    	delete[] myArray;
    	delete myBS;
    	return 0;
    }

**数据量为10000000的冒泡排序：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 4]  
跑了快5.5h都没跑完，，。。算了，不跑了。

\*\*总结：\*\*从上面的两种算法对相同数据量进行排序的时间上可以看出，快速排序的排序效率远高于冒泡排序算法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70]: /images/20221005/7e9101d6b67546dca72fd7e194e3c5b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/7b60e33545454bcb8cd5e57dc5df8bc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 2]: /images/20221005/6ed4437d23394b809314c8813ba78301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 3]: /images/20221005/ab050374850043099825f532c7d9d7dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMyODQxNA_size_16_color_FFFFFF_t_70 4]: /images/20221005/116031d4f0b1458eadd84a201ebda2e4.png