快畢業了,復習了一下C# 的數據結構的排序算法,其中主要有冒泡排序,直接插入排序,簡單選擇排序和快速排序,在其中參考了老趙的CodeTimer和eaglet的性能計數器 ,特此感謝~~
好了,開始我們的排序算法吧 ~
在進行排序算法之前,我們先定義一個100位的隨機數列,好進行各種排序算法的性能測試。
代碼如下:
/// <summary>
/// 隨機生成100位的數組
/// </summary>
/// <returns>返回生成數組</returns>
public static int[] RandomArray()
{
Random ran = new Random();
int[] arr = new int[100];
int tem;
for (int i = 0; i < 100; i++)
{
tem = ran.Next(1, 100);
arr[i] = tem;
}
return arr;
}
1.冒泡排序 (Bubble Sort)
基礎思想:將相鄰的記錄的關鍵碼進行比較,若前面記錄的關鍵碼大於後面記錄的關鍵碼,則將它們交換,否則不交換。
代碼如下:
/// <summary>
/// 冒泡排序算法
/// </summary>
public class BubbleSort : IAction
{
#region IAction 成員
public void Action()
{
int[] array = Program.RandomArray();
for (int a = 0; a < array.Length; a++)
{
int item = 0;
for (int b = array.Length - 1; b > a; b--)
{
if (array[b] < array[b - 1])
{
item = array[b];
array[b] = array[b - 1];
array[b - 1] = item;
}
}
}
}
#endregion
}
2.直接插入排序
基礎思想: 順序的將待排序的記錄安關鍵碼的大小插入到已排序的記錄子序列的適當位置。子序列的記錄個數從1開始逐漸增大,當子序列記錄個數於首先表中的記錄個數相同時排序完畢。
代碼如下:
/// <summary>
/// 直接插入排序算法
/// </summary>
public class DirectInsertSort : IAction
{
#region IAction 成員
public void Action()
{
int[] array = Program.RandomArray();
for (int i = 1; i < array.Length; i++)
{
if (array[i] < array[i - 1])
{
int tem = array[i];
int j = 0;
for (j = i - 1; j >= 0 && tem < array[j]; j--)
{
array[j + 1] = array[j];
}
array[j + 1] = tem;
}
}
}
#endregion
}
3.簡單選擇排序
基礎思想:從待排序的記錄序列中選擇關鍵碼最小(或)最大的記錄並將它也序列中的第一個記錄交換位置;然後從不包括第一個位置上的記錄序列中選擇關鍵碼最小(或最大)的記錄並將它也序列中的第2個記錄交換位置,如此重復,直到序列只剩下一個記錄為止。
代碼如下:
/// <summary>
/// 簡單選擇排序算法
/// </summary>
public class SimpleSelectSort : IAction
{
#region IAction 成員
public void Action()
{
int[] array = Program.RandomArray();
int tmp = 0;
int t = 0;
for (int i = 0; i < array.Length; i++)
{
t = i;
for (int j = i + 1; j < array.Length; j++)
{
if (array[t] > array[j])
{
t = j;
}
}
tmp = array[i];
array[i] = array[t];
array[t] = tmp;
}
#endregion
}
4.快速排序
基礎思想:通過不斷比較關鍵碼,以某咯記錄為界(該記錄成為支點),將待排序列分成兩部分。其中,一小部分滿足所有記錄的關鍵碼都大於或等於支點記錄為界將待排序列按關鍵碼中分成兩部分的過程,稱為一次劃分,直到整個序列按關鍵碼有序為止。
代碼如下:
/// <summary>
/// 快速排序算法
/// </summary>
public class QuickSort : IAction
{
#region IAction 成員
public void Action()
{
int[] array = Program.RandomArray();
QuickSortArray(array, 0, array.Length - 1);
}
private void QuickSortArray(int[] arr, int low, int high)
{
int i = low;
int j = high;
int tmp = arr[low];
while (low < high)
{
while ((low < high) && arr[high] >= tmp)
{
--high;
}
arr[low] = arr[high];
while ((low < high) && arr[low] <= tmp)
{
++low;
}
arr[high] = arr[low];
--high;
}
arr[low] = tmp;
if (i < low - 1)
{
QuickSortArray(arr, i, low - 1);
}
if (j > low + 1)
{
QuickSortArray(arr, low + 1, j);
}
}
#endregion
}
通過上面的描述,我們對C#幾個主要的排序算法了解清楚了 接下來開始解析它們其中的奧妙吧。其實在此之前 我一直都喜歡使用冒泡來排序,不過通過CodeTimer測試了下,結果如下:
總結:從C#幾個常用的排序算法中,我們常用的冒泡法消耗的系統時間是最多了,相比之下快速排序所用的時間倒是很快速。
希望能和大家一起探討.NET中的神奇,享受編程給我們帶來的樂趣~