这个快速排序主要利用递归调用，数组存储方式。包含3个文件，头文件QuickSort.h，库函数QuickSort.c，测试文件TestQuickSort。
其中Cutoff可以自己给定，这个当开始给定的数组（或者递归调用产生的子数组）的元素个数<=20个时，采用插入排序。一般认为当元素个数<=20时，插入排序更快。这个20不是固定的，在这附近浮动都可以的。
头文件QuickSort.h
1 #ifndef QuickSort_H 2 #define QuickSort_H 3 #define Cutoff 20 4 typedef float ElementType; 5 ElementType Median3(ElementType A[], int left, int right); 6 void Swap(ElementType *p, ElementType*q); 7 void InsertionSort(ElementType A[], int N); 8 void QuickSort(ElementType A[], int N); 9 void Qsort(ElementType A[], int Left, int Right);10 void PrintMatrix(ElementType A[], int N);11 12 #endif // !QuickSort_H
库函数QuickSort.c
1 #include "QuickSort.h" 2 #include<stdio.h> 3 //通过三数中值分割法获得数组的枢纽元 4 ElementType Median3(ElementType A[], int Left, int Right) 5 { 6int Center = (Left + Right) / 2; 7if (A[Left] > A[Right]) 8 Swap(&A[Left], &A[Right]); 9if (A[Left] > A[Center])10 Swap(&A[Left], &A[Center]);11if (A[Center] > A[Right])12 Swap(&A[Center], &A[Right]);13//上述三次交换使得：A[Left]<A[Center]<A[Right]14Swap(&A[Center], &A[Right - 1]);15return A[Right - 1];//返回枢纽元；16 }17 18 //交换指针p和q各自指向的值；19 void Swap(ElementType * p, ElementType * q)20 {21ElementType Tmp;22Tmp = *p;23*p = *q;24*q = Tmp;25 }26 27 //当开始给定的数组（或者递归调用产生的子数组）的元素个数<=20个时，采用插入排序。28 void InsertionSort(ElementType A[], int N)29 {30int j, P;31ElementType Tmp;32for (P = 1; P < N; P++)33{34 Tmp = A[P];35 for (j = P; j > 0 && A[j - 1] > Tmp; j--)36 A[j] = A[j - 1];37 A[j] = Tmp;38}39 }40 41 //快速排序算法驱动程序42 void QuickSort(ElementType A[], int N)43 {44Qsort(A, 0, N - 1);45 }46 47 //快速排序核心算法48 void Qsort(ElementType A[], int Left, int Right)49 {50int i,j;51ElementType Pivot;52if (Left + Cutoff-1 <= Right)//此处Cutoff-1是为了和N-1=Right对应上53{54 Pivot = Median3(A, Left, Right);//调用枢纽元函数选取枢纽元55 i = Left; j = Right - 1;56 for (; ;)57 {58 while (A[++i] < Pivot);59 while (A[--j] > Pivot);60 if (i < j) Swap(&A[i], &A[j]);61 else break;62 }63 Swap(&A[i], &A[Right - 1]);64 Qsort(A, Left, i - 1);//对剩下小于枢纽元的元素递归排序65 Qsort(A, i + 1, Right);//对剩下大于枢纽元的元素递归排序66}67else//当最后子数组只有Cutoff个，则采用插入排序。68 InsertionSort(A + Left, Right - Left + 1);69 }70 71 //打印数组72 void PrintMatrix(ElementType A[], int N)73 {74for (int i = 0; i < N; i++)75 printf("%f ", A[i]);76 }
测试文件TestQuickSort
1 #include "QuickSort.h" 2 #include <stdio.h> 3 #include<time.h> 4 #include<stdlib.h> 5 #define N 100000 6 int main() 7 { 8ElementType A[N]; 9srand((unsigned)time(NULL));10for (int i = 0; i < N; i++)11 A[i] = (float)(rand() % N)/N;12//printf("原始数组：\n");13//PrintMatrix(A, N);14QuickSort(A, N);15printf("\n");16printf("排序后数组：\n");17PrintMatrix(A, N);18printf("\n");19 }
随机生成100000个浮点型数据，调用QuickSort算法进行快速排序，速度极快。
如果觉得《排序算法----快速排序（数组形式）》对你有帮助，请点赞、收藏，并留下你的观点哦！
