下面的是用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;
}
}
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;
}
}