C#所有经典排序算法汇总

1、选择排序
选择排序
classSelectionSorter
{
privateintmin;
publicvoidSort(int[]arr)
{
for(inti=0;i<arr.Length-1;++i)
{
min=i;
for(intj=i+1;j<arr.Length;++j)
{
if(arr[j]<arr[min])
min=j;
}
intt=arr[min];
arr[min]=arr[i];
arr[i]=t;
}
}
}
2、冒泡排序
冒泡排序
classEbullitionSorter
{
publicvoidSort(int[]arr)
{
inti,j,temp;
booldone=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++;
}
}
}
3、快速排序
快速排序
classQuickSorter
{
privatevoidswap(refintl,refintr)
{
inttemp;
temp=l;
l=r;
r=temp;
}
publicvoidSort(int[]list,intlow,inthigh)
{
intpivot;//存储分支点
intl,r;
intmid;
if(high<=low)
return;
elseif(high==low+1)
{
if(list[low]>list[high])
swap(reflist[low],reflist[high]);
return;
}
mid=(low+high)>>1;
pivot=list[mid];
swap(reflist[low],reflist[mid]);
l=low+1;
r=high;
do
{
while(l<=r&&list[l]<pivot)
l++;
while(list[r]>=pivot)
r–;
if(l<r)
swap(reflist[l],reflist[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);
}
}
4、插入排序
插入排序
publicclassInsertionSorter
{
publicvoidSort(int[]arr)
{
for(inti=1;i<arr.Length;i++)
{
intt=arr[i];
intj=i;
while((j>0)&&(arr[j-1]>t))
{
arr[j]=arr[j-1];//交流次第
–j;
}
arr[j]=t;
}
}
}
5、希尔排序
希尔排序
publicclassShellSorter
{
publicvoidSort(int[]arr)
{
intinc;
for(inc=1;inc<=arr.Length/9;inc=3*inc+1);
for(;inc>0;inc/=3)
{
for(inti=inc+1;i<=arr.Length;i+=inc)
{
intt=arr[i-1];
intj=i;
while((j>inc)&&(arr[j-inc-1]>t))
{
arr[j-1]=arr[j-inc-1];//交流数据
j-=inc;
}
arr[j-1]=t;
}
}
}
}
6、归并排序
归并排序
///
///归并排序之归：归并排序入口
///
///无序的数组
///有序数组
///Lihua(www.zivsoft.com)
int[]Sort(int[]data)
{
//取数组中间下标
intmiddle=data.Length/2;
//初始化暂时数组let,right，并定义result作为最终有序数组
int[]left=newint[middle],right=newint[middle],result=newint[data.Length];
if(data.Length%2!=0)//若数组元素奇数个，重新初始化右暂时数组
{
right=newint[middle+1];
}
if(data.Length<=1)//只剩下1or0个元数，返回，不排序
{
returndata;
}
inti=0,j=0;
foreach(intxindata)//开端排序
{
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);//输出排序,测试用(lihuadebug)
returnresult;
}
///
///归并排序之并:排序在这一步
///
///左数组
///右数组
///兼并左右数组排序后返回
int[]Merge(int[]a,int[]b)
{
//定义结果数组，用来存储最终结果
int[]result=newint[a.Length+b.Length];
inti=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++];
}
returnresult;//返回结果数组
}
注：此算法由周利华提供（http://www.cnblogs.com/architect/archive/2009/05/06/1450489.html
）
7、基数排序
基数排序
//基数排序
publicint[]RadixSort(int[]ArrayToSort,intdigit)
{
//lowtohighdigit
for(intk=1;k<=digit;k++)
{
//temparraytostorethesortresultinsidedigit
int[]tmpArray=newint[ArrayToSort.Length];
//temparrayforcountingsort
int[]tmpCountingSortArray=newint[10]{0,0,0,0,0,0,0,0,0,0};
//CountingSort
for(inti=0;i<ArrayToSort.Length;i++)
{
//splitthespecifieddigitfromtheelement
inttmpSplitDigit=ArrayToSort[i]/(int)Math.Pow(10,k-1)-(ArrayToSort[i]/(int)Math.Pow(10,k))*10;
tmpCountingSortArray[tmpSplitDigit]+=1;
}
for(intm=1;m<10;m++)
{
tmpCountingSortArray[m]+=tmpCountingSortArray[m-1];
}
//outputthevaluetoresult
for(intn=ArrayToSort.Length-1;n>=0;n–)
{
inttmpSplitDigit=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;
}
//copythedigit-insidesortresulttosourcearray
for(intp=0;p<ArrayToSort.Length;p++)
{
ArrayToSort[p]=tmpArray[p];
}
}
returnArrayToSort;
}
8、计数排序
计数排序
//计数排序
///
///countingsort
///
///inputarray
///thevaluearrangeininputarray
///
publicint[]CountingSort(int[]arrayA,intarrange)
{
//arraytostorethesortedresult,
//sizeisthesamewithinputarray.
int[]arrayResult=newint[arrayA.Length];
//arraytostorethedirectvalueinsortingprocess
//includeindex0;
//sizeisarrange+1;
int[]arrayTemp=newint[arrange+1];
//clearupthetemparray
for(inti=0;i<=arrange;i++)
{
arrayTemp[i]=0;
}
//nowtemparraystoresthecountofvalueequal
for(intj=0;j<arrayA.Length;j++)
{
arrayTemp[arrayA[j]]+=1;
}
//nowtemparraystoresthecountofvaluelowerandequal
for(intk=1;k<=arrange;k++)
{
arrayTemp[k]+=arrayTemp[k-1];
}
//outputthevaluetoresult
for(intm=arrayA.Length-1;m>=0;m–)
{
arrayResult[arrayTemp[arrayA[m]]-1]=arrayA[m];
arrayTemp[arrayA[m]]-=1;
}
returnarrayResult;
}
9、小根堆排序
小根堆排序
///
///小根堆排序
///
///
///
///
privatevoidHeapSort(refdouble[]dblArray)
{
for(inti=dblArray.Length-1;i>=0;i–)
{
if(2*i+1<dblArray.Length)
{
intMinChildrenIndex=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(refdblArray[i],refdblArray[MinChildrenIndex]);
NodeSort(refdblArray,MinChildrenIndex);
}
}
}
}
///
///节点排序
///
///
///
privatevoidNodeSort(refdouble[]dblArray,intStartIndex)
{
while(2*StartIndex+1<dblArray.Length)
{
intMinChildrenIndex=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(refdblArray[StartIndex],refdblArray[MinChildrenIndex]);
StartIndex=MinChildrenIndex;
}
}
}
///
///交流值
///
///
///
privatevoidExchageValue(refdoubleA,refdoubleB)
{
doubleTemp=A;
A=B;
B=Temp;
}