Selection in expected linear time
上一篇 / 下一篇 2007-10-21 00:00:00 / 个人分类：算法
下面的是用C#写的一个算法, 功能是从一个数组中选择第 i 小的一个数, 平均时间复杂度是Θ(n).
using System;using System.Collections.Generic;using System.Text;using System.Diagnostics; class Program
...{
static void Main(string[] args)
...{ int[] array = new int[] ...{ 9, 3, 4, 7, 10, 5, 1 }; int ismall = RandomizedSelect(array, 3); Debug.Assert(ismall == 4);
} /**//// <summary> /// select the value of the i-th smallest number of the array /// </summary> static int RandomizedSelect(int[] array, int i) ...{ return RandomizedSelect(array, 0, array.Length - 1, i); } /**//// <summary> /// select the value of the i-th smallest number between array[startIndex] and array[endIndex] /// </summary> static int RandomizedSelect(int[] array, int startIndex, int endIndex, int i) ...{ if (startIndex == endIndex) return array[startIndex]; int q = Partition(array, startIndex, endIndex); int k = q - startIndex + 1; if (k == i) return array[q]; else if (k < i) return RandomizedSelect(array, q + 1, endIndex, i - k); else return RandomizedSelect(array, startIndex, q - 1, i); } /**//// <summary> /// partition the array(smaller left, bigger right), return the pivot index /// </summary> static int Partition(int[] array, int startIndex, int endIndex) ...{ //just using the middle number, thought it may not be the best way int mid = (endIndex + startIndex) / 2; int v = array[mid]; Swap(array, mid, endIndex); int i = startIndex - 1; int j = endIndex; while (true) ...{ while (array[++i] < v) ...{ } while (array[--j] > v) ...{ } if (i > j) break; Swap(array, i, j); } Swap(array, i, endIndex); return i; } /**//// <summary> /// swap two numbers in the array /// </summary> static void Swap(int[] array, int index1, int index2) ...{ int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; }
}导入论坛 引用链接 收藏 分享给好友 推荐到圈子 管理 举报
TAG:
标题搜索
日历
|
|||||||||
| 日 | 一 | 二 | 三 | 四 | 五 | 六 | |||
| 1 | 2 | 3 | 4 | 5 | 6 | ||||
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | |||
| 14 | 15 | 16 | 17 | 18 | 19 | 20 | |||
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | |||
| 28 | 29 | 30 | 31 | ||||||
我的存档
数据统计
- 访问量: 6425
- 日志数: 290
- 建立时间: 2008-01-02
- 更新时间: 2008-12-01
