几种常见排序算法的C#实现
发表于2018-07-05
网上关于几种排序算法的C#实现原理说的很清楚，但是在示例代码有些不友好，所以这里就给大家准备了几种常见的排序算法实例，供大家参考。
本文没有动图展示，没有逐步剖析，也没有算法比较（网上可以搜到很多）。
本文默认数组排序目标是从小到大排列，示例的目标数组是[1, 6, 4, 8, 2, 5, 0]。
一、冒泡排序
简单说明：从数组的首端（尾端）开始，将相邻两数进行比较，将最大（最小）的数放置到尾端（首端），如此循环，并在下次循环时剔除上次尾端（首端）已放置好的数，直至排出正确序列。
1.1 从首端开始的.冒泡排序
int temp;
for (int i = 0; i < list.Length - 1; i++)
｛
for (int j = 1; j < list.Length - i - 1; j++)
｛
if (list[j - 1] > list[j])
｛
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
｝
｝
｝
1.2 从尾端开始的冒泡排序
int temp;
for (int i = list.Length - 1; i > 0; i--)
｛
for (int j = list.Length - 1; j > list.Length - 1 - i; j--)
｛
if (list[j - 1] > list[j])
｛
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
｝
｝
｝
2.选择排序
简单说明：从首端开始，利用中间变量找出最小的数将此数与首端数进行交换，下次循环找出最小数与第二个数进行交换，如此循环，直至正确排序。
int min, temp;
for (int i = 0; i < list.Length - 1; i++)
｛
min = i;
for (int j = i + 1; j < list.Length - 1; j++)
｛
if (list[min] > list[j])
｛
min = j;
｝
｝
temp = list[i];
list[i] = list[min];
list[min] = temp;
｝
3.插入排序
简单说明：从第二个数开始往右循环，每次循环中将当前数分别与其左边的数进行比较，如发现比当前数大的数则进行交换，如此循环，直至正确排序。
int temp;
for (int i = 1; i < list.Length; i++)
｛
int j = i - 1;
temp = list[i];
//因为当前数的左边都已是排序好的数列，因此无需当前数与左边数列每个都进行比较，只要某个数比当前数小，则剩下未比较的数也一定比当前数小
while (j >= 0 && temp < list[j])
｛
list[j + 1] = list[j];
j--;
｝
list[j + 1] = temp;
｝
4.快速排序
简单说明：选择数组中的一个数作为基准数（一般是第一个数），并设两个变量low，high用于记录索引值，然后从尾端开始向前逐个比较基准数，直至某个数比基准数小，则将该数索引存入high，将该数放置于low索引上，然后从首端开始向后逐个比较基准数，直至某个数比基准数大，则将该数索引存入low，将该数放置于high索引上，如此循环，直至low=high，将此时的low索引存入中间变量，将基准数存入该索引上，此时原数组被分为了两边，左边小，右边大，然后分组进行上述操作，如此循环，直至正确排序。
4.1 快速排序的非递归实现
Stack<int> s = new Stack<int>();
s.Push(0);
s.Push(list.Length - 1);
while (s.Count > 1)
｛
int high = s.Pop();
int low = s.Pop();
int H = high;
int L = low;
int temp = list[low];
while (low < high)
｛
while (low < high && temp <= list[high])
｛
high--;
｝
if (low < high)
｛
list[low] = list[high];
//list[high] = temp;
｝
while (low < high && temp >= list[low])
｛
low++;
｝
if (low < high)
｛
list[high] = list[low];
//list[low] = temp;
｝
｝
list[low] = temp;
if (low == high)
｛
if (L < low - 1)
｛
s.Push(L);
s.Push(low - 1);
｝
if (H > low + 1)
｛
s.Push(low + 1);
s.Push(H);
｝
｝
｝
4.2快速排序的递归实现
QuickSort(list,0,list.Length - 1);
private static void QuickSort(int[] list,int low,int high)
｛
int mid;
if (low < high)
｛
mid = Partition(list, low, high);
QuickSort(list,low,mid - 1);
QuickSort(list,mid + 1,high);
｝
｝
private static int Partition(int[] list,int low,int high)
｛
int temp = list[low];
while (low < high)
｛
while (low<high && temp < list[high])
｛
high--;
｝
list[low] = list[high];
while (low < high && temp > list[low])
｛
low++;
｝
list[high] = list[low];
｝
list[low] = temp;
return low;
｝