常用数据结构及算法C#实现
1.冒泡排序、选择排序、插入排序（三种简单非递归排序）
int[] waitSort = { ,, , , , , , , , , };
//冒泡排序
int length = waitSort.Length;
for (int i = ; i < length; i++)
{
for (int j = i + ; j < length; j++)
{
if (waitSort[j] > waitSort[i])
{
int temp = waitSort[j];
waitSort[j] = waitSort[i];
waitSort[i] = temp;
}
}
}
//选择排序
int pos1;
for (int i = ; i < length; i++)
{
pos1 = i;
for (int j = i + ; j < length; j++)
{
if (waitSort[pos1] < waitSort[j])
{
pos1 = j;
}
}
if (pos1 != i)
{
int temp = waitSort[pos1];
waitSort[pos1] = waitSort[i];
waitSort[i] = temp;
}
}
//插入排序
for (int i = ; i < length; i++)
{
for (int k = i; k > ; k--)
{
if (waitSort[k] > waitSort[k - ])
{
int temp = waitSort[k];
waitSort[k] = waitSort[k - ];
waitSort[k - ] = temp;
}
}
}
foreach (var i in waitSort)
{
Console.WriteLine(i);
}
Console.ReadKey();
2.快速排序
C#版：
static int[] a = { , , , , , , , , ,,,,,, };
static void Main(string[] args)
{
QuickSort(, a.Length - );
foreach (var t in a)
{
Console.WriteLine(t);
}
Console.ReadKey();
}
static void QuickSort(int low,int high)
{
if (low < high)
{
int partition=Partition(low,high);
QuickSort(low, partition-);
QuickSort(partition+, high);
}
}
static int Partition(int low, int high)
{
int point = a[low];
while (low < high)
{
while (a[high] <= point && low<high)
{
high--;
}
Swap(high, low);
while (a[low] >= point && low<high)
{
low++;
}
Swap(high, low);
}
return low;
}
static void Swap(int x, int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
Java版：
package test.JavaProject;
import org.junit.Test;
public class QuickSort {
@Test
public void test(){
int[] num = {1,5,6,9,8,7,5,3,5,4,1,2,6};
Qsort(num,0,num.length-1);
for(int n:num){
System.out.println(n);
}
}
public void Qsort(int[] num ,int left,int right){
if(left<right){
int p = partition(num,left,right);
Qsort(num,left,p-1);
Qsort(num,p+1,right);
}
}
public int partition(int[] num,int left,int right){
int pivot = num[left];
while(right>left){
while(left<right && num[right]>=pivot){
right--;
}
exchenge(num,left,right);
while(left<right && num[left]<=pivot){
left++;
}
exchenge(num,left,right);
}
return left;
}
public void exchenge(int[] num,int m,int n){
int temp = num[m];
num[m]=num[n];
num[n]=temp;
}
}
3.二叉排序树
namespace BinarySortTree
{
class Node
{
public int Num { get; set; }
public Node LChild { get; set; }
public Node RChild { get; set; }
} class BinarySortTree
{
public Node Root { get; set; }
public BinarySortTree()
{
Root = new Node();
}
} class Program
{
static void Main(string[] args)
{
int[] sort = { , , , , , , , , ,,, };
BinarySortTree bst = new BinarySortTree();
bst.Root.Num = ;
for (int i = ; i < sort.Length; i++)
{
InsertBst(bst.Root, sort[i]);
}
DFS(bst.Root);
Console.ReadKey();
} static void InsertBst(Node parent,int num)
{
if (num <= parent.Num)
{
if (parent.LChild == null)
{
parent.LChild = new Node();
parent.LChild.Num = num;
return;
}
else
{
InsertBst(parent.LChild, num);
}
}
else
{
if (parent.RChild == null)
{
parent.RChild = new Node();
parent.RChild.Num = num;
return;
}
else
{
InsertBst(parent.RChild, num);
}
}
} static void DFS(Node parent)
{ if (parent.LChild != null)
{
DFS(parent.LChild); }
Console.WriteLine(parent.Num); if (parent.RChild != null)
{
DFS(parent.RChild);
}
}
}
}
4.堆排
namespace HeapSort
{
class Program
{
static int[] a = new int[] { -,, , , , , , , , };
static void Main(string[] args)
{
HeapSort(a.Length-);
} static void HeapSort(int len)
{
//第一次调整得到最小堆，即k>2k+1 && k>2k
for (int i = len/; i >= ; i--)
{
Adjust(i, len);
} //第二次先交换第一个节点和最后一个节点，使堆顶元素最小，然后调整
for (int i = len; i >= ; i--)
{
Swap(, i);
Adjust(, i-);
}
} static void Swap(int m,int n)
{
int temp = a[m];
a[m] = a[n];
a[n] = temp;
} static void Adjust(int parent,int len)
{
int l = * parent;
int r = * parent + ;
int largest = parent;
//选出最大的节点，用于与父节点交换位置
if (l <=len && a[l] > a[largest])
{
largest = l;
}
if (r<=len && a[r]>a[largest])
{
largest = r;
}
//如果需要调整父节点，先交换然后调整交换节点与其孩子节点
if (largest != parent)
{
Swap(parent, largest);
Adjust(largest, len);
}
}
}
}
5.栈的实现
namespace 栈
{
public class MyStack
{
private int index = -;
private int[] a = new int[]; public void Push(int num)
{
a[++index] = num;
} public int? Pop()
{
if (index == -)
{
return null;
}
return a[index--];
}
}
} namespace 栈
{
class Program
{
static void Main(string[] args)
{
MyStack stack = new MyStack();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
int? temp;
while ((temp = stack.Pop()) != null)
{
Console.WriteLine(temp);
} stack.Push();
stack.Push();
stack.Push();
stack.Push();
while ((temp = stack.Pop()) != null)
{
Console.WriteLine(temp);
}
Console.ReadKey();
}
}
}
6.List实现
namespace MyList
{
public class Node
{
public int Num{get;set;}
public Node Next{get;set;}
} public class MyList
{
public Node Head { get; set; }
public int Length { get; set; } public MyList()
{
Head = new Node();
Head.Next = null;
Length = ;
} public void Add(int num)
{
Node n = new Node();
n.Num = num;
Node node = Head;
while (node.Next != null)
{
node = node.Next;
}
node.Next = n;
Length++;
} public void Delete(int index)
{
Node n = Head;
if (index == )
{
Head = n.Next;
}
else if(Length-==index)
{
for (int i = ; i < index - ; i++)
{
n = n.Next;
}
n.Next = null;
}
else
{
for (int i = ; i < index - ; i++)
{
n = n.Next;
}
n.Next = n.Next.Next;
}
Length--;
} public int this[int index]
{
get {
Node n = Head;
for (int i = ; i < index; i++)
{
n = n.Next;
}
return n.Num;
}
set {
Node n = Head;
for (int i = ; i < index; i++)
{
n = n.Next;
}
n.Num = value;
}
}
}
} namespace MyList
{
class Program
{
static void Main(string[] args)
{
MyList list = new MyList();
list.Head.Num = ;
list.Add();
list.Add();
list.Add();
list.Add();
list.Add(); Console.WriteLine("链表长度："+list.Length);
Node n = list.Head;
Console.WriteLine(n.Num);
while (n.Next != null)
{
n = n.Next;
Console.WriteLine(n.Num);
} Console.ReadKey();
}
}
}
7.DFS(深搜)/BFS(宽搜)
private static void DFS(XmlNode parent)
{
if (!parent.HasChildNodes)
{
return;
}
else if (parent.HasChildNodes)
{
for (int j = ; j < parent.ChildNodes.Count; j++)
{
if (parent.ChildNodes[j].Name == "span")
{
list.Add(parent.ChildNodes[j]);
}
DFS(parent.ChildNodes[j]);
}
}
} public static void BFS(XmlNode root)
{
queue.Enqueue(root);
while (queue.Count != )
{
XmlNode n = queue.Dequeue();
if (n.Name == "span")
{
list.Add(n);
}
for (int i = ; i < n.ChildNodes.Count; i++)
{
queue.Enqueue(n.ChildNodes[i]);
}
}
}
8.优先队列（堆实现）
namespace PriorityQueue
{
class Program
{
static List<int> list = new List<int>();
static void Main(string[] args)
{
list.Add(-); EnQueue();
EnQueue();
EnQueue();
EnQueue();
EnQueue();
EnQueue(); Console.WriteLine(DeQueue()); EnQueue();
EnQueue();
EnQueue(); int num = -;
while ((num = DeQueue()) != -)
{
Console.WriteLine(num);
}
Console.ReadKey();
} static void EnQueue(int num)
{
list.Add(num);
Adjust((list.Count-)/, list.Count-);
} static int DeQueue()
{
int len = list.Count-;
if (len == )
{
return -;
} Swap(, len);
int num = list[len];
list.RemoveAt(len); int len1 = list.Count - ;
Adjust(, len1);
return num;
} static void Adjust(int parent, int len)
{
if (parent == )
{
return;
}
int l = * parent;
int r = * parent + ;
int min = parent;
//选出最大的节点，用于与父节点交换位置
if (l <= len && list[l] > list[min])
{
min = l;
}
if (r <= len && list[r] > list[min])
{
min = r;
}
//如果需要调整父节点，先交换然后调整父节点的父节点
if (min != parent)
{
Swap(parent, min);
Adjust(parent/, len);
}
} static void Swap(int m, int n)
{
int temp = list[m];
list[m] = list[n];
list[n] = temp;
} }
}
9.归并排序
C#版：
namespace MergeSort
{
class Program
{
static int[] a = new int[] { ,,,, , , , , , , , ,,,,,,};
static void Main(string[] args)
{
MergeSort(, a.Length-);
} static void MergeSort(int first, int last)
{
if (first < last)
{
int mid = (first + last) / ;
MergeSort(first, mid);
MergeSort(mid + , last);
Merge(first, mid, last);
}
} static void Merge(int first, int mid, int last)
{
int[] temp = new int[last - first + ];
int l = first;
int r = mid + ;
int index = ; while (l <= mid && r <= last)
{
if (a[l] > a[r])
{
temp[index++] = a[l++];
}
else
{
temp[index++] = a[r++];
}
} while (l <= mid)
{
temp[index++] = a[l++];
}
while (r <= last)
{
temp[index++] = a[r++];
} index = ;
while (first <= last)
{
a[first++] = temp[index++];
}
}
}
}
Java版：
package test.JavaProject;
import org.junit.Test;
public class MergeSort {
@Test
public void test(){
int[] num = {1,5,6,9,8,7,5,3,5,4,1,2,6};
mergeSort(num,0,num.length-1);
for(int n:num){
System.out.println(n);
}
}
public void mergeSort(int[] num,int first,int last){
if(first<last){
int middle = (last+first)/2;
mergeSort(num,first,middle);
mergeSort(num,middle+1,last);
merge(num,first,middle,last);
}
}
public void merge(int[] num,int first,int mid,int last){
int[] temp = new int[last-first+1];
int l = first;
int r = mid+1;
int index=0;
while(l<=mid && r<=last){
if(num[l]<num[r]){
temp[index++]=num[l++];
}
else{
temp[index++]=num[r++];
}
}
while(l<=mid){
temp[index++]=num[l++];
}
while(r<=last){
temp[index++]=num[r++];
}
index=0;
while(first<=last){
num[first++]=temp[index++];
}
}
}
10.二分查找
namespace BinarySearch
{
class Program
{
static int[] search = {,,,,,,,,,};
static void Main(string[] args)
{
int target = BinarySearch();
Console.WriteLine("第"+target+"个数");
Console.WriteLine(search[target]);
Console.ReadKey();
} static int BinarySearch(int num)
{
int low = ;
int high = search.Length-;
while (high >= low)
{
int middle = (low + high) / ;
if (search[middle] == num)
{
return middle;
}
else if (search[middle] > num)
{
high = middle-;
}
else
{
low = middle + ;
}
}
return -;
}
}
}