快速排序(英语:Quick Sort),又称划分交换排序(Partition-Exchange Sort),简称快排,一种排序算法,最早由东尼·霍尔提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序算法描述:
1、从数列中挑出一个元素,称为”基准”(pivot),
2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3、递归把小于基准值元素的子数列和大于基准值元素的子数列排序。
一、 快速排序源码
#include <stdio.h> #include <stdlib.h> #include <time.h> #define NUM 10 // 两个数交换函数 void swap(int *p, int *q) { int temp = *p; *p = *q; *q = temp; } // 快速排序函数实现 void quick_sort(int a[], int left, int right) { if(left >= right) return; int mid = left; for(int i=left+1; i<=right; i++) { if(a[i] < a[left]) swap(&a[i], &a[++mid]); } swap(&a[left], &a[mid]); quick_sort(a, left, mid-1); quick_sort(a, mid+1, right); } int main(void) { int array[NUM]; srand((unsigned int)time(NULL)); // 给数组赋随机值 for(int i=0; i<NUM; i++) { array[i] = rand()%100; } // 打印排序前数组 for(int i=0; i<NUM; i++) { printf("%5d", array[i]); } printf("\n"); // 快速排序 quick_sort(array, 0, NUM-1); // 打印排序后数组 for(int i=0; i<NUM; i++) { printf("%5d", array[i]); } printf("\n"); return 0; }
二、 运行结果
[ycxie@fedora Workspace]$ gcc quick_sort.c -o quick_sort -Wall [ycxie@fedora Workspace]$ ./quick_sort 22 72 92 0 37 75 5 95 40 41 0 5 22 37 40 41 72 75 92 95 [ycxie@fedora Workspace]$ ./quick_sort 7 31 39 47 28 81 41 85 6 67 6 7 28 31 39 41 47 67 81 85 [ycxie@fedora Workspace]$ ./quick_sort 16 84 12 74 53 16 33 12 99 68 12 12 16 16 33 53 68 74 84 99 [ycxie@fedora Workspace]$ ./quick_sort 92 48 73 84 42 41 40 11 68 62 11 40 41 42 48 62 68 73 84 92 [ycxie@fedora Workspace]$ ./quick_sort 92 48 73 84 42 41 40 11 68 62 11 40 41 42 48 62 68 73 84 92