275-快速排序算法(单向划分)

以你之姓@ 2023-01-13 10:54 133阅读 0赞

## 快速排序算法(单向划分) ##

## 解题思路图解 ##

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

**我们希望把小于等于56的都集中在左边，大于56的集中在右边。**  
**34<56，把i+1，i和j的位置交换。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

**j往下走，是23，小于56，i+1，i到达j，23和23交换。j往下走，**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**78大于56，不交换，j往下走，90大于56，不交换，j往下走，到12的位置。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
**12小于56，i+1到达78的位置，j和i的数据交换，也就是12和78交换。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
**i不动，j往下走，到45的位置。小于56，i+1,到90的位置。i和j的数据交换，90和45交换，**  
**交换后，j往后走，都大于56，然后j超出去了**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
**i在45的位置，把45和第一个值交换，即和56交换。这就是单向划分。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]

## 解题代码如下：（单向划分） ##

![在这里插入图片描述][20210418193318303.png_pic_center]

int OWParition(vector<int>& br, int left, int right)
    {
        
    	int i = left, j = left + 1;
    	int tmp = br[i];
    	while (j <= right)
    	{
        
    		if (br[j] <= tmp)
    		{
        
    			++i;
    			std::swap(br[i], br[j]);
    		}
    		++j;
    	}
    	std::swap(br[left], br[i]);
    	return i;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/99a1580bfc074ebe83715bd16224f6c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/102d5a302df04560b0e80d9a9e684024.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/6f7b697af9de4773b29a2688b13e8817.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/4599c5e56c4f44a183dd43bf10bc8288.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/c4f3138d1ff64203a6b66c29a30188f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221022/4c45c34c145c43efbe2ade8de1c3c47b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221022/21fd6e8ad1cc40f198a1081f6bd53ecb.png
[20210418193318303.png_pic_center]: /images/20221022/e4cb13e890ce4b4bbeb57e0e45c1d01b.png