快速排序代码实现以及时间复杂度分析

你的名字 2023-01-01 12:59 185阅读 0赞

# 原理分析 #

快速排序（冒泡排序的升级版）

**快速排序原理分析：先选出一个基准元素（pivot），将数组变为基准元素左边的元素都比基准元素小，基准元素右边的元素都比基准元素大。我们下面将基准元素选择为数组最左边的元素。**

***为了容易理解：我们可以认为是将基准元素进行挖空的操作，然后找到该位置适合填入的元素，从最右边开始往左找找出一个小于基准元素。然后将该元素填入到基准元素的位置，现在基准元素空出来，多了一个相同元素的较大值，那么我们再从左往右进行查找，看是否能找到一个大于基准元素的值来填补到空缺的那个位置上。这样一个循环，循环结束条件是左边的索引大于右边的索引了。一次这样进行递归，遇到结束条件的时候，终止操作。***

template<class T>
    void quicklySort(T& data, int left, int right)
    { 
    	int i = left, j = right, pivot = data[left];
    	while (i < j)
    	{ 
    		while (i < j && data[j] > pivot) j--;
    		if (i < j) data[i++] = data[j];
    		while (i < j && data[i] < pivot)i++;
    		if (i < j) data[j--] = data[i];
    	}
    	data[i] = pivot;
    	if (left < i) quicklySort(data, left, i - 1);
    	if (j < right) quicklySort(data, j + 1, right);
    }

# 时间复杂度分析 #

## 最优情况 ##

**最左边的pivot将数据分为左右相等的两个部分**  
时间复杂度为：O(nlog n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dfd2VpeGlhb3Rhbw_size_16_color_FFFFFF_t_70]

## 最坏情况 ##

有序数列情况是最坏情况，时间复杂度为O(n^2)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dfd2VpeGlhb3Rhbw_size_16_color_FFFFFF_t_70 1]

## 平均时间复杂度 ##

平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：  
![在这里插入图片描述][20210102230410378.png]

![在这里插入图片描述][20210102230138718.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dfd2VpeGlhb3Rhbw_size_16_color_FFFFFF_t_70]: /images/20221120/d11eac649f734f8d9b889a62f1c44525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dfd2VpeGlhb3Rhbw_size_16_color_FFFFFF_t_70 1]: /images/20221120/c805a4e8eee644d7a7d519f0f9185b9c.png
[20210102230410378.png]: /images/20221120/07766f11fcce46f68a85b22e589cd9b5.png
[20210102230138718.png]: /images/20221120/fcfe65ccbd7a414788205e75312fcbac.png