1、冒泡排序
冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它通過一趟又一趟地比較數組中的每一個元素，使較大的數據下沉，較小的數據上升。它是O(n^2)的算法。
2、插入排序
插入排序通過把序列中的值插入一個已經排序好的序列中，直到該序列的結束。
3、Shell排序
Shell排序通過將數據分成不同的組，先對每一組進行排序，然後再對所有的元素進行一次插入排序，以減少數據交換和移動的次數。平均效率是O(nlogn)。
冒泡排序C#實現：
![]()
/// <summary>
/// 冒泡排序
/// </summary>
public class BubbleSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
for (int i = 0; i < array.Length; i++)
{
for (int j = 1; j < array.Length - i; j++)
{
Swap(ref array[j - 1], ref array[j]);
}
}
}
return array;
}
public static void Swap(ref int int1, ref int int2)
{
if (int1 > int2)
{
int temp = int1;
int1 = int2;
int2 = temp;
}
}
}
冒泡排序
插入排序C#實現：
![]()
/// <summary>
/// 插入排序
/// </summary>
public class InsertSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
int k = 1;//使用k變量，後面更好的擴展到Shell排序
for (int i = k; i < array.Length; i++)
{
int current = array[i];
int preIndex = i - k;
while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])
{
array[preIndex + k] = array[preIndex];
preIndex = preIndex - k;
}
array[preIndex + k] = current;
}
}
return array;
}
}
插入排序
Shell排序C#實現：
![]()
/// <summary>
/// shell排序
/// </summary>
public class ShellSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
int[] list = { 9, 5, 3, 2, 1 };
foreach (int k in list)
{
for (int i = k; i < array.Length; i++)
{
int current = array[i];
int preIndex = i - k;
while (preIndex >= 0 && preIndex < array.Length && current < array[preIndex])
{
array[preIndex + k] = array[preIndex];
preIndex = preIndex - k;
}
array[preIndex + k] = current;
}
}
}
return array;
}
}
shell排序
性能測試代碼：
![]()
class Program
{
public static Random re = new Random();
static void Main(string[] args)
{
Stopwatch stw1 = new Stopwatch();
Stopwatch stw2 = new Stopwatch();
Stopwatch stw3 = new Stopwatch();
int[] intArray1 = GetArray(int.MaxValue/100000);
int[] intArray2 = GetArray(int.MaxValue/100000);
int[] intArray3 = GetArray(int.MaxValue/100000);
ISort sort1 = new BubbleSort();//冒泡排序
stw1.Start();
int[] result1 = sort1.Sort(intArray1);
stw1.Stop();
Console.WriteLine("輸出排序的結果(冒泡排序)");
Console.WriteLine("程序共運行時間:" + stw1.Elapsed.ToString());
ISort sort2 = new InsertSort();//插入排序
stw2.Start();
int[] result2 = sort2.Sort(intArray2);
stw2.Stop();
Console.WriteLine("輸出排序的結果(插入排序)");
Console.WriteLine("程序共運行時間:" + stw2.Elapsed.ToString());
ISort sort3 = new ShellSort();//Shell排序
stw3.Start();
int[] result3 = sort3.Sort(intArray3);
stw3.Stop();
Console.WriteLine("輸出排序的結果(Shell排序)");
Console.WriteLine("程序共運行時間:" + stw3.Elapsed.ToString());
//輸出排序的結果
//OutputResult(result1, result2, result3);
Console.ReadKey();
}
}
性能測試
結果截圖：
