线性时间选择算法

1 问题概述

在一个由 n 个元素组成的集合中，第 i 个顺序统计量（order statistic）是该集合中第 i 小的元素。也就是说，最小值是第 1 个顺序统计量（i = 1），最大值是第 n 个顺序统计量（i = n）。
中位数（median）是它所在集合的中点元素。当 n 为奇数时，中位数是唯一的，出现在 i = (n + 1)/2 处。当 n 为偶数时，存在两个中位数，下中位数 i = n/2 和上中位数 i = n/2 + 1 处。因此，不考虑 n 的奇偶性，中位数总是出现在 i = (n+1)/2 的中位数处。本文中所用的中位数总是指下中位数。
选择最大值和最小值
选择中位数或任意位置值

1 选择最大值和最小值

算法原理

对于确定最大值和最小值的问题，n-1 次比较是最优的。

对于同时获取最大值和最小值，至多需要 3(n/2) 次比较就足以同时找到。如果 n 是奇数，那么总共需要 3(n/2) 次比较。如果 n 是偶数，则可先做一次初始比较，接着做 3((n - 2)/2) 次比较。

代码实现

 1   class Program
 2   {
 3     static void Main(string[] args)
 4     {
 5       int[] unsorted = 
 6         { 
 7           4, 1, 5, 2, 6, 3, 7, 9, 8, 0 
 8         };
 9 
10       Console.WriteLine("Min: {0}", GetMinimum(unsorted));
11       Console.WriteLine("Max: {0}", GetMaximum(unsorted));
12 
13       int min, max;
14       GetBothMinMax(unsorted, out min, out max);
15       Console.WriteLine("Min: {0}, Max: {1}", min, max);
16 
17       Console.Read();
18     }
19 
20     static int GetMinimum(int[] a)
21     {
22       int min = a[0];
23 
24       // n-1 次比较
25       for (int i = 1; i < a.Length; i++)
26       {
27         if (a[i] < min)
28           min = a[i];
29       }
30 
31       return min;
32     }
33 
34     static int GetMaximum(int[] a)
35     {
36       int max = a[0];
37 
38       // n-1 次比较
39       for (int i = 1; i < a.Length; i++)
40       {
41         if (a[i] > max)
42           max = a[i];
43       }
44 
45       return max;
46     }
47 
48     static void GetBothMinMax(int[] a, out int min, out int max)
49     {
50       min = a[0];
51       max = a[0];
52 
53       if (a.Length % 2 > 0) // n 为奇数
54       {
55         for (int i = 1; i < a.Length; i = i + 2)
56         {
57           if (a[i] < a[i + 1])
58           {
59             if (a[i] < min) min = a[i];
60             if (a[i + 1] > max) max = a[i + 1];
61           }
62           else
63           {
64             if (a[i + 1] < min) min = a[i + 1];
65             if (a[i] > max) max = a[i];
66           }
67         }
68       }
69       else                  // n 为偶数
70       {
71         for (int i = 1; i < a.Length - 1; i = i + 2)
72         {
73           if (a[i] < a[i + 1])
74           {
75             if (a[i] < min) min = a[i];
76             if (a[i + 1] > max) max = a[i + 1];
77           }
78           else
79           {
80             if (a[i + 1] < min) min = a[i + 1];
81             if (a[i] > max) max = a[i];
82           }
83         }
84 
85         if (a[a.Length - 1] < min) min = a[a.Length - 1];
86         if (a[a.Length - 1] > max) max = a[a.Length - 1];
87       }
88     }
89   }

2 选择中位数或任意位置值

RANDOMIZED-SELECT 算法采用快速排序算法的思想。区别是，快速排序会递归地处理划分的两边，而 RANDOMIZED-SELECT 则只处理一边。所以快速排序的期望运行时间是 Θ(n lg n)，而 RANDOMIZED-SELECT 的期望运行时间为 Θ(n)。

