算法基础：排序基础：分区算法之单向循环法

梦里梦外; 2022-11-20 09:34 29阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
前一篇文章中介绍了快排的核心分区算法的双向循环法的实现，分区算法将待排序列根据基准值进行分区，形成整体有序局部无序的结果特征，加之每次执行都会使序列中的基准值就位，非常简洁和有效。双向循环虽然理解简单，但是实现稍微繁琐（虽然之后十来行，但是毕竟是经典算法，还是可以利用别的方式进一步的简化），这篇文章继续介绍一下另外一种方式：单向循环法。

### 目录 ###

*  双向循环 vs 单向循环
 *  算法思路
 *  单向循环方式
 *  模拟实现
 *  结果验证

--------------------

# 双向循环 vs 单向循环 #

> 双向循环：理解起来非常简单，就是大循环中分别套两个循环（分别用于控制左右指针），根据左右指针进行交换，左右指针重叠的地方就是基准值的就坐位置。

双向循环法详细参看如下内容：[https://liumiaocn.blog.csdn.net/article/details/109324844][https_liumiaocn.blog.csdn.net_article_details_109324844]

> 单向循环：双向循环可能会是一般直接能想到的方式，排除这种先入为主的方式，问题重新梳理，无非就是分成两块，正常一遍遍历下来顺便就完成小于基准值的都移到左边呢。按照着这个思路，更简单的单向循环就呼之欲出了。只用一个指针用来记录小于或等于基准值的元素位置，准确来说是范围，从0～此位置的所有元素都满足小于或等于基准值，只有一个正常的循环，循环中如果碰到比初始值小的就进行交换，每次交换之后此指针前行一个位置，此指针的位置确保为小于或等于基准值。循环结束之后在进行基准值和此位置的交换即可，整体只有一个循环加上一个条件判断和两处交换，简洁美丽。

# 算法思路 #

>  *  分区算法也体现了分而治之的思想，在待排的序列中选取基准值pivot，根据基准值将待排序列分为两个区域，如果是升序方式的左边都是小于或等于基准值的部分，而右边则都是大于基准值的部分。分区算法执行一次之后，一般来说序列仍然是无序的状态，唯一在后续排列中不需要再移动位置的就是基准值，分区算法执行一次之后产生的效果是：
>     
>      *  基准值归位：基准值的位置已经是整体排序之后的正确位置，后续的排序继续抛开基准值进行分而治之分别排序即可，这也是和归并排序的一个不同之处，边界处理的方式是不同的，而根本之处在于算法的核心是不同的。
>      *  左右分区：整体将数据分为左右两个分区，这也是此算法名称的来源，整体大致有序，分区还需继续迭代，这也是分区算法一次执行之后的效果

--------------------

# 单向循环方式 #

分区算法可以使用单向循环方式，主要的算法要点如下所示，

*  基准值：为了理解简单，本文基准值缺省选取数组的第一个元素，也可以选择最后一个元素，或者随机选择，这并不是本算法本身的核心，在快排的时候还会展开。
 *  循环：只有一处循环，初始值从基准值后一个元素开始，结束为序列最后一个元素
 *  指针：只有一个真正意义上的指针，指针初始值指向基准值，循环遍历中碰到大于基准值的情况直接无视，只有小于基准值的情况下才会进行指针的移动和内容的交换，注意先移动后交换，因为此指针只有发生移位的时候才会递增，是这个算法的关键。
 *  元素交换：在循环内递增和交换需要一同处理，因为循环会跳过大于基准值的情况，所以循环的下标比此指针可能走的要快，这种情况下，此指针移动的位置处必然是大于基准值的元素，而外层遍历中进来的条件是小于的情况，所以就可以进行交换了。
 *  基准值定位：最终的指针指定的位置即为小于或等于基准值的最后一个元素的位置，直接和初始的基准值进行交换即可。

# 模拟实现 #

int partition(int* arr, int start, int end) { 
        if (start >= end ) return end;
    
        int pivot = arr[start];
        int index = start;
        for (int i=start+1; i<=end; i++) { 
            if (arr[i] <= pivot) { 
                index++;
                int tmp=arr[i]; arr[i]=arr[index]; arr[index]=tmp;
            }
        }
        arr[start]=arr[index];
        arr[index]=pivot;
    
        return index;
    }

--------------------

# 结果验证 #

加上打印和调用的示例代码，可以使用如下方式进行验证

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int partition(int* arr, int start, int end) { 
        if (start >= end ) return end;
    
        int pivot = arr[start];
        int index = start;
        for (int i=start+1; i<=end; i++) { 
            if (arr[i] <= pivot) { 
                index++;
                int tmp=arr[i]; arr[i]=arr[index]; arr[index]=tmp;
            }
        }
        arr[start]=arr[index];
        arr[index]=pivot;
    
        return index;
    }
    
    void print_array(int* arr, int num) { 
        for (int i=0; i<num; i++) printf("%d ",arr[i]);
        printf("\n");
    }
    
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) { 
                scanf("%d",&array[i]);
            }
            partition(array,0,n-1);
            print_array(array,n);
            free(array); array= NULL;
        }
    }

执行结果示例

9
    4 6 4 5 2 6 4 4 9
    4 4 2 4 4 6 5 6 9

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e3409563f16d420993dc79a7775d4860.png
[https_liumiaocn.blog.csdn.net_article_details_109324844]: https://liumiaocn.blog.csdn.net/article/details/109324844