基本排序算法（快排）

59 阅读 0 评论 39 点赞

我是靠谱客的博主幽默发夹，最近开发中收集的这篇文章主要介绍基本排序算法（快排），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快排的关键是每次排序中的枢轴值，在最理想情况下，枢轴值能做到最平衡的划分，即得到的两个子问题的大小都不超过n/2。在这种情况下，快速排序的运行速度大幅提升。此时时间复杂度为O( $nlog_{2} n$ )。

空间复杂度：由于快速排序是基于递归的，需要一个递归工作栈来保存每一层递归调用的必要信息，因此空间复杂度和栈的深度有关。最理想情况下，栈的深度为O( $log _{2}n$ )；最坏情况下，栈的深度为O(n)；平均空间复杂度为O( $log _{2}n$ )。

// bug代码，待补充
#include<stdio.h>
int main(){
int buffer[100];
int n,i;
void quickSort(int a[], int low, int high);
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d",buffer+i);
}
printf("The numbers are:rn");
for(i=0; i<n; i++){
printf("%d ", *(buffer+i));
}
printf("rnThe sorted numbers are:rn");
quickSort(buffer[],0,n-1);
for(i=0; i<n; i++){
printf("%d ", *(buffer+i));
}
}
// 将数组a内的low-high之间的元素快速排序
void quickSort(int a[], int low, int high){
int point = partition(int buffer[], int from, int to);
if(low < high){
int point = partition(a,low,high);
quickSort(a,low, point-1);
quickSort(a,point, high);
}
}
int point = partition(int buffer[], int from, int to){
// 具体的划分算法
}

在C语言的实现中，在标准库（<stdlib.h>）中已经实现了快排算法，下面是 qsort() 函数的声明。

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
base -- 指向要排序的数组的第一个元素的指针。
nitems -- 由 base 指向的数组中元素的个数。
size -- 数组中每个元素的大小，以字节为单位。
compar -- 用来比较两个元素的函数。

以下是demo：

#include<stdio.h>
#include<stdlib.h>
int main(){
int buffer[100];
int n,i;
int compar(const void *a, const void *b);
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d",buffer+i);
}
printf("The numbers are:rn");
for(i=0; i<n; i++){
printf("%d ", *(buffer+i));
}
printf("rnThe sorted numbers are:rn");
//	void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
qsort(buffer, n, sizeof(int), compar);
for(i=0; i<n; i++){
printf("%d ", *(buffer+i));
}
}
// compar是一个比较函数，qsort支持多种数据格式的排序比较，故需要自定义比较函数。
int compar(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
// compar_struct是一个结构体比较函数
int compar_struct(){
}

快速排序是一个不稳定的算法。我们无需知道库中是如何将枢纽值选出来，在C中，要会使用qsort函数。