RANDOMIZED-SELECT 的最坏运行时间为 Θ(n2)，即使是要选择最小元素也是如此。因为它是随机化的，该算法的平均情况性能较好。

  1   public class QuickFindAlgorithm
  2   {
  3     public static void TestRandomizedQuickFind()
  4     {
  5       int[] unsorted = 
  6         { 
  7           4, 1, 5, 2, 6, 3, 7, 9, 8, 0 
  8         };
  9 
 10       Console.WriteLine("Find Value : {0}",
 11         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 1));
 12       Console.WriteLine("Find Value : {0}",
 13         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 2));
 14       Console.WriteLine("Find Value : {0}",
 15         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 3));
 16       Console.WriteLine("Find Value : {0}",
 17         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 4));
 18       Console.WriteLine("Find Value : {0}",
 19         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 5));
 20       Console.WriteLine("Find Value : {0}",
 21         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 6));
 22       Console.WriteLine("Find Value : {0}",
 23         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 7));
 24       Console.WriteLine("Find Value : {0}",
 25         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 8));
 26       Console.WriteLine("Find Value : {0}",
 27         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 9));
 28       Console.WriteLine("Find Value : {0}",
 29         RandomizedQuickFind(unsorted, 0, unsorted.Length - 1, 10));
 30 
 31       int median = RandomizedQuickFind(unsorted, 
 32         0, unsorted.Length - 1, (unsorted.Length + 1) / 2);
 33       Console.WriteLine("Find Median : {0}", median);
 34 
 35       Console.Read();
 36     }
 37 
 38     static int RandomizedQuickFind(int[] a, int p, int r, int i)
 39     {
 40       if (p == r)
 41         return a[p];
 42 
 43       int q = RandomizedPartition(a, p, r);
 44       int k = q - p + 1;
 45 
 46       if (i == k)     // the pivot value is the answer
 47       {
 48         return a[q];
 49       }
 50       else if (i < k) // i is in left side
 51       {
 52         return RandomizedQuickFind(a, p, q - 1, i);
 53       }
 54       else            // i is in right side
 55       {
 56         return RandomizedQuickFind(a, q + 1, r, i - k);
 57       }
 58     }
 59 
 60     static void RandomizedQuickSort(int[] unsorted, int left, int right)
 61     {
 62       if (!(left < right)) return;
 63 
 64       int pivotIndex = RandomizedPartition(unsorted, left, right);
 65 
 66       RandomizedQuickSort(unsorted, left, pivotIndex - 1);
 67       RandomizedQuickSort(unsorted, pivotIndex + 1, right);
 68     }
 69 
 70     static int RandomizedPartition(int[] unsorted, int left, int right)
 71     {
 72       int i = random.Next(left, right);
 73       Swap(unsorted, i, right);
 74       return Partition(unsorted, left, right);
 75     }
 76 
 77     static int Partition(int[] unsorted, int left, int right)
 78     {
 79       int pivotIndex = right;
 80 
 81       // 哨兵
 82       int sentinel = unsorted[right];
 83 
 84       // 子数组长度为 right - left + 1
 85       int i = left - 1;
 86       for (int j = left; j <= right - 1; j++)
 87       {
 88         if (unsorted[j] <= sentinel)
 89         {
 90           i++;
 91           Swap(unsorted, i, j);
 92         }
 93       }
 94 
 95       Swap(unsorted, i + 1, pivotIndex);
 96 
 97       return i + 1;
 98     }
 99 
100     static void Swap(int[] unsorted, int i, int j)
101     {
102       int temp = unsorted[i];
103       unsorted[i] = unsorted[j];
104       unsorted[j] = temp;
105     }
106 
107     static Random random = new Random(new Guid().GetHashCode());
108   }

3 分治法选择最大最小值

问题描述

在一个整数组 A[1…n]中，同时寻找最大值和最小值。

算法原理

非递归算法

1．	x ← A[1]; y ← A[1]
2. 	for i ← 2 to n
3. 		if A[i ] < x then x ← A[i ]
4.		if A[i ] > y then y ← A[i ]
5.	end for
6.	return (x, y)

递归算法
1. 将数组分割成两半：A [1… n/2] 和A [(n/2) +1… n]。（设 n 为2的幂）
2. 在每一半中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值中的最大值。

Procedure minmax (low, high)
 	if high – low = 1 then
		if A [low] < A [high] then return (A [low], A[high])
		else return ( A[high], A [low])
 		end if
 	else
		mid ← 		
 		(x1, y1) ← minmax (low, mid)
		(x2, y2) ← minmax (mid + 1, high)
		x ← min {x1, x2}
		y ← max {y1, y2}
		return (x, y)
 	end if