Windows 2008 R2Windows 2008Windows VistaWindows 7Visual Studio 2008Visual Studio 2010C# 3.5C# 3.0C# 4.0IntermediateDevVisual StudioWindowsC#
通过 C# 进行搜索和排序算法
4.67/5 (11投票s)
本文档详细介绍如何使用 C# 编写算法。
引言与参考
本文将重点介绍通过 .NET Framework 类库实现的排序和搜索算法。因此，它假设读者对泛型（Generics）有实际的了解。FCL（Framework Class Library）提供了几种称为集合（collections）的类，用于存储相关对象的组。这些类不仅提供了组织、存储和检索数据的方法，还提供了排序和搜索的方法。请考虑 `System.Collections.Generic` 命名空间中的通用 `List<T>` 类以及 `System.Collections` 命名空间中的 `ArrayList` 类。这两个类都具有与 C# 数组非常相似的属性，并且还附带了执行高效排序和搜索的方法。然而，使用集合类而非传统数组的一个关键优势是，集合可以随着元素数量的变化而动态地增长和缩小。另一方面，数组不会在运行时自动调整其大小以适应初始分配元素数量的变化，除非编写代码的人手动编写一个新数组或使用数组类的 `Resize` 方法。请注意，本文档中引用的材料来自 CRC Press 出版的《C# 中的数值方法、算法和工具》一书，作者是 Waldemar Dos Passos。
排序算法本质上是一种包含代码指令的“菜谱”，用于将列表中的元素组织成明确定义的数字或字母顺序。列表是一个抽象概念，由一组有限的、固定长度的实体组成，这些实体可以按随机顺序或按递增或递减的顺序排列。在实际应用中，技术文档指出，列表通常以数组或更高级的数据结构（如链表）的形式表示。如果我们对数据进行排序，我们显然是将未排序的数据输入计算模型。输出是排序后的数据。让我们看一个名为冒泡排序（Bubble Sort）的基本 C# 算法示例。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
public class Program
{
public static void bubbleSort1(ref int[] x)
{
bool exchanges;
do
{
exchanges = false;
for (int i = 0; i < x.Length - 1; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
exchanges = true;
}
}
} while (exchanges);
}
public static void DisplayElements(ref int[] xArray, char status, string sortname)
{
if (status == 'a')
Console.WriteLine("After sorting using algorithm: " + sortname);
else
Console.WriteLine("Before sorting");
for (int i = 0; i <= xArray.Length - 1; i++)
{
if ((i != 0) && (i % 10 == 0))
Console.Write("\n");
Console.Write(xArray[i] + " ");
}
Console.ReadLine();
}
static void MixDataUp(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void Main(string[] args)
{
Console.WriteLine("Sorting Algorithms Demo Code\n\n");
const int nItems = 20;
Random rdn = new Random(nItems);
int[] xdata = new int[nItems];
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
Console.WriteLine();
bubbleSort1(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSort1");
Console.WriteLine("\n\n");
Console.WriteLine("Press Enter to Exit...");
}
}
不可否认，本例中的数据量非常小。然而，示例代码旨在演示其工作原理。看看输出。
Sorting Algorithms Demo Code
Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1
After sorting using algorithm: bubbleSort1
0 0 1 1 3 4 4 5 7 7
9 9 10 12 13 14 16 17 17 19
Press Enter to Exit...
冒泡排序的工作原理是遍历要排序的整个列表，一次比较两个元素，如果发现它们的顺序错误就交换它们的位置。重复此过程，直到不需要交换为止，这表明列表已排序。该算法之所以得名，是因为较小的元素似乎会“冒泡”到列表的顶部。事实上，冒泡排序算法的性能问题之一是它对于大量数据效率低下。MIT Open Course Ware 提供了一门关于算法的课程，并强调算法设计的一个重要部分是性能分析。这里是冒泡排序算法的另一个示例。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
public class Program
{
public static void bubbleSort2(ref int[] x)
{
for (int pass = 1; pass < x.Length - 1; pass++)
{
// Count how many times this next loop
// becomes shorter and shorter
for (int i = 0; i < x.Length - pass; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
}
}
}
}
public static void DisplayElements(ref int[] xArray, char status, string sortname)
{
if (status == 'a')
Console.WriteLine("After sorting using algorithm: " + sortname);
else
Console.WriteLine("Before sorting");
for (int i = 0; i <= xArray.Length - 1; i++)
{
if ((i != 0) && (i % 10 == 0))
Console.Write("\n");
Console.Write(xArray[i] + " ");
}
Console.ReadLine();
}
static void MixDataUp(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void Main(string[] args)
{
Console.WriteLine("Sorting Algorithms Demo Code\n\n");
const int nItems = 20;
Random rdn = new Random(nItems);
int[] xdata = new int[nItems];
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
Console.WriteLine();
bubbleSort2(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSort2");
Console.WriteLine("\n\n");
Console.WriteLine("Press Enter to Exit...");
}
}
注意输出。它基本相同，但代码不同，以便对 20 个数据元素进行更高效的处理。
Sorting Algorithms Demo Code
Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1
After sorting using algorithm: bubbleSort2
0 0 1 1 3 4 4 5 7 7
9 9 10 12 13 14 16 17 17 19
Press Enter to Exit...
鸡尾酒排序（Cocktail Sort），也称为双向冒泡排序（Bi-directional Bubble Sort），只是基本冒泡排序算法的一个略微改进的版本。鸡尾酒排序与冒泡排序算法的区别在于，鸡尾酒排序不是从底部到顶部反复遍历输入列表，而是交替地从底部到顶部然后从顶部到底部进行遍历。通过执行双向迭代，鸡尾酒排序可以比标准的冒泡排序算法实现稍好的性能，后者只沿一个方向遍历输入列表，因此每次迭代只能将项目移动一步。这里是鸡尾酒排序算法的示例。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
public class Program
{
public static void CocktailSort(ref int[] x)
{
for (int k = x.Length - 1; k > 0; k--)
{
bool swapped = false;
for (int i = k; i > 0; i--)
if (x[i] < x[i - 1])
{
// swap
int temp = x[i];
x[i] = x[i - 1];
x[i - 1] = temp;
swapped = true;
}
for (int i = 0; i < k; i++)
if (x[i] > x[i + 1])
{
// swap
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
swapped = true;
}
if (!swapped)
break;
}
}
public static void DisplayElements(ref int[] xArray, char status, string sortname)
{
if (status == 'a')
Console.WriteLine("After sorting using algorithm: " + sortname);
else
Console.WriteLine("Before sorting");
for (int i = 0; i <= xArray.Length - 1; i++)
{
if ((i != 0) && (i % 10 == 0))
Console.Write("\n");
Console.Write(xArray[i] + " ");
}
Console.ReadLine();
}
static void MixDataUp(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void Main(string[] args) {
const int nItems = 50;
Random rdn = new Random(nItems);
int[] xdata = new int[nItems];
MixDataUp(ref xdata, rdn);
Console.WriteLine();
DisplayElements(ref xdata, 'b', "");
Console.WriteLine();
CocktailSort(ref xdata);
DisplayElements(ref xdata, 'a', "CocktailSort");
Console.WriteLine("\n\n");
}
}
这是不同方法的输出。请注意，我们再次使用了一种方法，它会打乱数据、显示数据、调用排序算法，然后显示结果。
Before sorting
Before sorting
42 24 35 11 39 12 15 26 8 35
6 25 0 24 49 12 44 49 1 33
23 5 22 24 30 34 46 33 17 17
32 31 20 12 5 46 22 22 45 17
44 30 36 46 13 41 17 12 1 41
After sorting using algorithm: CocktailSort
0 1 1 5 5 6 8 11 12 12
12 12 13 15 17 17 17 17 20 22
22 22 23 24 24 24 25 26 30 30
31 32 33 33 34 35 35 36 39 41
41 42 44 44 45 46 46 46 49 49
下载的 zip 文件包含了上述排序示例，以及大量的其他排序算法和搜索算法。在此描述它们全部将超出本文的范围。此时，我们应该考虑搜索算法。
搜索算法
线性搜索（Linear Search），也称为顺序搜索（Sequential Search），是一种适用于在数据列表中查找特定值的搜索算法。它通过一次检查列表中的每个元素，直到找到匹配项为止。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
public class Program
{
public static int LinearSearch(ref int[] x, int valueToFind)
{
for (int i = 0; i < x.Length; i++)
{
if (valueToFind == x[i])
{
return i;
}
}
return -1;
}
public static void DisplayElements(ref int[] xArray, char status, string sortname)
{
if (status == 'a')
Console.WriteLine("After sorting using algorithm: " + sortname);
else
Console.WriteLine("Before sorting");
for (int i = 0; i <= xArray.Length - 1; i++)
{
if ((i != 0) && (i % 10 == 0))
Console.Write("\n");
Console.Write(xArray[i] + " ");
}
Console.ReadLine();
}
static void MixDataUp(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void Main(string[] args) {
const int nItems = 20;
Random rdn = new Random(nItems);
int[] xdata = new int[nItems];
MixDataUp(ref xdata, rdn); //Randomize data to be searched
DisplayElements(ref xdata, 'b', ""); //Display random data
Console.WriteLine("Using LINEAR SEARCH ALGORITHM " +
"to look for 4th data entry in randomized list");
//Look for the 4th data entry in the list
int location = LinearSearch(ref xdata, xdata[4]);
if (location == -1)
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
location = LinearSearch(ref xdata, 19); //Look for the number 19 in the list.
if (location == -1)
Console.WriteLine("Value of 19 was not found in list");
else
Console.WriteLine("Value of 19 was found at location = {0}", location);
Console.WriteLine("\n\n");
}
}
输出如下
Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1
Using LINEAR SEARCH ALGORITHM to look for 4th data entry in randomized list
Found it at location = 4
Value of 19 was found at location = 14
请记住，数组（用方括号 `[]` 表示）通常是零基索引的。也就是说，如果有 [4] 个元素，那么它们的索引是 0、1、2 和 3。通过查看上面代码输出中的位置来验证这一点。现在，让我们看看整合整个解决方案文件的代码。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
public class Program
{
#region Bubble Sorts
public static void bubbleSort1(ref int[] x)
{
bool exchanges;
do
{
exchanges = false;
for (int i = 0; i < x.Length - 1; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
exchanges = true;
}
}
} while (exchanges);
}
public static void bubbleSort2(ref int[] x)
{
for (int pass = 1; pass < x.Length - 1; pass++)
{
// Count how many times this next loop
// becomes shorter and shorter
for (int i = 0; i < x.Length - pass; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
}
}
}
}
public static void bubbleSort3(ref int[] x)
{
bool exchanges;
int n = x.Length;
do
{
n--; // Make loop smaller each time.
// and assume this is last pass over array
exchanges = false;
for (int i = 0; i < x.Length - 1; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
exchanges = true;
}
}
} while (exchanges);
}
public static void bubbleSortRange(ref int[] x)
{
int lowerBound = 0; // First position to compare.
int upperBound = x.Length - 1; // First position NOT to compare.
int n = x.Length - 1;
// Continue making passes while there is a potential exchange.
while (lowerBound <= upperBound)
{
int firstExchange = n; // assume impossibly high index for low end.
int lastExchange = -1; // assume impossibly low index for high end.
// Make a pass over the appropriate range.
for (int i = lowerBound; i < upperBound; i++)
{
if (x[i] > x[i + 1])
{
// Exchange elements
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
// Remember first and last exchange indexes.
if (i < firstExchange)
{ // True only for first exchange.
firstExchange = i;
}
lastExchange = i;
}
}
//--- Prepare limits for next pass.
lowerBound = firstExchange - 1;
if (lowerBound < 0)
{
lowerBound = 0;
}
upperBound = lastExchange;
}
}
#endregion
#region Cocktail Sort
public static void CocktailSort(ref int[] x)
{
for (int k = x.Length - 1; k > 0; k--)
{
bool swapped = false;
for (int i = k; i > 0; i--)
if (x[i] < x[i - 1])
{
// swap
int temp = x[i];
x[i] = x[i - 1];
x[i - 1] = temp;
swapped = true;
}
for (int i = 0; i < k; i++)
if (x[i] > x[i + 1])
{
// swap
int temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
swapped = true;
}
if (!swapped)
break;
}
}
#endregion
#region Odd Even Sort
public static void OddEvenSort(ref int[] x)
{
int temp;
for (int i = 0; i < x.Length / 2; ++i)
{
for (int j = 0; j < x.Length - 1; j += 2)
{
if (x[j] > x[j + 1])
{
temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}
}
for (int j = 1; j < x.Length - 1; j += 2)
{
if (x[j] > x[j + 1])
{
temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}
}
}
}
#endregion
#region Comb Sort
public static int newGap(int gap)
{
gap = gap * 10 / 13;
if (gap == 9 || gap == 10)
gap = 11;
if (gap < 1)
return 1;
return gap;
}
public static void CombSort(ref int[] x)
{
int gap = x.Length;
bool swapped;
do
{
swapped = false;
gap = newGap(gap);
for (int i = 0; i < (x.Length - gap); i++)
{
if (x[i] > x[i + gap])
{
swapped = true;
int temp = x[i];
x[i] = x[i + gap];
x[i + gap] = temp;
}
}
} while (gap > 1 || swapped);
}
#endregion
#region Gnome Sort
public static void GnomeSort(ref int[] x)
{
int i = 0;
while (i < x.Length)
{
if (i == 0 || x[i - 1] <= x[i]) i++;
else
{
int temp = x[i];
x[i] = x[i - 1];
x[--i] = temp;
}
}
}
#endregion
#region Insertion Sort
public static void InsertionSort(ref int[] x)
{
int n = x.Length - 1;
int i, j, temp;
for (i = 1; i <= n; ++i)
{
temp = x[i];
for (j = i - 1; j >= 0; --j)
{
if (temp < x[j]) x[j + 1] = x[j];
else break;
}
x[j + 1] = temp;
}
}
#endregion
#region Quick Sort
public static void QuickSort(ref int[] x)
{
qs(x, 0, x.Length - 1);
}
public static void qs(int[] x, int left, int right)
{
int i, j;
int pivot, temp;
i = left;
j = right;
pivot = x[(left + right) / 2];
do
{
while ((x[i] < pivot) && (i < right)) i++;
while ((pivot < x[j]) && (j > left)) j--;
if (i <= j)
{
temp = x[i];
x[i] = x[j];
x[j] = temp;
i++; j--;
}
} while (i <= j);
if (left < j) qs(x, left, j);
if (i < right) qs(x, i, right);
}
#endregion
#region Shell Sort
public static void ShellSort(ref int[] x)
{
int i, j, temp;
int increment = 3;
while (increment > 0)
{
for (i = 0; i < x.Length; i++)
{
j = i;
temp = x[i];
while ((j >= increment) && (x[j - increment] > temp))
{
x[j] = x[j - increment];
j = j - increment;
}
x[j] = temp;
}
if (increment / 2 != 0)
{
increment = increment / 2;
}
else if (increment == 1)
{
increment = 0;
}
else
{
increment = 1;
}
}
}
#endregion
#region Selection Sort
public static void SelectionSort(ref int[] x)
{
int i, j;
int min, temp;
for (i = 0; i < x.Length - 1; i++)
{
min = i;
for (j = i + 1; j < x.Length; j++)
{
if (x[j] < x[min])
{
min = j;
}
}
temp = x[i];
x[i] = x[min];
x[min] = temp;
}
}
#endregion
#region Merge Sort
public static void MergeSort(ref int[] x, int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
MergeSort(ref x, left, middle);
MergeSort(ref x, middle + 1, right);
Merge(ref x, left, middle, middle + 1, right);
}
}
public static void Merge(ref int[] x, int left, int middle, int middle1, int right)
{
int oldPosition = left;
int size = right - left + 1;
int[] temp = new int[size];
int i = 0;
while (left <= middle && middle1 <= right)
{
if (x[left] <= x[middle1])
temp[i++] = x[left++];
else
temp[i++] = x[middle1++];
}
if (left > middle)
for (int j = middle1; j <= right; j++)
temp[i++] = x[middle1++];
else
for (int j = left; j <= middle; j++)
temp[i++] = x[left++];
Array.Copy(temp, 0, x, oldPosition, size);
}
#endregion
#region Bucket Sort
public static void BucketSort(ref int[] x)
{
//Verify input
if (x == null || x.Length <= 1)
return;
//Find the maximum and minimum values in the array
int maxValue = x[0];
int minValue = x[0];
for (int i = 1; i < x.Length; i++)
{
if (x[i] > maxValue)
maxValue = x[i];
if (x[i] < minValue)
minValue = x[i];
}
//Create a temporary "bucket" to store the values in order
//each value will be stored in its corresponding index
//scooting everything over to the left as much as possible (minValue)
LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];
//Move items to bucket
for (int i = 0; i < x.Length; i++)
{
if (bucket[x[i] - minValue] == null)
bucket[x[i] - minValue] = new LinkedList<int>();
bucket[x[i] - minValue].AddLast(x[i]);
}
//Move items in the bucket back to the original array in order
int k = 0; //index for original array
for (int i = 0; i < bucket.Length; i++)
{
if (bucket[i] != null)
{
LinkedListNode<int> node = bucket[i].First; //start add head of linked list
while (node != null)
{
x[k] = node.Value; //get value of current linked node
node = node.Next; //move to next linked node
k++;
}
}
}
}
#endregion
#region Heap Sort
public static void Heapsort(ref int[] x)
{
int i;
int temp;
int n = x.Length;
for (i = (n / 2) - 1; i >= 0; i--)
{
siftDown(ref x, i, n);
}
for (i = n - 1; i >= 1; i--)
{
temp = x[0];
x[0] = x[i];
x[i] = temp;
siftDown(ref x, 0, i - 1);
}
}
public static void siftDown(ref int[] x, int root, int bottom)
{
bool done = false;
int maxChild;
int temp;
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom)
maxChild = root * 2;
else if (x[root * 2] > x[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (x[root] < x[maxChild])
{
temp = x[root];
x[root] = x[maxChild];
x[maxChild] = temp;
root = maxChild;
}
else
{
done = true;
}
}
}
#endregion
#region Count Sort
public static void Count_Sort(ref int[] x)
{
try
{
int i = 0;
int k = FindMax(x); //Finds max value of input array
// output array holds the sorted output
int[] output = new int[x.Length];
// provides temperarory storage
int[] temp = new int[k + 1];
for (i = 0; i < k + 1; i++)
{
temp[i] = 0;
}
for (i = 0; i < x.Length; i++)
{
temp[x[i]] = temp[x[i]] + 1;
}
for (i = 1; i < k + 1; i++)
{
temp[i] = temp[i] + temp[i - 1];
}
for (i = x.Length - 1; i >= 0; i--)
{
output[temp[x[i]] - 1] = x[i];
temp[x[i]] = temp[x[i]] - 1;
}
for (i = 0; i < x.Length; i++)
{
x[i] = output[i];
}
}
catch (System.Exception e)
{
Console.WriteLine(e.ToString());
Console.ReadLine();
}
}
#endregion
#region Radix Sort
//RadixSort takes an array and the number of bits used as
//the key in each iteration.
public static void RadixSort(ref int[] x, int bits)
{
//Use an array of the same size as the original array
//to store the result of each iteration.
int[] b = new int[x.Length];
int[] b_orig = b;
//Mask is the bitmask used to extract the sort key.
//We start with the bits least significant bits and
//left-shift it the same amount at each iteration.
//When all the bits are shifted out of the word, we are done.
int rshift = 0;
for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits)
{
//An array is needed to store the count for each key value.
int[] cntarray = new int[1 << bits];
//Count each key value
for (int p = 0; p < x.Length; ++p)
{
int key = (x[p] & mask) >> rshift;
++cntarray[key];
}
//Sum up how many elements there are with lower
//key values, for each key.
for (int i = 1; i < cntarray.Length; ++i)
cntarray[i] += cntarray[i - 1];
//The values in cntarray are used as indexes
//for storing the values in b. b will then be
//completely sorted on this iteration's key.
//Elements with the same key value are stored
//in their original internal order.
for (int p = x.Length - 1; p >= 0; --p)
{
int key = (x[p] & mask) >> rshift;
--cntarray[key];
b[cntarray[key]] = x[p];
}
//Swap the a and b references, so that the
//next iteration works on the current b,
//which is now partially sorted.
int[] temp = b; b = x; x = temp;
}
}
#endregion
#region Linear Search
public static int LinearSearch(ref int[] x, int valueToFind)
{
for (int i = 0; i < x.Length; i++)
{
if (valueToFind == x[i])
{
return i;
}
}
return -1;
}
#endregion
#region Binary Search
public static int BinSearch(ref int[] x, int searchValue)
{
// Returns index of searchValue in sorted array x, or -1 if not found
int left = 0;
int right = x.Length;
return binarySearch(ref x, searchValue, left, right);
}
public static int binarySearch(ref int[] x, int searchValue, int left, int right)
{
if (right < left)
{
return -1;
}
int mid = (left + right) >> 1;
if (searchValue > x[mid])
{
return binarySearch(ref x, searchValue, mid + 1, right);
}
else if (searchValue < x[mid])
{
return binarySearch(ref x, searchValue, left, mid - 1);
}
else
{
return mid;
}
}
#endregion
#region Interpolation Search
public static int InterpolationSearch(ref int[] x, int searchValue)
{
// Returns index of searchValue in sorted input data
// array x, or -1 if searchValue is not found
int low = 0;
int high = x.Length - 1;
int mid;
while (x[low] < searchValue && x[high] >= searchValue)
{
mid = low + ((searchValue - x[low]) * (high - low)) / (x[high] - x[low]);
if (x[mid] < searchValue)
low = mid + 1;
else if (x[mid] > searchValue)
high = mid - 1;
else
return mid;
}
if (x[low] == searchValue)
return low;
else
return -1; // Not found
}
#endregion
#region Nth Largest
public static int NthLargest1(int[] array, int n)
{
//Copy input data array into a temporary array
//so that original array is unchanged
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
//Sort the array
QuickSort(ref tempArray);
//Return the n-th largest value in the sorted array
return tempArray[tempArray.Length - n];
}
public static int NthLargest2(int[] array, int k)
{
int maxIndex;
int maxValue;
//Copy input data array into a temporary array
//so that original array is unchanged
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
for (int i = 0; i < k; i++)
{
maxIndex = i; // index of minimum element
maxValue = tempArray[i];// assume minimum is the first array element
for (int j = i + 1; j < tempArray.Length; j++)
{
// if we've located a higher value
if (tempArray[j] > maxValue)
{ // capture it
maxIndex = j;
maxValue = tempArray[j];
}
}
Swap(ref tempArray[i], ref tempArray[maxIndex]);
}
return tempArray[k - 1];
}
#endregion
#region Mth Smallest
public static int MthSmallest1(int[] array, int m)
{
//Copy input data array into a temporary array
//so that original array is unchanged
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
//Sort the array
QuickSort(ref tempArray);
//Return the m-th smallest value in the sorted array
return tempArray[m - 1];
}
public static int MthSmallest2(int[] array, int m)
{
int minIndex;
int minValue;
//Copy input data array into a temporary array
//so that original array is unchanged
int[] tempArray = new int[array.Length];
array.CopyTo(tempArray, 0);
for (int i = 0; i < m; i++)
{
minIndex = i; // index of minimum element
minValue = tempArray[i];// assume minimum is the first array element
for (int j = i + 1; j < array.Length; j++)
{
if (tempArray[j] < minValue)
{ // capture it
minIndex = j;
minValue = tempArray[j];
}
}
Swap(ref tempArray[i], ref tempArray[minIndex]);
}
return tempArray[m - 1];
}
#endregion
#region Miscellaneous Utilities
public static int FindMax(int[] x)
{
int max = x[0];
for (int i = 1; i < x.Length; i++)
{
if (x[i] > max) max = x[i];
}
return max;
}
public static int FindMin(int[] x)
{
int min = x[0];
for (int i = 1; i < x.Length; i++)
{
if (x[i] < min) min = x[i];
}
return min;
}
static void MixDataUp(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
static void Swap(ref int left, ref int right)
{
int temp = left;
left = right;
right = temp;
}
// Determines if int array is sorted from 0 -> Max
public static bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i - 1] > arr[i])
{
return false;
}
}
return true;
}
// Determines if string array is sorted from A -> Z
public static bool IsSorted(string[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
if (arr[i - 1].CompareTo(arr[i]) > 0) // If previous is bigger, return false
{
return false;
}
}
return true;
}
// Determines if int array is sorted from Max -> 0
public static bool IsSortedDescending(int[] arr)
{
for (int i = arr.Length - 2; i >= 0; i--)
{
if (arr[i] < arr[i + 1])
{
return false;
}
}
return true;
}
// Determines if string array is sorted from Z -> A
public static bool IsSortedDescending(string[] arr)
{
for (int i = arr.Length - 2; i >= 0; i--)
{
if (arr[i].CompareTo(arr[i + 1]) < 0) // If previous is smaller, return false
{
return false;
}
}
return true;
}
public static void DisplayElements(ref int[] xArray, char status, string sortname)
{
if (status == 'a')
Console.WriteLine("After sorting using algorithm: " + sortname);
else
Console.WriteLine("Before sorting");
for (int i = 0; i <= xArray.Length - 1; i++)
{
if ((i != 0) && (i % 10 == 0))
Console.Write("\n");
Console.Write(xArray[i] + " ");
}
Console.ReadLine();
}
#endregion
static void Main(string[] args)
{
Console.WriteLine("Sorting Algorithms Demo Code\n\n");
const int nItems = 20;
Random rdn = new Random(nItems);
int[] xdata = new int[nItems];
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
bubbleSort1(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSort1");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
bubbleSort2(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSort2");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
bubbleSort3(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSort3");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
bubbleSortRange(ref xdata);
DisplayElements(ref xdata, 'a', "bubbleSortRange");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
CocktailSort(ref xdata);
DisplayElements(ref xdata, 'a', "CocktailSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
OddEvenSort(ref xdata);
DisplayElements(ref xdata, 'a', "OddEvenSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
CombSort(ref xdata);
DisplayElements(ref xdata, 'a', "CombSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
GnomeSort(ref xdata);
DisplayElements(ref xdata, 'a', "GnomeSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
InsertionSort(ref xdata);
DisplayElements(ref xdata, 'a', "InsertionSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
QuickSort(ref xdata);
DisplayElements(ref xdata, 'a', "QuickSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
ShellSort(ref xdata);
DisplayElements(ref xdata, 'a', "ShellSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
SelectionSort(ref xdata);
DisplayElements(ref xdata, 'a', "SelectionSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
MergeSort(ref xdata, 0, xdata.Length - 1);
DisplayElements(ref xdata, 'a', "MergeSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
BucketSort(ref xdata);
DisplayElements(ref xdata, 'a', "BucketSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
Heapsort(ref xdata);
DisplayElements(ref xdata, 'a', "HeapSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
Count_Sort(ref xdata);
DisplayElements(ref xdata, 'a', "CountSort");
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
int bits = 4;
RadixSort(ref xdata, bits);
DisplayElements(ref xdata, 'a', "RadixSort");
Console.WriteLine("\n\n");
//The search tests that follow are divided into two steps
//(1) Tries to find the 4th data entry in a randomized list.
//Since this data value always exist, the result will always be successful
//(2) Tries to find a numerical value of 100 in a randomized list.
//Since this data value is beyond the maximum
//value that the random generator is setup
//to produce, the result will always fail.
//This way all possible outcomes are fully checked.
//Note that the linear search strategy
//is the out method that accepts randomized data.
//For all other searches, the data must be sorted first.
Console.WriteLine("Search Algorithms Demo Code\n\n");
MixDataUp(ref xdata, rdn); //Randomize data to be searched
DisplayElements(ref xdata, 'b', ""); //Display random data
Console.WriteLine("Using LINEAR SEARCH ALGORITHM " +
"to look for 4th data entry in randomized list");
//Look for the 4th data entry in the list
int location = LinearSearch(ref xdata, xdata[4]);
if (location == -1)
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
location = LinearSearch(ref xdata, 100); //Look for the number 100 in the list.
if (location == -1)
Console.WriteLine("Value of 100 was not found in list");
else
Console.WriteLine("Value of 100 was found at at location = {0}", location);
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', ""); //Display random data
QuickSort(ref xdata);
Console.WriteLine("Using INTERPOLATION SEARCH ALGORITHM " +
"to look for 4th data entry in randomized list");
location = InterpolationSearch(ref xdata, xdata[4]);
if (location == -1)
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
location = InterpolationSearch(ref xdata, 100);
if (location == -1)
Console.WriteLine("Value of 100 was not found in list");
else
Console.WriteLine("Value of 100 was found at at location = {0}", location);
Console.WriteLine("\n\n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', ""); //Display random data
QuickSort(ref xdata);
Console.WriteLine("Using BINARY SEARCH ALGORITHM to " +
"look for 4th data entry in randomized list");
location = BinSearch(ref xdata, xdata[4]);
if (location == -1)
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
location = InterpolationSearch(ref xdata, 100);
if (location == -1)
Console.WriteLine("Value of 100 was not found in list");
else
Console.WriteLine("Value of 100 was found at at location = {0}", location);
Console.WriteLine("\n\n");
//The ArrayList collection in C# comes with its own built-in search algorithm.
//And can be called up to perform a search as shown below.
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', ""); //Display random data
Console.WriteLine("Using the built-in BINARY " +
"SEARCH ALGORITHM in ArrayList data structure");
ArrayList alist = new ArrayList(); //Set up an ArrayList object
for (int i = 0; i < xdata.Length; i++)
alist.Add(xdata[i]); //and add some radomized data to it
location = alist.BinarySearch(xdata[4]); //Call up its BinarySearch method
if (location == -1) //and run the examples
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
location = alist.BinarySearch(100);
if (location < 0)
Console.WriteLine("Value was not found in list");
else
Console.WriteLine("Found it at location = {0}", location);
Console.WriteLine("Testing to find the n-th largest " +
"value in a random array\n\nOriginal Data (method 1): \n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
int nthMathIndex1 = 8;
int nthMaxValue1 = NthLargest1(xdata, nthMathIndex1);
Console.WriteLine("\nThe " + nthMathIndex1 +
" largest value in the array above is: " +
nthMaxValue1 + "\n");
Console.WriteLine("Verifying result... \nFirst verify " +
"that original data array is not changed.\n");
DisplayElements(ref xdata, 'b', "");
Console.WriteLine("\nThen sort the array and count the " +
"requested position from the largest value at the top\n");
QuickSort(ref xdata);
DisplayElements(ref xdata, 'a', "QuickSort");
//////
Console.WriteLine("\n\nTesting to find the n-th largest " +
"value in a random array\n\nOriginal Data (method 2): \n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
int nthMathIndex2 = 4;
int nthMinValue2 = NthLargest2(xdata, nthMathIndex2);
Console.WriteLine("\nThe " + nthMathIndex2 +
" largest value in the array above is: " +
nthMinValue2 + "\n");
Console.WriteLine("Verifying result... \nFirst verify " +
"that original data array is not changed.\n");
DisplayElements(ref xdata, 'b', "");
Console.WriteLine("\nThen sort the array and count the " +
"requested position from the smallest value at the bottom\n");
QuickSort(ref xdata);
DisplayElements(ref xdata, 'a', "QuickSort");
Console.WriteLine("\n\nTesting to find the m-th smallest " +
"value in a random array\n\nOriginal Data (method 1): \n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
int mthMathIndex1 = 3;
int mthMinValue1 = MthSmallest1(xdata, mthMathIndex1);
Console.WriteLine("\nThe " + mthMathIndex1 +
" smallest value in the array above is: " +
mthMinValue1 + "\n");
Console.WriteLine("Verifying result... \nFirst verify " +
"that original data array is not changed.\n");
DisplayElements(ref xdata, 'b', "");
Console.WriteLine("\nThen sort the array and count the " +
"requested position from the smallest value at the bottom\n");
QuickSort(ref xdata);
DisplayElements(ref xdata, 'a', "QuickSort");
Console.WriteLine("\n\nTesting to find the m-th smallest " +
"value in a random array\n\nOriginal Data (method 2): \n");
MixDataUp(ref xdata, rdn);
DisplayElements(ref xdata, 'b', "");
int mthMathIndex2 = 3;
int mthMinValue2 = MthSmallest2(xdata, mthMathIndex2);
Console.WriteLine("\nThe " + mthMathIndex2 +
" smallest value in the array above is: " +
mthMinValue2 + "\n");
Console.WriteLine("Verifying result... \nFirst " +
"verify that original data array is not changed.\n");
DisplayElements(ref xdata, 'b', "");
Console.WriteLine("\nThen sort the array and count the " +
"requested position from the smallest value at the bottom\n");
QuickSort(ref xdata);
DisplayElements(ref xdata, 'a', "QuickSort");
Console.WriteLine("\n\nTesting sorting utitlities\n");
int[] sortedInts = new int[] { 1, 5, 20, 50 };
int[] unsortedInts = new int[] { 35, 2, 56, 1 };
int[] reversedInts = new int[] { 10, 9, 8, 7 };
string[] sortedStrings = new string[] { "monkey", "duck", "bird" };
string[] unsortedStrings = new string[] { "duck", "monkey", "dog" };
string[] reversedStrings = new string[] { "dog", "duck", "monkey" };
Console.WriteLine(IsSorted(sortedInts)); // True
Console.WriteLine(IsSortedDescending(sortedInts)); // False
Console.WriteLine(IsSorted(unsortedInts)); // False
Console.WriteLine(IsSortedDescending(unsortedInts)); // False
Console.WriteLine(IsSorted(reversedInts)); // False
Console.WriteLine(IsSortedDescending(reversedInts)); // True
Console.WriteLine(IsSorted(sortedStrings)); // True
Console.WriteLine(IsSortedDescending(sortedStrings)); // False
Console.WriteLine(IsSorted(unsortedStrings)); // False
Console.WriteLine(IsSortedDescending(unsortedStrings)); // False
Console.WriteLine(IsSorted(reversedStrings)); // False
Console.WriteLine(IsSortedDescending(reversedStrings)); // True
Console.ReadLine();
Console.WriteLine("\n\nTesting Conversion from List to Array\n");
List<string> myList = new List<string>();
myList.Add("dog");
myList.Add("cat");
myList.Add("duck");
myList.Add("monkey");
myList.Add("bird");
string[] myString = myList.ToArray();
foreach (string s in myString)
Console.WriteLine(s);
Console.WriteLine("\n\nTesting Conversion from Array to List\n");
string[] str = new string[] { "duck", "cat", "dog", "monkey", "bird" };
List<string> myOtherList = new List<string>(str);
myOtherList = str.ToList();
foreach (string s in myOtherList)
Console.WriteLine(s);
Console.ReadLine();
}
}
学习算法最重要的一点是能够编写代码以处理大量数据来解决问题。上面所示的代码不是使用数据并行性编写的。也许读者可以尝试查找可并行化的“热点”，并使用适当的任务并行库（Task Parallel Library）结构来处理它们。