图解快速排序
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]。
—
快速排序实现
经过一轮分割得到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);
}
—
算法验证
下面我们写一个小程序验证算法的正确性。
#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
算法完全正确。
评论