420-分治算法-快速排序

喜欢ヅ旅行 2022-09-05 02:00 211阅读 0赞

![在这里插入图片描述][24365e4309fe4ce294b5daf50609d7d5.png]  
**用分治算法实现的快速排序对上面数字进行排序**

## 快速排序算法 ##

**选定一个基准数val，把小于val的调整到左边，把大于val的调整到右边**  
**我们选定41位基准**

**左边定义一个l，右边定义一个r**  
![在这里插入图片描述][3d3986cbf6cc44838adef9af8fbaa377.png]  
**我们找的第一个5，发现就小于41了，所以把5调整到41这个地方。**  
![在这里插入图片描述][deba771482fc4aac83051c7ded366770.png]  
**然后l往前加一下。**  
![在这里插入图片描述][a7327660981740a595d1eaf817186651.png]  
**此时r的位置的5已结给过去了，所以r的位置空闲下来了，在左边l进行对比，67大于41，所以把67填到r的位置。**  
![在这里插入图片描述][65b1d29411354736a71c26a703d73b18.png]  
**此时r的位置有效了，r往前走，之前l的67已结放在原来的r位置保存了，现在l的位置是空闲的**  
![在这里插入图片描述][597a56142c8f4e8fb84d85113917403f.png]  
**现在r开始找比41小的，64比41大，不动，r继续左移，一直走到24的位置。**  
![在这里插入图片描述][519b418d882a47dbabb4a3be71e088bc.png]  
**24比41小。把24放到l的位置，然后l向右走1步。**  
![在这里插入图片描述][b35328dfcbc1474b8091156ce13c9d12.png]  
**此时r的位置的24已经给过去了，此时的位置是空闲的。**  
**从l开始找比41大的元素。**  
**l一直走到69，69大于41，把69赋值到r的位置，然后r左移1步，此时l和r跑到同一个位置上了。**  
![在这里插入图片描述][8b3cf57d0be3476a820be190fae84c24.png]  
**相遇的这个地方就存放val值41**  
![在这里插入图片描述][782c121f773448f8be3d624c7db09e1e.png]  
**这个算法的时间复杂度是O(n)**  
原问题只能把41调整到现在的这个位置。并不能解决问题。  
**所以接下来进行问题规模的缩减！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**快排一趟：每一层基准数的平衡调整的时间复杂度是O(n)  
快排多少趟，就是树的深度。二分搜索树。所以总的效率就是O(nlogn)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**继续进行子问题的划分**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**相当于二叉树的中序遍历，就是一组有序的序列了**  
**理想状态下**，平衡的二叉树，原始数据比较乱，时间复杂度是:O(nlogn)  
**如果原始序列是降序的**，我们通过快速排序让降序序列成为升序序列，每一次都要把基准数从头调到末尾，每一层基准数的平衡的调整是O(n)，树的深度是一个链表，O(n)，所以时间复杂度是O(n^2)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    //快排划分函数，调整基准数
    int partation(vector<int> &vec, int i, int j) {
        
    	int val = vec[i];//作为基准数
    	int l = i;
    	int r = j;
    	while (l < r) {
        
    		while (l < r && vec[r] >= val) {
        //右 - 左  找第一个比val小的
    			r--;
    		}
    		if (l < r) {
        
    			vec[l++] = vec[r];
    		}
    		while (l < r && vec[l] < val) {
        //左 - 右  找第一个比val大的
    			l++;
    		}
    		if (l < r) {
        
    			vec[r--] = vec[l];
    		}
    	}
    	vec[l] = val;//放置基准数
    	return l;//返回基准数的下标
    }
    
    void quickSort(vector<int> &vec, int i, int j) {
        
    	if (i >= j)//结束的条件，参加快排的元素只剩下1个了
    	{
        
    		return;
    	}
    	int pos = partation(vec, i, j);
    	quickSort(vec, i, pos - 1);
    	quickSort(vec, pos + 1, j);
    }
    
    int main()
    {
        
    	vector<int> vec;
    	for (int i = 0; i < 11; ++i) {
        
    		vec.push_back(rand() % 100);
    	}
    	
    	for (int v : vec) {
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	quickSort(vec, 0, vec.size() - 1);
    	for (int v : vec) {
        
    		cout << v << " ";
    	}
    
    	cout << endl;
    
    	return 0;
    }

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

## 趋于有序的数组，使用插入排序效率比较高 ##

[24365e4309fe4ce294b5daf50609d7d5.png]: /images/20220829/8ad50b4395a84650a646774eca073ba2.png
[3d3986cbf6cc44838adef9af8fbaa377.png]: /images/20220829/cef826e4773c45e38270242fa165af85.png
[deba771482fc4aac83051c7ded366770.png]: /images/20220829/812884aa6a354b108d4e42cfeb072326.png
[a7327660981740a595d1eaf817186651.png]: /images/20220829/5a7db74bab964c1daa1691c880371090.png
[65b1d29411354736a71c26a703d73b18.png]: /images/20220829/58aaefbf318b45f49f083b70fe17371b.png
[597a56142c8f4e8fb84d85113917403f.png]: /images/20220829/b76975f805c84e7093d79c6a2559bdab.png
[519b418d882a47dbabb4a3be71e088bc.png]: /images/20220829/64cf19484a434a5ea5100694dd3f0707.png
[b35328dfcbc1474b8091156ce13c9d12.png]: /images/20220829/9251f2aa1e394b9791c35962f32dc04b.png
[8b3cf57d0be3476a820be190fae84c24.png]: /images/20220829/6a347d50f54f4ea8b238b58b44defa7f.png
[782c121f773448f8be3d624c7db09e1e.png]: /images/20220829/8c2bf5c36cf640838602688a1d1d8780.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/ce6b738df7014b4eb012b3e7a4de9411.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/357fdd980450436d8c712a0fa7835755.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/819f6ff81add4becb13d8fbd7bc45f61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/7113a300260f4ada8acd4639df152111.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/877e8d7ef6f34ac49eb9fd9df8247d52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/633402c280ce47c99987eaecfb2435f2.png