图解快速排序

共 2723字,需浏览 6分钟

 ·

2021-09-17 21:01


01

快速排序原理


快速排序用到了分治的思想,主要分为三步分治过程:

数组A[p..r]被划分为两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于A[q],而A[q+1..r]的每一个元素大于等于A[q],计算分割点q也是过程的一部分。

递归对A[p..q-1]进行划分直到无法划分为止,则A[p..q-1]处于有序状态,且每一个元素小于A[q]。同样的递归对A[q+1..r]进行划分直到无法划分为止,则A[q+1..r]处于有序状态,且每一个元素大于等于A[q]。

02

快速排序实现

快速排序的核心是数组划分和分割点计算过程,我们用下图表示快速排序划分子序列的过程,现在有原始序列如下图,p、r分别对应0和7。

现在我们使用A[r]作为分割点x,从A[p]开始遍历序列,将小于x的值放在序列左边,大于等于x的值放在序列右边,并求出分割点q,下图则是分割过程。

经过一轮分割得到q位置作为分割点,A[p..q-1]序列小于A[q]而A[q+1..r]大于等于A[q]。后面不断分别对A[p..q-1]和A[q+1..r]进行递归划分则得到一个有序序列A[p..r]

快速排序操作函数声明如下:


typedef int data_type_t;

extern void quick_sort(data_type_t *A, int p, int r);


划分序列获取分割点实现代码如下:
static void swap(data_type_t *x, data_type_t *y){
    if(x == NULL || y == NULL){
        return;
    }

    data_type_t temp = *x;
    *x = *y;
    *y = temp;
}

static int partision(data_type_t *A, int p, int r){
    data_type_t x = A[r]; //以最后一个元素作为主元
    int i = p - 1;
    int j = p;

    while(j < r){
        if(A[j] < x){
            i++;
            swap(&A[j], &A[i]); //比主元大的数放右边,小的数放在数组左边。
        }
        j++;
    }
    swap(&A[++i], &A[r]); //主元作为分割点
    return i; //返回当前分割点位置
}


快速排序实现代码如下:


void quick_sort(data_type_t *A, int p, int r){
    if(p >= r){
        return;
    }
    int q = partision(A, p, r);
    quick_sort(A, p, q - 1);
    quick_sort(A, q + 1, r);
}


03

算法验证


下面我们写一个小程序验证算法的正确性。


#include <stdio.h>
#include "quick_sort.h"

int main() {
    int arr[10] = {8, 3, 5, 9, 1, 2, 78, 32, 6, 8};

    quick_sort(arr, 0, 9);

    int i = 0;
    for(i = 0; i < 10; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


编译输出结果如下:


1 2 3 5 6 8 8 9 32 78


算法完全正确。


浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报