Visual Studio 2008.NET 3.0Visual Studio 2005Visual Studio 2010.NET 2.0.NET 3.5C# 2.0C# 3.5C# 3.0C# 4.0IntermediateDevVisual Studio.NETC#
搜索和排序算法的起点
4.81/5 (6投票s)
通过 C# 了解搜索和排序算法的基础知识。
前言
本文将对搜索和排序算法进行基本介绍。高级开发者可以忽略此内容。如示例代码所示，算法包含许多嵌套功能。例如，假设您有一组数据。您对每个元素执行一个操作。该操作的输出随后被馈送到一个 for 循环中，在该循环中，每个元素都会被遍历，然后馈送到另一个 for 循环中，其中输出数据又作为输入传递，以进行另一次算术/逻辑运算。话虽如此，本文的顺序将如下排列：
- 线性搜索算法
- 二分搜索算法
- 归并排序算法
- 插入排序算法
- 选择排序算法
- 快速排序算法
一位 YouTube MIT 公开课上的算法讲师曾表示，程序员的成功在很大程度上取决于他或她理解和编写算法的能力。他的重点是使用 C 和 Java。我们将使用 .NET 托管代码。有许多算法可以搜索和/或排序数据。搜索数据包括确定值是否存在于数据中，如果存在，则找到该值的位置。搜索算法通常涉及线性搜索或更复杂的二分搜索。顾名思义，线性搜索算法按顺序搜索数组中的每个元素。如果搜索键与数组中的元素不匹配，算法将测试每个元素，当到达数组末尾时，会通知用户搜索键（要查找的值）不存在。
搜索算法
那么我们如何编写一个线性算法呢？下面的代码包含一个类，该类具有一个名为 values 的私有实例变量，以及一个名为 rd 的静态 Random 对象，用于填充具有随机生成整数的数组。我们创建一个数组空间，并用值在 10-99 之间的随机整数填充数组。Search 方法对元素执行线性搜索。用户应输入一个整数，并让该方法找到它（如果它包含在数组中）并输出其位置。
using System;
public class SearchLinear
{
private Int32 [] values;
private static Random rd = new Random();
public SearchLinear(Int32 size)
{
values = new Int32[size];
for (Int32 i = 0; i < size; ++i)
values[ i ] = rd.Next(10, 100);
}
public Int32 Search(Int32 key)
{
for ( Int32 j = 0; j < values.Length; ++j)
if ( values[ j ] == key)
return j;
return -1;
}
public override string ToString()
{
string temp = string.Empty;
foreach (Int32 k in values)
= k + " ";
temp += "\n";
return temp;
}
}
public class Program
{
public static void Main()
{
Int32 s;
Int32 p;
SearchLinear sl = new SearchLinear(10);
Console.WriteLine(sl);
Console.Write( "Enter an integer value (-1 to quit): " );
s = Convert.ToInt32(Console.ReadLine() );
while ( s != -1 )
{
p = sl.Search(s);
if ( p != -1 )
Console.WriteLine("Integer {0} was found in place {1}.\n", s, p);
else
Console.WriteLine("Integer {0} was not found.\n", s);
Console.Write("Enter an integer value(-1 to quit): ");
s = Convert.ToInt32(Console.ReadLine());
}
}
}
线性搜索示例被简化以例证顺序搜索元素以查找值并指定其位置的概念。二分搜索算法是查找已排序列表中特定值的更强大的技术。该方法会进行逐步改进的猜测，并通过选择范围内中间的元素来接近目标值的位置，由于列表是已排序的，因此这是中位数。将其值与目标值进行比较，并确定它大于、小于还是等于目标值。一个猜测的索引，如果其值过高，则成为范围的新上限；如果其值过低，则该索引成为新下限。
using System;
public class BinarySearch
{
private Int32 [] values;
private static Random rd = new Random();
public BinarySearch(Int32 size)
{
values = new Int32 [ size ];
for (Int32 i = 0; i < size; ++i)
values[ i ] = rd.Next(10, 100);
Array.Sort( values );
}
public Int32 Search(Int32 element)
{
Int32 bottom = 0;
Int32 top = values.Length - 1;
Int32 center = (bottom + top + 1) / 2;
Int32 area = -1;
do
{
Console.Write(Remainders(bottom, top) );
for (Int32 i = 0; i < center; ++i)
Console.WriteLine(" * ");
if ( element == values[center] )
area = center;
else if (element < values[center])
top = center - 1;
else
bottom = center + 1;
center = (bottom + top + 1) /2;
} while ( ( bottom <= top) && ( area == -1));
return area;
}
public string Remainders(Int32 bottom, Int32 top)
{
string temp = string.Empty;
for (Int32 i = 0; i < bottom; ++i)
temp += " ";
for (Int32 i = bottom; i <= top; ++i)
temp += values[ i ] + " ";
temp += "\n";
return temp;
}
public override string ToString()
{
return Remainders( 0, values.Length - 1);
}
}
public class Application
{
public static void Main()
{
Int32 s;
Int32 p;
BinarySearch bs = new BinarySearch(15);
Console.WriteLine(bs);
Console.Write("Enter an integer(-1 to quit): " );
s = Convert.ToInt32(Console.ReadLine());
Console.WriteLine();
while (s != -1)
{
p = bs.Search(s);
if ( p != -1 )
Console.WriteLine("Integer {0} was found in place {1}.\n", s, p);
else
Console.WriteLine("Integer {0} was not found.\n", s);
Console.Write("Enter an integer value(-1 to quit): ");
s = Convert.ToInt32(Console.ReadLine());
}
}
}
如前所述，该算法从中间元素开始搜索。这是在搜索了一系列随机生成的数字后，通过二分搜索获得的结果。
11 29 49 51 52 55 65 71 77 83 84 85 85 87 90
Enter an integer(-1 to quit): 55
11 29 49 51 52 55 65 71 77 83 84 85 85 87 90
*
*
*
*
*
*
*
11 29 49 51 52 55 65
*
*
*
52 55 65
*
*
*
*
*
Integer 55 was found in place 5.
排序算法
归并排序算法比插入排序和选择排序算法更有效。听说过“分而治之”策略吗？归并排序基于“分而治之”策略。首先将数据分成两半。然后，每半独立排序，并且可能不递归排序。然后将两个已排序的半部分合并在一起，形成完整的已排序序列。
using System;
public class Program
{
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);
}
private static void ScrambleData(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void PrintData(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();
}
public static void Main()
{
const int items = 50;
Random rd = new Random(items);
Int32[] values = new Int32[items];
ScrambleData(ref values, rd);
PrintData(ref values, 'b', "");
Console.WriteLine();
MergeSort(ref values, 0, values.Length - 1);
PrintData(ref values, 'a', "MergeSort");
Console.WriteLine("\n\n");
}
}
插入排序是另一种简单但“效率低下”的排序算法。它的第一次迭代获取数组中的第二个元素，如果它小于第一个元素，则交换它们。第二次迭代查看第三个元素，并将其插入到前两个元素中的正确位置，从而使所有三个元素都有序。在此算法的第 i 次迭代中，原始数组中的前 i 个元素将是有序的。
34 56 4 10 77 51 93 30 5 52
实现插入排序算法的应用程序首先查看数组的前两个元素，34 和 56。它们已经有序，因此应用程序继续（如果它们无序，它会交换它们）。在下一次迭代中，应用程序查看第三个值，4。此值小于 56，因此应用程序将 4 存储在一个临时变量中，并将 56 向右移动一个元素。然后，应用程序会检查并确定 4 小于 34，因此它将 34 向右移动一个元素。应用程序现在已到达数组的开头，因此它将 4 放在第零个位置。数组现在是
4 34 56 10 77 51 93 30 5 52
我猜想读者可能会认为这个算法在数据已经有序的情况下会非常强大！但这很少发生（尤其是在为演示目的生成随机数时）。但是，与选择排序一样，这些算法有很多好处；它们也可以作为更专业算法的基线。
using System;
public class ISort
{
private Int32[] values;
private static Random rd = new Random();
public ISort(Int32 size)
{
values = new Int32[ size ];
for (Int32 i = 0; i < size; ++i)
values[ i ] = rd.Next(10, 100);
}
public void Sort()
{
Int32 input;
for (Int32 n = 1; n < values.Length; n++)
{
input = values[ n ];
Int32 m = n;
while ( m > 0 && values[m - 1] > input )
{
values[ m ] = values[m - 1];
m--;
}
values[ m ] = input;
PrintData(n, m);
}
}
public void PrintData(Int32 p, Int32 x)
{
Console.Write( "after pass {0}: ", p);
for (Int32 i = 0; i < x; ++i)
Console.Write( values[ i ] + " " );
Console.Write( values[x] + "* " );
for (Int32 i = x + 1; i < values.Length; ++i)
Console.Write( values[ i ] + " " );
Console.Write( "\n ");
for (Int32 i = 0; i <= p; ++i)
Console.Write("--");
Console.WriteLine("\n");
}
public override string ToString()
{
string temp = string.Empty;
foreach (Int32 element in values)
temp += element + " ";
temp += "\n";
return temp;
}
}
public class Program {
public static void Main() {
ISort ins = new ISort(20);
Console.WriteLine( "Unsorted Array:");
Console.WriteLine( ins);
ins.Sort();
Console.WriteLine("Sorted array: ");
Console.WriteLine(ins);
}
}
请注意，当我们实例化 ISort 类并创建一个对象时，我们传入值为 0，以表示该类的成员将生成 20 个随机数。回想一下，这些整数是无序的。输出可能会揭示为什么这被认为是一种效率低下的算法。
Unsorted Array:
60 95 68 39 59 18 28 98 27 89 43 89 76 88 29 96 52 78 36 37
after pass 1: 60 95* 68 39 59 18 28 98 27 89 43 89 76 88 29 96 52 78 36 37
----
after pass 2: 60 68* 95 39 59 18 28 98 27 89 43 89 76 88 29 96 52 78 36 37
------
after pass 3: 39* 60 68 95 59 18 28 98 27 89 43 89 76 88 29 96 52 78 36 37
--------
after pass 4: 39 59* 60 68 95 18 28 98 27 89 43 89 76 88 29 96 52 78 36 37
----------
after pass 5: 18* 39 59 60 68 95 28 98 27 89 43 89 76 88 29 96 52 78 36 37
------------
after pass 6: 18 28* 39 59 60 68 95 98 27 89 43 89 76 88 29 96 52 78 36 37
--------------
after pass 7: 18 28 39 59 60 68 95 98* 27 89 43 89 76 88 29 96 52 78 36 37
----------------
after pass 8: 18 27* 28 39 59 60 68 95 98 89 43 89 76 88 29 96 52 78 36 37
------------------
after pass 9: 18 27 28 39 59 60 68 89* 95 98 43 89 76 88 29 96 52 78 36 37
--------------------
after pass 10: 18 27 28 39 43* 59 60 68 89 95 98 89 76 88 29 96 52 78 36 37
----------------------
after pass 11: 18 27 28 39 43 59 60 68 89 89* 95 98 76 88 29 96 52 78 36 37
------------------------
after pass 12: 18 27 28 39 43 59 60 68 76* 89 89 95 98 88 29 96 52 78 36 37
--------------------------
after pass 13: 18 27 28 39 43 59 60 68 76 88* 89 89 95 98 29 96 52 78 36 37
----------------------------
after pass 14: 18 27 28 29* 39 43 59 60 68 76 88 89 89 95 98 96 52 78 36 37
------------------------------
after pass 15: 18 27 28 29 39 43 59 60 68 76 88 89 89 95 96* 98 52 78 36 37
--------------------------------
after pass 16: 18 27 28 29 39 43 52* 59 60 68 76 88 89 89 95 96 98 78 36 37
----------------------------------
after pass 17: 18 27 28 29 39 43 52 59 60 68 76 78* 88 89 89 95 96 98 36 37
------------------------------------
after pass 18: 18 27 28 29 36* 39 43 52 59 60 68 76 78 88 89 89 95 96 98 37
--------------------------------------
after pass 19: 18 27 28 29 36 37* 39 43 52 59 60 68 76 78 88 89 89 95 96 98
----------------------------------------
Sorted array:
18 27 28 29 36 37 39 43 52 59 60 68 76 78 88 89 89 95 96 98
算法是否可以被标记为效率低下，从而通过不同的编码方式来提高其性能？
这是选择排序算法的一个示例。这里我们使用将参数按引用传递给方法的语法。请注意，CLR 将 ref 和 out 关键字视为执行相同操作。它们显然会产生相同的 IL。请检查此简短的代码片段。
using System;
public sealed class Program {
public static void Main() {
Int32 x = 5;
InsertValue(ref x);
Console.WriteLine(x); // output is "15"
}
private static void InsertValue(ref Int32 v) {
v += 10; // This method can use the initialized value in v.
}
}
如果方法的参数被标记为 ref，则调用者必须在调用方法之前初始化参数的值。被调用的方法可以读取或写入该值。
using System;
public class Program {
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;
}
}
private static void UnSortData(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void PrintData(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();
}
public static void Main()
{
const int items = 40;
Random rnd = new Random(items);
int[] data = new int[items];
UnSortData(ref data, rnd);
PrintData(ref data, 'b', "");
SelectionSort(ref data);
Console.WriteLine();
PrintData(ref data, 'a', "SelectionSort");
}
}
using System;
public class SelectionSort
{
private int[] data;
private static Random generator = new Random();
public SelectionSort( int size )
{
data = new int[ size ];
for ( int i = 0; i < size; i++ )
data[ i ] = generator.Next( 10, 100 );
}
public void Sort()
{
int smallest;
// loop over data.Length - 1 elements
for ( int i = 0; i < data.Length - 1; i++ )
{
smallest = i;
for ( int index = i + 1; index < data.Length; index++ )
if ( data[ index ] < data[ smallest ] )
smallest = index;
Swap( i, smallest );
PrintData( i + 1, smallest );
}
}
public void Swap( int first, int second )
{
int temporary = data[ first ];
data[ first ] = data[ second ];
data[ second ] = temporary;
}
public void PrintData( int pass, int index )
{
Console.Write( "after pass {0}: ", pass );
// output elements through the selected item
for ( int i = 0; i < index; i++ )
Console.Write( data[ i ] + " " );
Console.Write( data[ index ] + "* " );
// finish outputting array
for ( int i = index + 1; i < data.Length; i++ )
Console.Write( data[ i ] + " " );
Console.Write( "\n " );
// indicate amount of array that is sorted
for ( int j = 0; j < pass; j++ )
Console.Write( "-- " );
Console.WriteLine( "\n" );
}
public override string ToString()
{
string temporary = string.Empty;
// iterate through array
foreach ( int element in data )
temporary += element + " ";
temporary += "\n";
return temporary;
}
}
public class Program
{
public static void Main()
{
// create object to perform selection sort
SelectionSort sortArray = new SelectionSort( 15 );
Console.WriteLine( "Unsorted array:" );
Console.WriteLine( sortArray );
sortArray.Sort();
Console.WriteLine( "Sorted array:" );
Console.WriteLine( sortArray );
}
}
结果显示了上述过程的实际执行。
Unsorted array:
48 43 61 55 30 88 30 77 10 61 42 36 23 25 30
after pass 1: 10 43 61 55 30 88 30 77 48* 61 42 36 23 25 30
--
after pass 2: 10 23 61 55 30 88 30 77 48 61 42 36 43* 25 30
-- --
after pass 3: 10 23 25 55 30 88 30 77 48 61 42 36 43 61* 30
-- -- --
after pass 4: 10 23 25 30 55* 88 30 77 48 61 42 36 43 61 30
-- -- -- --
after pass 5: 10 23 25 30 30 88 55* 77 48 61 42 36 43 61 30
-- -- -- -- --
after pass 6: 10 23 25 30 30 30 55 77 48 61 42 36 43 61 88*
-- -- -- -- -- --
and so on . . . . .
-- -- -- -- -- -- -- -- -- --
after pass 11: 10 23 25 30 30 30 36 42 43 48 55 77* 61 61 88
-- -- -- -- -- -- -- -- -- -- --
after pass 12: 10 23 25 30 30 30 36 42 43 48 55 61 77* 61 88
-- -- -- -- -- -- -- -- -- -- -- --
after pass 13: 10 23 25 30 30 30 36 42 43 48 55 61 61 77* 88
-- -- -- -- -- -- -- -- -- -- -- -- --
after pass 14: 10 23 25 30 30 30 36 42 43 48 55 61 61 77* 88
-- -- -- -- -- -- -- -- -- -- -- -- -- --
Sorted array:
10 23 25 30 30 30 36 42 43 48 55 61 61 77 88
快速排序算法：据说最快的排序算法
算法的主题总是涉及对性能的分析，主要是速度。快速排序可能是最流行的排序算法。所编写的代码一直在生成导致无序序列的随机数。我们获取这些数据，对其进行打乱，将其输入排序算法，然后显示结果。我们还没有使用 System.Diagnostics 计时器来衡量性能。足以相信文档坚持认为快速排序是最快的算法。快速排序使用一种“分而治之”的排序方法，首先将输入列表分区为两个部分。然后，每个分区通过递归地反复调用自身来单独排序，直到整个列表排序完成。众所周知，递归函数是调用自身的函数，类似于数学中的阶乘过程。检查代码，注意我们通过引用（使用“ref”关键字）将参数传递给方法，以及代码如何对输入列表进行分区。在视觉上，这似乎比逐个遍历输入列表然后根据数值进行放置更有效。
using System;
public static class QuickSortAlg
{
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);
}
public static void ScrambleData(ref int[] x, Random rdn)
{
for (int i = 0; i <= x.Length - 1; i++)
{
x[i] = (int)(rdn.NextDouble() * x.Length);
}
}
public static void PrintData(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();
}
public static void Main(string[] args)
{
const int items = 30;
Random rdn = new Random(items);
int[] info = new int[items];
ScrambleData(ref info, rdn);
PrintData(ref info, 'b', "");
Console.WriteLine();
QuickSort(ref info);
PrintData(ref info, 'a', "QuickSort");
Console.WriteLine("\n\n");
}
}
输出结果与其他输出结果相同。技术文档坚持认为“实际上”快速排序是最快的。这可能意味着它在处理大量未排序数据时效果更好。输出应该如下所示。
Before sorting
11 18 22 28 22 23 10 14 20 10
11 26 7 2 29 22 14 17 14 27
24 6 1 15 19 24 21 8 24 7
After sorting using algorithm: QuickSort
1 2 6 7 7 8 10 10 11 11
14 14 14 15 17 18 19 20 21 22
22 22 23 24 24 24 26 27 28 29
算法也广泛用于转换数据。输出数据通常是输入到一系列执行算术和/或逻辑运算的步骤。然而，在这种情况下，会遍历输入数组，暂时存储需要检索才能放置在其正确位置的值，以输出有序的数据序列。这适用于任何数据存储：员工 ID 号、姓名、地点等。