C#、.NET常用排序算法

分类:.NET
 标签:冒泡排序,插入排序,选择排序,归并排序,快速排序
   修改 | 阅读(852)| 评论(0)

冒泡排序

冒泡排序也被称为下沉排序,是一个简单的排序算法,通过多次重复比较每对相邻的元素,并按规定的顺序交换他们,最终把数列进行排好序。一直重复下去,直到结束。该算法得名于较小元素“气泡”会“浮到”列表顶部。由于只使用了比较操作,所以这是一个比较排序。

冒泡排序算法的运作如下:

1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

3、针对所有的元素重复以上的步骤,除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

static void BubbleSort(int[] arrayToSort)
{
	int n = arrayToSort.Length - 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = n; j > i; j--)
		{
			if ((arrayToSort[j - 1]) > arrayToSort[j])
			{
				int temp = arrayToSort[j - 1];
				arrayToSort[j - 1] = arrayToSort[j];
				arrayToSort[j] = temp;
			}
		}
	}
}


插入排序

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。


具体算法描述如下:


1、从第一个元素开始,该元素可以认为已经被排序

2、取出下一个元素,在已经排序的元素序列中从后向前扫描

3、如果该元素(已排序)大于新元素,将该元素移到下一位置

4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

5、将新元素插入到该位置后

6、重复步骤2~5

static void InsertionSort(int[] arrayToSort)
{
	for (int i = 1; i < arrayToSort.Length; i++)
	{
		int val = arrayToSort[i];
		int j = i - 1;
		bool done = false;
		do
		{
			if (arrayToSort[j] > val)
			{
				arrayToSort[j + 1] = arrayToSort[j];
				j--;
				if (j < 0)
				{
					done = true;
				}
			}
			else
			{
				done = true;
			}
		} while (!done);
		arrayToSort[j + 1] = val;
	}
}


选择排序

原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法过程如下:

1、找到列表中的最小值,

2、把它和第一个位置的元素交换,

3、列表其余部分重复上面的步骤(从第二个位置开始,且每次加1).

static void SelectionSort(int[] arrayToSort)
{
	int min;
	for (int i = 0; i < arrayToSort.Length; i++)
	{
		min = i;
		for (int j = i + 1; j < arrayToSort.Length; j++)
		{
			if (arrayToSort[j]<arrayToSort[min])
			{
				min = j;
			}
		}
		int temp = arrayToSort[i];
		arrayToSort[i] = arrayToSort[min];
		arrayToSort[min] = temp;
	}
}


归并排序

从概念上讲,归并排序的工作原理如下:

1、如果列表的长度是0或1,那么它已经有序。否则:

2、未排序的部分平均划分为两个子序列。

3、每个子序列,递归使用归并排序。

4、合并两个子列表,使之整体有序。


归并排序包含两个主要观点,以改善其运行时:

1、一个小列表排序的花费少于大列表。

2、把两个有序表合并,要比直接排列一个无序表花费更少的步骤。例如,您只需要遍历每个有序列表一次即可(见下面的合并功能)。


归并操作的过程如下:

1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

4、重复步骤3直到某一指针到达序列尾

5、将另一序列剩下的所有元素直接复制到合并序列尾

static void MergeSort(int[] a, int low, int height)
{
	int l = low;
	int h = height;
	if (l >= h)
	{
		return;
	}
	int mid = (l + h) / 2;
	MergeSort(a, l, mid);
	MergeSort(a, mid + 1, h);
	int end_lo = mid;
	int start_hi = mid + 1;
	while ((l <= end_lo) && (start_hi <= h))
	{
		if (a[l] < a[start_hi])
		{
			l++;
		}
		else
		{
			int temp = a[start_hi];
			for (int k = start_hi - 1; k >= l; k--)
			{
				a[k + 1] = a[k];
			}
			a[l] = temp;
			l++;
			end_lo++;
			start_hi++;
		}
	}
}


快速排序

快速排序采用分而治之的策略,把一个列表划分为两个子列表。步骤是:

1、从列表中,选择一个元素,称为基准(pivot)。

2、重新排序列表,把所有数值小于枢轴的元素排到基准之前,所有数值大于基准的排基准之后(相等的值可以有较多的选择)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3、分别递归排序较大元素的子列表和较小的元素的子列表。

递归的结束条件是列表元素为零或一个,即已不需要排序。

static void QuickSort(int[] a, int left, int right)
{
	int i = left;
	int j = right;
	double pivotValue = ((left + right) / 2);
	int x = (int)a[int.Parse(pivotValue.ToString())];
	while (i <= j)
	{
		while (a[i] < x)
		{
			i++;
		}
		while (x < a[j])
		{
			j--;
		}
		if (i <= j)
		{
			int temp = a[i];
			a[i] = a[j];
			i++;
			a[j] = temp;
			j--;
		}
	}
	if (left < j)
	{
		QuickSort(a, left, j);
	}
	if (i < right)
	{
		QuickSort(a, i, right);
	}
}


您的昵称:*
QQ登录(无需注册直接登录可进行回复)
您的邮箱:(填写邮箱,如有回复可进行邮件通知)
验证码:
点击刷新