選擇排序
選擇排序的基本思想是對待排序的記錄序列進行n
選擇排序是不穩定的
class SelectionSorter
{
private int min;
public void Sort(int[] arr)
{
for (int i =
{
min = i;
for (int j = i + 1; j < arr.Length; ++j)
{
if (arr[j] < arr[min])
min = j;
}
int t = arr[min];
arr[min] = arr[i];
arr[i] = t;
}
}
}
冒泡排序
冒泡排序方法是最簡單的排序方法。tw.WiNgWIt.Com這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮。在冒泡排序算法中我們要對這個“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個序列，並時刻注意兩個相鄰的元素的順序是否正確。如果發現兩個相鄰元素的順序不對，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之後，“最輕”的元素就浮到了最高位置；處理二遍之後，“次輕”的元素就浮到了次高位置。在作第二遍處理時，由於最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時，不必檢查第i高位置以上的元素，因為經過前面i-1遍的處理，它們已正確地排好序。
冒泡排序是穩定的。算法時間復雜度是O(n ^2)
class EbullitionSorter
{
public void Sort(int[] arr)
{
int i, j, temp;
bool done = false;
j = 1;
while ((j < arr.Length) && (!done))//判斷長度
{
done = true;
for (i = 0; i < arr.Length - j; i++)
{
if (arr[i] > arr[i + 1])
{
done = false;
temp = arr[i];
arr[i] = arr[i + 1];//交換數據
arr[i + 1] = temp;
}
}
j++;
}
}
}
快速排序
快速排序是對冒泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。快速排序通過一趟掃描，就能確保某個數（以它為基准點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基准點的左右只有一個元素為止。
快速排序是不穩定的。最理想情況算法時間復雜度O(nlog2n)，最壞O(n ^2)。
class QuickSorter
{
private void swap(ref int l, ref int r)
{
int temp;
temp = l;
l = r;
r = temp;
}
public void Sort(int[] list, int low, int high)
{
int pivot;//存儲分支點
int l, r;
int mid;
if (high <= low)
return;
else if (high == low + 1)
{
if (list[low] > list[high])
swap(ref list[low], ref list[high]);
return;
}
mid = (low + high) >> 1;
pivot = list[mid];
swap(ref list[low], ref list[mid]);
l = low + 1;
r = high;
do
{
while (l <= r && list[l] < pivot)
l++;
while (list[r] >= pivot)
r–;
if (l < r)
swap(ref list[l], ref list[r]);
} while (l < r);
list[low] = list[r];
list[r] = pivot;
if (low + 1 < r)
Sort(list, low, r - 1);
if (r + 1 < high)
Sort(list, r + 1, high);
}
}
插入排序
插入排序的基本思想是，經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
直接插入排序是穩定的。算法時間復雜度是O(n ^2) 。
public class InsertionSorter
{
public void Sort(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int t = arr[i];
int j = i;
while ((j > 0) && (arr[j - 1] > t))
{
arr[j] = arr[j - 1];//交換順序
–j;
}
arr[j] = t;
}
}
}
希爾排序
希爾排序基本思想： 先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2
{
public void Sort(int[] arr)
{
int inc;
for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i <= arr.Length; i += inc)
{
int t = arr[i - 1];
int j = i;
while ((j > inc) && (arr[j - inc - 1] > t))
{
arr[j - 1] = arr[j - inc - 1];//交換數據
j -= inc;
}
arr[j - 1] = t;
}
}
}
}
歸並排序
設有兩個有序（升序）序列存儲在同一數組中相鄰的位置上，不妨設為A[l..m]，A[m+1..h]，將它們歸並為一個有序數列，並存儲在A[l..h]。
其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。
///
///
///
無序的數組
///
/// Lihua()
int[] Sort(int[] data)
{
//取數組中間下標
int middle = data.Length / 2;
//初始化臨時數組let,right，並定義result作為最終有序數組
int[] left = new int[middle], right = new int[middle], result = new int[data.Length];
if (data.Length % 2 != 0)//若數組元素奇數個，重新初始化右臨時數組
{
right = new int[middle + 1];
}
if (data.Length <= 1)//只剩下1 or 0個元數，返回，不排序
{
return data;
}
int i = 0, j = 0;
foreach (int x in data)//開始排序
{
if (i < middle)//填充左數組
{
left[i] = x;
i++;
}
else//填充右數組
{
right[j] = x;
j++;
}
}
left = Sort(left);//遞歸左數組
right = Sort(right);//遞歸右數組
result = Merge(left, right);//開始排序
//this.Write(result);//輸出排序,測試用(lihua debug)
return result;
}
///
///
///
左數組 ///
右數組
///
int[] Merge(int[] a, int[] b)
{
//定義結果數組，用來存儲最終結果
int[] result = new int[a.Length + b.Length];
int i = 0, j = 0, k = 0;
while (i < a.Length && j < b.Length)
{
if (a[i] < b[j])//左數組中元素小於右數組中元素
{
result[k++] = a[i++];//將小的那個放到結果數組
}
else//左數組中元素大於右數組中元素
{
result[k++] = b[j++];//將小的那個放到結果數組
}
}
while (i < a.Length)//這裡其實是還有左元素，但沒有右元素
{
result[k++] = a[i++];
}
while (j < b.Length)//右右元素，無左元素
{
result[k++] = b[j++];
}
return result;//返回結果數組
}
注：此算法由周利華提供（
）
基數排序
基數排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的比較性排序法。
//基數排序
public int[] RadixSort(int[] ArrayToSort, int digit)
{
//low to high digit
for (int k = 1; k <= digit; k++)
{
//temp array to store the sort result inside digit
int[] tmpArray = new int[ArrayToSort.Length];
//temp array for countingsort
int[] tmpCountingSortArray = new int[10]{0,0,0,0,0,0,0,0,0,0};
//CountingSort
for (int i = 0; i < ArrayToSort.Length; i++)
{
//split the specified digit from the element
int tmpSplitDigit = ArrayToSort[i]/(int)Math.Pow(10,k-1) - (ArrayToSort[i]/(int)Math.Pow(10,k))*10;
tmpCountingSortArray[tmpSplitDigit] += 1;
}
for (int m = 1; m < 10; m++)
{
tmpCountingSortArray[m] += tmpCountingSortArray[m - 1];
}
//output the value to result
for (int n = ArrayToSort.Length - 1; n >= 0; n–)
{
int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10,k – 1) – (ArrayToSort[n]/(int)Math.Pow(10,k)) * 10;
tmpArray[tmpCountingSortArray[tmpSplitDigit]-1] = ArrayToSort[n];
tmpCountingSortArray[tmpSplitDigit] -= 1;
}
//copy the digit-inside sort result to source array
for (int p = 0; p < ArrayToSort.Length; p++)
{
ArrayToSort[p] = tmpArray[p];
}
}
return ArrayToSort;
}
計數排序
數排序, 基數排序, 桶排序等非比較排序算法,平均時間復雜度都是O(n). 這些排序因為其待排序元素本身就含有了定位特征,因而不需要比較就可以確定其前後位置,從而可以突破比較排序算法時間復雜度O(nlgn)的理論下限.
計數排序是最簡單的特例,它要 求待排序元素是位於0到k之間的正整數 , 因而它是很特殊的情況,基本上沒有特別的應用價值; 但是另一方面, 它又是基數排序的基礎,或者說是一部分,所以簡單的描述一下:
輸入數組 A : 元素特征是 0-k的正整數,可以有重復值;
輸出數組 B : 輸出A的一個非減序列
中間數組 C : 大小是k, 它的i( 0<= i <= k)索引位置存儲的是A元素集合中值是k的元素的個數有關.
算法的基本思想是:
統計A中元素的值的集合, 以A中元素的值為索引, 將值的個數填寫到中間數組C的對應處.
對C從頭開始自累加, 這樣C中存儲的就是, 當輸入數組A中的值為當前索引時, 它前面的元素數量(包含重復元素).
將C依次輸出到輸出數組B中.
///
///
///
input array ///
the value arrange in input array
///
public int[] CountingSort(int[] arrayA, int arrange)
{
//array to store the sorted result,
//size is the same with input array.
int[] arrayResult = new int[arrayA.Length];
//array to store the direct value in sorting process
//include index 0;
//size is arrange+1;
int[] arrayTemp = new int[arrange+1];
//clear up the temp array
for(int i = 0; i <= arrange; i++)
{
arrayTemp[i] = 0;
}
//now temp array stores the count of value equal
for(int j = 0; j < arrayA.Length; j++)
{
arrayTemp[arrayA[j]] += 1;
}
//now temp array stores the count of value lower and equal
for(int k = 1; k <= arrange; k++)
{
arrayTemp[k] += arrayTemp[k - 1];
}
//output the value to result
for (int m = arrayA.Length-1; m >= 0; m–)
{
arrayResult[arrayTemp[arrayA[m]] – 1] = arrayA[m];
arrayTemp[arrayA[m]] -= 1;
}
return arrayResult;
}
根堆排序
堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
堆排序是不穩定的。算法時間復雜度O(nlog n)。
///
///
///
///
///
private void HeapSort(ref double[] dblArray)
{
for (int i = dblArray.Length – 1; i >= 0; i–)
{
if (2 * i + 1 < dblArray.Length)
{
int MinChildrenIndex = 2 * i + 1;
//比較左子樹和右子樹，記錄最小值的Index
if (2 * i + 2 < dblArray.Length)
{
if (dblArray[2 * i + 1] > dblArray[2 * i + 2])
MinChildrenIndex = 2 * i + 2;
}
if (dblArray[i] > dblArray[MinChildrenIndex])
{
ExchageValue(ref dblArray[i], ref dblArray[MinChildrenIndex]);
NodeSort(ref dblArray, MinChildrenIndex);
}
}
}
}
///
///
///
///
private void NodeSort(ref double[] dblArray, int StartIndex)
{
while (2 * StartIndex + 1 < dblArray.Length)
{
int MinChildrenIndex = 2 * StartIndex + 1;
if (2 * StartIndex + 2 < dblArray.Length)
{
if (dblArray[2 * StartIndex + 1] > dblArray[2 * StartIndex + 2])
{
MinChildrenIndex = 2 * StartIndex + 2;
}
}
if (dblArray[StartIndex] > dblArray[MinChildrenIndex])
{
ExchageValue(ref dblArray[StartIndex], ref dblArray[MinChildrenIndex]);
StartIndex = MinChildrenIndex;
}
}
}
///
///
///
///
private void ExchageValue(ref double A, ref double B)
{
double Temp = A;
A = B;
B = Temp;
}
From:http://tw.wingwit.com/Article/program/sjjg/201405/30939.html