排序--交换排序(Exchange Sort)

andyyuduo

一.冒泡排序
　　冒泡排序（Bubble Sort)是一种简单的交换排序算法，它的基本思想是对所有相邻记录进行比较，如果是逆序，则将二者进行交换，最终达到有序，代码如下：
using System;
namespace BubbleSort
{
class Program
{
public static void Main(string[] args)
{
int[] array={3,6,5,9,7,1,8,2,4};
for(int i=1;i<array.Length;i++)
{
for(int j=0;j<array.Length-i;j++)
{
if(array[j]>array[j+1])
{
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
foreach(int i in array)
{
Console.Write(i+" ");
}
Console.ReadKey(true);
}
}
}
二.快速排序
　　冒泡排序在扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序，如果通过两个不相邻元素的交换能够消除待排序元素中的多个逆序，则排序效率会得到明显提高，快速排序正是通过不相邻元素交换而消除多个逆序的。
　　在.NET的多个集合类所用的Sort方法，就是使用快速排序算法进行的。
　　快速排序的基本思想是：在待排序的n个元素中任取一个元素作为基准值，数据序列被此元素划分成两个部分，所有比该元素小的记录放置在前半部分，所有比它大的记录放置在后半部分，并把该元素排在这两部分中间，称为元素归位，这个过程称为一趟快速排序。然后对左右两部分分别递归上述过程，直到每部分只有一个元素为止。
using System;
namespace QuickSort
{
class Program
{
public static void Main(string[] args)
{
int[] array={3,6,5,9,7,1,8,2,4};
Quick(array,0,array.Length-1);
foreach(int i in array)
{
Console.Write(i+" ");
}
Console.ReadKey(true);
}
public static void Quick(int[] R,int low,int high)
{
if(low<high)
{
int i=low,j=high,temp=R;
while(i<j)
{
while(i<j&&R[j]>=temp)
{
j--;
}
R=R[j];
while(i<j&&R<=temp)
{
i++;
}
R[j]=R;
}
R=temp;
Quick(R,low,i-1);
Quick(R,i+1,high);
}
}
}
}