本文讲述了常见的四种排序算法:冒泡排序,选择排序,插入排序,快速排序
并给出了在.net中实现这些算法的代码,
(文中程序均默认按升序处理,即数组为从小到大排序)
一 冒泡排序
[算法描述]
给出N个数,
用第1个与第2个比较,如果N[1]>N[2],则让N[1]与N[2]交换;
用第2个与第3个比较,如果N[2]>N[3],则让N[2]与N[3]交换;
………………
用第N-1个与第N个比较,如果N[N-1]>N[N],则让N[N-1]与N[N]交换;
这样比较一圈后,最大的数就到最后,接着对剩下的N-1个数进行上述的处理,
把这N-1个数中最大的数放到第N-1的位置上,
到最后就排序OK了.由于过程象气泡冒出来,就叫冒泡算法。
protected static void MaoPaoSort1(int[] arr){
for(int i=1;i<arr.Length;i++){ //从1到N循环
if(arr[j] > arr[j+1]){
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}//end MaoPaoSort1 func
for(int i=0;i<arr.Length-1;i++){
for(int j=arr.Length-1;j>i;j--){
if(arr[j-1] > arr[j]){
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
}//end MaoPaoSort2 func
二 选择排序
[算法描述]
扫描所有数据,选择最小的数据与第1个数据互换;
protected static void SelectSort(int[] arr){
for(int i=0;i<arr.Length-1;i++){
int smallNo = i;
for(int j=i+1;j<arr.Length;j++){
if(arr[j] < arr[smallNo]){
smallNo = j; //选出最小数的序号
}
}
int tmp = arr[i];
arr[i] = arr[smallNo];
arr[smallNo] = tmp;
}
}//end SelectSort func
[算法描述]
protected static void InsertSort(int[] arr){
int ins,i=0,j=0;
for(i=1;i<arr.Length;i++){
ins = arr[i]; //等待插入的元素
if(ins < arr[i-1]){ //i之前(不包括i)的元素是已经排序好的
j = i-1;
while( j>=0 && ins < arr[j]){//这里需要注意一下:不能写成 ins < arr[j] &&j>=0
arr[j+1] = arr[j]; //把大于ins的元素依次后移
j--; //后移直到让出ins的位置为止
}
arr[j+1] = ins;
}
}//end for i
}//end InsertSort func
四 快速排序
[算法描述]
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
2.将中间元素左边大于参考值的与中间元素右边小于参考值的元素互换位置;
3.把中间元素左边的所有元素看成数组,递归执行1~4的操作;
4.对中间元素右边的所有元素看成数组,递归执行1~4的操作;
[源程序]
protected static void QuickSort(int[] arr,int leftNo, int rightNo){
int mid = (int)Math.Floor((leftNo + rightNo) / 2);//取得中间点
//Math.Floor(3.6)=3;Math.Ceiling(3.1)=4,用这两种方法都可以
int i = leftNo;
int j = rightNo;
do{
while(arr[i] < arr[mid])i++;
while(arr[j] > arr[mid])j--;
if(i <= j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}while(i<=j);
if(leftNo < j) QuickSort(arr,leftNo,j);
if(rightNo > i)QuickSort(arr,i,rightNo);
}//end QuickSort func
代码下载参见全文链接: http://beinet.cn/blog/?tid=36。