算法基础：排序算法：快速排序

快速排序的整体的思路也非常优秀，相较于冒泡选择还是插入的平均时间复杂度都是达到了O（ n 2 n^2 n2)，而快速排序也是降至 O（nlogn），而且相较于归并排序对于空间的额外需求O（n），快速排序这方面也没有问题。唯一的一个问题可能在于由于存在非临元素的交换，可能会产生不稳定性，所以快速排序是不稳定的排序。这篇文章介绍一下归并排序的主要要点和实现，也是比较不错的一个排序算法，深受很多高校老师和面试官的青睐。

算法思路

• 快速排序乍一看很像归并排序，但实际上这是由于两者都是使用了分而治之的思路，所以在算法上都有递归的实现。但是仔细看来二者还是有很多区别的。快速排序的核心在于分区算法，分区算法设定基准值，根据基准值将数据分为三部分：左侧小于基准值序列、基准值、右侧大于基准值的序列。层层递归即完成整体快排。

分区算法有两种实现方式：双向循环方式和单向循环方式，详细可参看：

• 双向循环方式
• 单向循环方式

算法要点

选择排序的主要要点如下所示：

• 循环结束条件：start >= end，非常容易理解
• 主函数：非常简单，递归调用分区函数进行分割，分区函数会返回基准值要就位的位置，然后根据此位置进行递归左侧和右侧的快速排序，直至满足循环结束条件。

注：快排实际上并不是这么简单，因为我们把快排最核心的分区的算法抽出来单独讲解了，在此基础之上快速实现快排就非常简单了。

模拟实现

void quick_sort(int* arr, int start, int end){ if (start >= end) return; int pivot_index = partition(arr,start,end); quick_sort(arr,start,pivot_index-1); quick_sort(arr,pivot_index+1,end); } 

结果验证

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

#include  #include  #include  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 quick_sort(int* arr, int start, int end){ if (start >= end) return; int pivot_index = partition(arr,start,end); quick_sort(arr,start,pivot_index-1); quick_sort(arr,pivot_index+1,end); } 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]); } quick_sort(array,0,n-1); print_array(array,n); free(array); array= NULL; } } 

执行结果示例

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