找到第k个最小元----快速选择

 1 #ifndef QuickSelect_H
 2 #define QuickSelect_H
 3 #define Cutoff 20
 4 typedef int 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 ElementType QuickSelect(ElementType A[],int k, int N);
 9 ElementType Qselect(ElementType A[],int k, int Left, int Right);
10 void PrintMatrix(ElementType A[], int N);
11 #endif // !QuickSelect_H

 1 #include "QuickSelect.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 ElementType QuickSelect(ElementType A[],int k, int N)
43 {
44     return Qselect(A, k-1, 0, N - 1);//该程序即为，输入，k，返回A[k]。因为A从0开始存储，如果想找第5个最小值，其实找的是A[4],所以当我们找第k个值时，应输入k-1。
45 }
46 
47 //快速选择核心算法
48 ElementType Qselect(ElementType A[], int k, 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         if (k < i)
65             Qselect(A, k, Left, i - 1);//对剩下小于枢纽元的元素递归排序
66         else if (k>i)
67             Qselect(A, k, i + 1, Right);//对剩下大于枢纽元的元素递归排序
68         //当k=i时，即查询的值==枢纽元，则找到了，返回A[k]
69     }
70     else//当最后子数组只有Cutoff个，则采用插入排序。
71         InsertionSort(A + Left, Right - Left + 1);
72     return A[k];
73 }
74 
75 //打印数组
76 void PrintMatrix(ElementType A[], int N)
77 {
78     for (int i = 0; i < N; i++)
79         printf("%d ", A[i]);
80 }

 1 #include "QuickSelect.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     int ID;
10     srand((unsigned)time(NULL));
11     for (int i = 0; i < N; i++)
12     {
13         //A[i] = rand() % N;
14         A[i] =N-i;//100000个数，倒序排
15     }
16         
17     printf("n");
18     //PrintMatrix(A, N);
19     printf("请输入要查询的ID:");
20     scanf_s("%d", &ID);
21     printf("Result:%d",QuickSelect(A, ID, N));
22     printf("n");
23 }