快速排序详解
基本概念：
快速排序是一种分治的排序算法，由C. A. R. Hoare在1962年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
如何切割成两部分：
a) 假设有两个指针low和high,它们的初值分别为low和high
b) 设关键值为key（通常取第一个值）
c) 首先从high所指位置起往前搜索找到第一个比key小的值，和key交换
d) 然后从low所指位置起往后搜索找到第一个比key大的值，和key交换
e) 重复c/d这两步直至low=high为止
最差时间复杂度 (n²)
最优时间复杂度 (nlogn)
平均时间复杂度 (nlogn)
平均空间复杂度（logn）
动态图：
动态图：
简单例子：
切割流程：
源码：
#include <stdio.h>
/* 切分数组 */
int partition(int a[], int first, int last)
{
int i = first;
int j = last;
int key = a[first]; /* 用第一个值作为关键值 */
printf("the key is %d; ", key);
while (i < j) {
/* 从右往左比较 */
while (i < j && a[j] >= key) {
--j; /* 向前找 */
}
a[i] = a[j]; /* 将比关键值小的移到低端 */
/* 从左往右比较 */
while (i < j && a[i] <= key) {
++i; /* 向后找 */
}
a[j] = a[i]; /* 将比关键值大的移到高端 */
}
/* 此时i == j，更改为关键值 */
a[i] = key;
/* 打印合并后的数据 */
int k;
for (k = first; k <= last; ++k)
printf("%d ", a[k]);
printf("\n");
return i; /* 返回关键值位置 */
}
/* 递归方式 */
void sort(int a[], int first, int last)
{
if (a != NULL && first < last) {
int key = partition(a, first, last);
sort(a, first, key-1);
sort(a, key+1, last);
}
}
int main()
{
int arr[] = {49, 38, 65, 97, 76, 13, 27};
int size = sizeof(arr) / sizeof(int);
//sort
sort(arr, 0, size - 1);
int i = 0;
printf("end sort: ");
for (i; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
编译运行：
原文出自： http://blog.csdn.net/daiyudong2020/article/details/52498220
End;
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。