快速排序的实现与优化

灰太狼 2022-05-28 08:10 175阅读 0赞

> 快排的基本思想：  
> 1）选择一个基准元素key，通常选择第一个元素或者最后一个元素  
> 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部 分记录的元素值均比key值小。另一部分记录的元素值比key值大。  
> 3）此时key在其排好序后的正确位置  
> 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

## 三种实现方法 ##

**1、左右指针法**  
算法思想：  
在待排序序列中选择一个数据作为基准值（暂且将区间右端数据作为基准值），定义两个指针begin,end开始分别指向待排序区间的两端，左指针向右找比基准值大的数据，找到后停下来，接着右指针向左开始找比基准值小的数据，找到后停下来，交换左右指针所指数据，直到两指针相遇，出循环后将左指针指向的值与基准值进行交换，交换成功后比基准值小的数据都在其左边，比基准值大的数据都在基准值的右边，换言之基准值已经处于合适的位置。接着递归对基准值的左区间和右区间进行排序，区间只有一个数据默认已经有序。

算法执行过程：  
快排：将大于key值的数放在key值右边，小于key值的数放在key值左边，递归左右子区间。  
![这里写图片描述][SouthEast]

核心代码：

//左右指针法
    int PartSort1(int* a, int begin, int end) { int mid = GetMidIndex(a, begin, end);
        swap(&a[mid], &a[end]);
    
        int key = a[end];//用区间的最右边的值作为基准值
        int keyidx = end;
        while (begin < end) { while (begin < end && a[begin] <= key) ++begin;
            while (begin < end && a[end] >= key) --end;
            if (a[begin] != a[end]) swap(&a[begin], &a[end]);
        }
        swap(&a[begin], &a[keyidx]);
        return begin;
    }

**2、挖坑法**  
算法思想：在待排序序列中选择一个数据作为基准值（暂且将区间右端数据作为基准值），首次将坑设在基准值处，定义两个指针begin，end开始分别指向待排序区间的两端，左指针向右找比基准值大的数据，找到后将该值填入坑中并且将坑的位置更新在左指针所指位置，接着右指针向左开始找比基准值小的数据，找到后将该值填入坑中并且将坑的位置更新在右指针所指位置，直到两指针相遇，出循环后比基准值小的数据都在其左边，比基准值大的数据都在基准值的右边，换言之基准值已经处于合适的位置。接着递归对基准值的左区间和右区间进行排序，区间只有一个数据默认已经有序。

[SouthEast]: /images/20220528/ee396a74e37a4db1986b3782e9f8393f.png