三大高級排序
1、堆排序
堆排序適合於數據量非常大的場合（百萬數據）。
堆排序不需要大量的遞歸或者多維的暫存數組。
這對於數據量非常巨大的序列是合適的。
比如超過數百萬條記錄，因為快速排序，歸並排序都使用遞歸來設計算法，
在數據量非常大的時候，可能會發生堆棧溢出錯誤。
堆排序會將所有的數據建成一個堆，最大的數據在堆頂，
然後將堆頂數據和序列的最後一個數據交換。
接下來再次重建堆，交換數據，依次下去，就可以排序所有的數據。
![]()
/// <summary>
/// 堆排序
/// </summary>
public class HeapSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
HeapHanle(array, array.Length);//整理了堆結構
for (int i = array.Length - 1; i >= 0; i--)
{
Swap(ref array[0], ref array[i]);
if (i > 1)
{
HeapToDown(array, 0, i);
}
}
}
return array;
}
/// <summary>
/// 整理堆結構
/// </summary>
/// <param name="array"></param>
/// <param name="length"></param>
private static void HeapHanle(int[] array, int length)
{
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapToDown(array, i, length);
}
}
/// <summary>
/// 從下往上處理
/// </summary>
/// <param name="array">數組</param>
/// <param name="i">給定的節點數組索引</param>
private static void HeapToUp(int[] array, int i)
{
int cur = array[i];
int preIndex = (i - 1) / 2;
while (i > 0 && preIndex >= 0 && cur < array[preIndex])
{
array[preIndex] = cur;
i = preIndex;
preIndex = (i - 1) / 2;
}
array[i] = cur;
}
/// <summary>
/// 從上往下處理
/// </summary>
/// <param name="array">數組</param>
/// <param name="i">給定的節點數組索引</param>
private static void HeapToDown(int[] array, int i, int length)
{
int cur = array[i];
int nextIndex = 2 * i + 1;//左孩子對應的數組索引
while (nextIndex < length)
{
if (nextIndex + 1 < length)
{
if (array[nextIndex] > array[nextIndex + 1])
{
nextIndex = nextIndex + 1;//右孩子
}
}
if (cur <= array[nextIndex])
{
break;
}
else//處理
{
array[i] = array[nextIndex];
i = nextIndex;
nextIndex = 2 * i + 1;
}
}
array[i] = cur;
}
public static void Swap(ref int int1, ref int int2)
{
int temp = int1;
int1 = int2;
int2 = temp;
}
}
堆排序
2、歸並排序
歸並排序先分解要排序的序列，從1分成2，2分成4，依次分解，
當分解到只有1個一組的時候，就可以排序這些分組，
然後依次合並回原來的序列中，這樣就可以排序所有數據。
合並排序比堆排序稍微快一點，但是需要比堆排序多一倍的內存空間，
因為它需要一個額外的數組。
![]()
/// <summary>
/// 歸並排序
/// </summary>
public class MergeSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
int[] temp = new int[array.Length];
SortLeftAndRight(array, 0, array.Length - 1, temp);
}
return array;
}
/// <summary>
/// 對array[first]-array[middle]和array[middle+1]-array[last]進行並歸
/// </summary>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="middle"></param>
/// <param name="last"></param>
/// <param name="temp"></param>
private void Merge(int[] array, int first, int middle, int last, int[] temp)
{
int i = first;
int n = middle;
int j = middle + 1;
int m = last;
int k = 0;
while (i <= n && j <= m)
{
if (array[i] <= array[j])
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
}
}
while (i <= n)
{
temp[k++] = array[i++];
}
while (j <= m)
{
temp[k++] = array[j++];
}
for (i = 0; i < k; i++)
{
array[first + i] = temp[i];
}
}
/// <summary>
/// 遞歸分治
/// </summary>
/// <param name="array"></param>
/// <param name="first"></param>
/// <param name="last"></param>
/// <param name="temp"></param>
private void SortLeftAndRight(int[] array, int first, int last, int[] temp)
{
if (first < last)
{
int middle = (first + last) / 2;
SortLeftAndRight(array, first, middle, temp);
SortLeftAndRight(array, middle + 1, last, temp);
Merge(array, first, middle, last, temp);
}
}
}
歸並排序
3、快速排序
快速排序是一個就地排序，分而治之，大規模遞歸的算法。
從本質上來說，它是歸並排序的就地版本。
快速排序可以由下面四步組成。
（1） 如果不多於1個數據，直接返回。
（2） 一般選擇序列最左邊的值作為支點數據。
（3） 將序列分成2部分，一部分都大於支點數據，另外一部分都小於支點數據。
（4） 對兩邊利用遞歸排序數列。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，
但是就通常情況而言，沒有比它更快的了。
快速排序是遞歸的，對於內存非常有限的機器來說，它不是一個好的選擇。
![]()
/// <summary>
/// 快速排序
/// </summary>
public class QuickSort : ISort
{
public int[] Sort(int[] array)
{
if (array != null)
{
int[] temp = new int[array.Length];
QuickSorting(array, 0, array.Length - 1);
}
return array;
}
private static void QuickSorting(int[] array, int l, int r)
{
if (l < r)
{
int i = l;
int j = r;
int temp = array[i];
while (i < j)
{
while (i < j && array[j] >= temp)
{
j--;
}
if (i < j)
{
array[i++] = array[j];
}
while (i < j && array[i] < temp)
{
i++;
}
if (i < j)
{
array[j--] = array[i];
}
}
array[i] = temp;
QuickSorting(array, l, i - 1);
QuickSorting(array, i + 1, r);
}
}
}
快速排序
測試代碼：
![]()
class Program
{
public static Random re = new Random();
static void Main(string[] args)
{
Stopwatch stw4 = new Stopwatch();
Stopwatch stw5 = new Stopwatch();
Stopwatch stw6 = new Stopwatch();
int[] intArray4 = GetArray(int.MaxValue / 100000);
int[] intArray5 = GetArray(int.MaxValue / 100000);
int[] intArray6 = GetArray(int.MaxValue / 100000);
ISort sort4 = new HeapSort();//堆排序
stw4.Start();
int[] result4 = sort4.Sort(intArray4);
stw4.Stop();
Console.WriteLine("輸出排序的結果(堆排序)");
Console.WriteLine("程序共運行時間:" + stw4.Elapsed.ToString());
ISort sort5 = new MergeSort();//歸並排序
stw5.Start();
int[] result5 = sort5.Sort(intArray5);
stw5.Stop();
Console.WriteLine("輸出排序的結果(歸並排序)");
Console.WriteLine("程序共運行時間:" + stw5.Elapsed.ToString());
ISort sort6 = new QuickSort();//快速排序
stw6.Start();
int[] result6 = sort6.Sort(intArray6);
stw6.Stop();
Console.WriteLine("輸出排序的結果(快速排序)");
Console.WriteLine("程序共運行時間:" + stw6.Elapsed.ToString());
Console.ReadKey();
}
private static int[] GetArray(long _arrayLength)
{
long arrayLength = _arrayLength;
//初始化數組
int[] intArray = new int[arrayLength];
for (int i = 0; i < arrayLength; i++)
{
intArray[i] = re.Next();
}
return intArray;
}
}
View Code
測試結果截圖：
