首页 > 代码库 > 线性时间选择算法
线性时间选择算法
在一个由 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 的中位数处。本文中所用的中位数总是指下中位数。
选择最大值和最小值
对于确定最大值和最小值的问题，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 else63 {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 else79 {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 }
选择中位数或任意位置值
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 }
本篇文章《线性时间选择算法》由 Dennis Gao 发表自博客园，任何未经作者同意的爬虫或人为转载均为耍流氓。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。