1.快速排序
這種排序是.net中使用的，均衡性比較好，效率相對來說最高，
protected void Page_Load(object sender, EventArgs e)
{
int[] arr = {7,6,5,4,3,2,1};
List<int> list = arr.ToList<int>();
QuickSortClass qu = new QuickSortClass();
Response.Write("<br><br><br>");
//qu.show(list, " ");
Response.Write("<br><br><br><br>");
qu.QuickSort(list, 0, list.Count - 1);
//Response.Write(qu.count);
}
}
public class QuickSortClass
{
public int count = 0;
///<summary>
/// 分割函數
///</summary>
///<param name="list">待排序的數組</param>
///<param name="left">數組的左下标</param>
///<param name="right"></param>
///<returns></returns>
public int Division(List<int> list, int left, int right)
{
show(list, " List:");
//首先挑選一個基準元素
int baseNum = list[left];
HttpContext.Current.Response.Write(" Left:" + left + " Right:" + right + "<br>");
while (left < right)
{
count++;
//從數組的右端開始向前找，一直找到比base小的數字為止(包括base同等數)
while (left < right && list[right] >= baseNum)
right = right - 1;
//最終找到了比baseNum小的元素，要做的事情就是此元素放到base的位置
list[left] = list[right];
show(list," Righ:");
//從數組的左端開始向後找，一直找到比base大的數字為止（包括base同等數）
while (left < right && list[left] <= baseNum)
left = left + 1;
//最終找到了比baseNum大的元素，要做的事情就是将此元素放到最後的位置
list[right] = list[left];
show(list, " Left:");
}
//最後就是把baseNum放到該left的位置
list[left] = baseNum;
show(list, " Last:");
HttpContext.Current.Response.Write("<br><br><br>");
//最終，我們發現left位置的左側數值部分比left小，left位置右側數值比left大
//至此，我們完成了第一篇排序
return left;
}
public void QuickSort(List<int> list, int left, int right)
{
//左下标一定小于右下标，否則就超越了
if (left < right)
{
//對數組進行分割，取出下次分割的基準标号
int i = Division(list, left, right);
HttpContext.Current.Response.Write("I:" + i+"<br>");
//對“基準标号“左側的一組數值進行遞歸的切割，以至于将這些數值完整的排序
HttpContext.Current.Response.Write("對“基準标号“左側的一組數值進行遞歸的切割，以至于将這些數值完整的排序<br>");
QuickSort(list, left, i - 1);
//對“基準标号“右側的一組數值進行遞歸的切割，以至于将這些數值完整的排序
HttpContext.Current.Response.Write("對“基準标号“右側的一組數值進行遞歸的切割，以至于将這些數值完整的排序<br>");
QuickSort(list, i + 1, right);
}
//HttpContext.Current.Response.Write("count:"+count + "<br>");
}
public void show(List<int> list,string a)
{
if (list == null) return;
StringBuilder strBuilder = new StringBuilder();
strBuilder.Append("<span style='width:40px'>"+a+"</span>");
foreach (var li in list)
{
strBuilder.Append(" " + li.ToString());
}
HttpContext.Current.Response.Write(strBuilder.ToString() + "<br><br>");
}
} 堆排序
除了最後一個父節點以外，每個父節點都必須有兩個子節點
大根堆： 就是說父節點要比左右孩子都要大。
小根堆： 就是說父節點要比左右孩子都要小。
每次重構以後發現位置不一定一樣，但是根節點一定是一樣的。
這種排序在找數組中最大，最小的值時效率最高，幾個也行，找的值越多，效率越低。
protected void Page_Load(object sender, EventArgs e)
{
int[] arr = {9,7,8,6,3,4,1,5,2};
List<int> list = arr.ToList<int>();
HeapSort(list);
show(list, "");
}
///<summary>
/// 建構堆
///</summary>
///<param name="list">待排序的集合</param>
///<param name="parent">父節點</param>
///<param name="length">輸出根堆時剔除最大值使用</param>
public static void HeapAdjust(List<int> list, int parent, int length)
{
show(list, "I:" + parent.ToString() + ",Length:" + length.ToString()+" ");
//temp儲存目前父節點
int temp = list[parent];
//得到左孩子(這可是二叉樹的定義，大家看圖也可知道)
int child = 2 * parent + 1;
while (child < length) //判斷該節點是否還有子節點
{
//如果parent有右孩子，則要判斷左孩子是否小于右孩子
if (child + 1 < length && list[child] < list[child + 1])
child++;
//父親節點大于子節點，就不用做交換
if (temp >= list[child])
break;
//将較大子節點的值賦給父親節點
list[parent] = list[child];
//然後将子節點做為父親節點，已防止是否破壞根堆時重新構造
parent = child;
//找到該父親節點較小的左孩子節點
child = 2 * parent + 1;
}
//最後将temp值賦給較大的子節點，以形成兩值交換
list[parent] = temp;
}
///<summary>
/// 堆排序
///</summary>
///<param name="list"></param>
public static void HeapSort(List<int> list)
{
//list.Count/2-1:就是堆中父節點的個數
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
HeapAdjust(list, i, list.Count);
}
//上面就是按照數組建立一個二叉樹，符合二叉樹的标準，是大根堆，最上面的就是最大的，父節點比子節點大
HttpContext.Current.Response.Write("-----------------<br>");
//最後輸出堆元素，在每次建構堆後，list[0]都是最大的，每次找出最大的放在數組最後，再把二叉樹的長度減1，形成的由小到大排列
for (int i = list.Count - 1; i > 0; i--)
{
//堆頂與目前堆的第i個元素進行值對調
int temp = list[0];
list[0] = list[i];
list[i] = temp;
//因為兩值交換，可能破壞根堆，是以必須重新構造
HeapAdjust(list, 0, i); //在把現有的二叉樹内的最大值找出，i是二叉樹的長度
show(list, "List: ");
}
}
public static void show(List<int> list, string a="")
{
if (list == null) return;
StringBuilder strBuilder = new StringBuilder();
strBuilder.Append("<span style='width:40px'>" + a + "</span>");
foreach (var li in list)
{
strBuilder.Append(" " + li.ToString());
}
HttpContext.Current.Response.Write(strBuilder.ToString() + "<br><br>");
} 二叉排序樹（主要應用于查找)
若根節點有左子樹，則左子樹的所有節點都比根節點小。
若根節點有右子樹，則右子樹的所有節點都比根節點大。
看出節點的左右子節點都可以存在，每次添加元素時位置是唯一的
public partial class Default2 : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
List<int> list = new List<int>() { 50, 30, 70, 10, 40, 90, 80 };
BSTree bsTree = CreateBST(list);
//中序周遊
LDR_BST(bsTree);
Response.Write("<br>");
bool isExist = SearchBST(bsTree, 40);
Response.Write(isExist.ToString());
}
///<summary>
/// 定義一個二叉排序樹結構
///</summary>
public class BSTree
{
public int data;
public BSTree left;
public BSTree right;
}
///<summary>
/// 二叉排序樹的插入操作
///</summary>
///<param name="bsTree">排序樹</param>
///<param name="key">插入數</param>
///<param name="isExcute">是否執行了if語句</param>
static void InsertBST(BSTree bsTree, int key, ref bool isExcute)
{
if (bsTree == null)
return;
//如果父節點大于key，則周遊左子樹
if (bsTree.data > key)
InsertBST(bsTree.left, key, ref isExcute);
else
InsertBST(bsTree.right, key, ref isExcute);
if (!isExcute)
{
//建構目前節點
BSTree current = new BSTree()
{
data = key,
left = null,
right = null
};
//插入到父節點的目前元素
if (bsTree.data > key)
bsTree.left = current;
else
bsTree.right = current;
isExcute = true;
}
}
///<summary>
/// 建立二叉排序樹
///</summary>
///<param name="list"></param>
static BSTree CreateBST(List<int> list)
{
//建構BST中的根節點
BSTree bsTree = new BSTree()
{
data = list[0],
left = null,
right = null
};
for (int i = 1; i < list.Count; i++)
{
bool isExcute = false;
InsertBST(bsTree, list[i], ref isExcute);
}
return bsTree;
}
///<summary>
/// 在排序二叉樹中搜尋指定節點
///</summary>
///<param name="bsTree"></param>
///<param name="key"></param>
///<returns></returns>
static bool SearchBST(BSTree bsTree, int key)
{
//如果bsTree為空，說明已經周遊到頭了
if (bsTree == null)
return false;
if (bsTree.data == key)
return true;
if (bsTree.data > key)
return SearchBST(bsTree.left, key);
else
return SearchBST(bsTree.right, key);
}
///<summary>
/// 中序周遊二叉排序樹
///</summary>
///<param name="bsTree"></param>
///<returns></returns>
static void LDR_BST(BSTree bsTree)
{
if (bsTree != null)
{
//周遊左子樹
LDR_BST(bsTree.left);
//輸入節點資料
HttpContext.Current.Response.Write(bsTree.data + "||");
//周遊右子樹
LDR_BST(bsTree.right);
}
}
///<summary>
/// 删除二叉排序樹中指定key節點
///</summary>
///<param name="bsTree"></param>
///<param name="key"></param>
static void DeleteBST(ref BSTree bsTree, int key)
{
if (bsTree == null) //循環到底了，沒有指定key的節點
return;
if (bsTree.data == key)
{
//第一種情況：葉子節點
if (bsTree.left == null && bsTree.right == null)
{
bsTree = null;
return;
}
//第二種情況：左子樹不為空
if (bsTree.left != null && bsTree.right == null)
{
bsTree = bsTree.left;
return;
}
//第三種情況，右子樹不為空
if (bsTree.left == null && bsTree.right != null)
{
bsTree = bsTree.right;
return;
}
//第四種情況，左右子樹都不為空
if (bsTree.left != null && bsTree.right != null)
{
var node = bsTree.right;
//找到右子樹中的最左節點
while (node.left != null)
{
//周遊它的左子樹
node = node.left;
}
//交換左右孩子
node.left = bsTree.left;
//判斷是真正的葉子節點還是空左孩子的父節點
if (node.right == null)
{
//删除掉右子樹最左節點
DeleteBST(ref bsTree, node.data);
node.right = bsTree.right;
}
//重新指派一下
bsTree = node;
}
}
if (bsTree.data > key)
{
DeleteBST(ref bsTree.left, key);
}
else
{
DeleteBST(ref bsTree.right, key);
}
}
public static void show(List<int> list, string a = "")
{
if (list == null) return;
StringBuilder strBuilder = new StringBuilder();
strBuilder.Append("<span style='width:40px'>" + a + "</span>");
foreach (var li in list)
{
strBuilder.Append(" " + li.ToString());
}
HttpContext.Current.Response.Write(strBuilder.ToString() + "<br><br>");
}
} 可以看出這種方式也可以排序，每次排序時先找一個根節點
每次插入元素時循環判斷大小，找到唯一的位置插入。
查詢：最左邊的節點的左葉節點-->最左邊的節點-->最左邊的節點的右葉節點-->父節點-->
判斷是否有節點（有的話 左葉節點-->節點-->右節點）。。。。