排序算法----快速排序（数组形式）

 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

 1 #include "QuickSort.h"
 2 #include<stdio.h>
 3 //通过三数中值分割法获得数组的枢纽元
 4 ElementType Median3(ElementType A[], int Left, int Right)
 5 {
 6     int Center = (Left + Right) / 2;
 7     if (A[Left] > A[Right])
 8         Swap(&A[Left], &A[Right]);
 9     if (A[Left] > A[Center])
10         Swap(&A[Left], &A[Center]);
11     if (A[Center] > A[Right])
12         Swap(&A[Center], &A[Right]);
13     //上述三次交换使得：A[Left]<A[Center]<A[Right]
14     Swap(&A[Center], &A[Right - 1]);
15     return A[Right - 1];//返回枢纽元；
16 }
17 
18 //交换指针p和q各自指向的值；
19 void Swap(ElementType * p, ElementType * q)
20 {
21     ElementType Tmp;
22     Tmp = *p;
23     *p = *q;
24     *q = Tmp;
25 }
26 
27 //当开始给定的数组（或者递归调用产生的子数组）的元素个数<=20个时，采用插入排序。
28 void InsertionSort(ElementType A[], int N)
29 {
30     int j, P;
31     ElementType Tmp;
32     for (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 {
44     Qsort(A, 0, N - 1);
45 }
46 
47 //快速排序核心算法
48 void Qsort(ElementType A[], int Left, int Right)
49 {
50     int i,j;
51     ElementType Pivot;
52     if (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     }
67     else//当最后子数组只有Cutoff个，则采用插入排序。
68         InsertionSort(A + Left, Right - Left + 1);
69 }
70 
71 //打印数组
72 void PrintMatrix(ElementType A[], int N)
73 {
74     for (int i = 0; i < N; i++)
75         printf("%f ", A[i]);
76 }

 1 #include "QuickSort.h"
 2 #include <stdio.h>
 3 #include<time.h>
 4 #include<stdlib.h>
 5 #define N 100000
 6 int main()
 7 {
 8     ElementType A[N];
 9     srand((unsigned)time(NULL));
10     for (int i = 0; i < N; i++)
11         A[i] = (float)(rand() % N)/N;
12     //printf("原始数组：n");
13     //PrintMatrix(A, N);
14     QuickSort(A, N);
15     printf("n");
16     printf("排序后数组：n");
17     PrintMatrix(A, N);
18     printf("n");
19 }