前言：
排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。
平均时间复杂度从高到低依次是：
冒泡排序（o(n2)），选择排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)），
归并排序（o(nlogn)），快速排序（o(nlogn)）， 希尔排序（o(n1.25)），基数排序（o(n)）
申明：以下排序全部针对数组{ 25, 1, 5, 2, 9, 11, 2, 4 }; 所有测试使用备注，只是为了让用户根据结果看得更加明白，理解之后可删除。
一、冒泡排序：
思想：从数组第一位开始，每个元素和它下一位比较，将大的换到后面，即每一轮循环之后可以确定一个位置。提高效率（可定义一个标记，如果一轮循环之后没有发生交换直接结束）
代码：
static void maopao()
{int[] a = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; bool sign = false;for (int i = 0; i < a.Length - 1; i++)
{for (int j = 0; j < a.Length - i - 1; j++)
{if (a[j] > a[j+1])
{
outPuts(a, "交换之前");//测试使用Console.Write(String.Format(" {0:D2}<-交换->{1:D2} ", a[j], a[j + 1]));//测试使用int b = a[j];
a[j] = a[j + 1];
a[j + 1] = b;
sign = true;
outPuts(a, "交换之后");//测试使用Console.WriteLine();//测试使用 }
}if (!sign) break;
}
Console.WriteLine();//测试使用outPuts(a, "最后数据");
Console.ReadKey();
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
结果：
二、选择排序：
对冒泡排序进行优化，由上结果可以看到25连续交换多次，那么如何实现一次循环只交换一次就可以确定一个位置呢？
思想：对于第一趟，搜索整个数组，寻找出最小（或最大此处以最小为例即从小到大排序）的，然后放置在数组的0号位置；对于第二趟，搜索数组的n-1个记录，寻找出最小的（对于整个数组来说则是次小的），然后放置到数组的第1号位置。在第i趟时，搜索数组的n-i+1个记录，寻找最小的记录（对于整个数组来说则是第i小的），然后放在数组i-1的位置（注意数组以0起始）。
代码：
private static void xuanze()
{int[] a = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 };for (int i = 0; i < a.Length - 1; i++)
{int sign = i;for (int j = i + 1; j < a.Length; j++)
{if (a[sign] > a[j])
{
sign = j;
}
}if (sign != i)
{
outPuts(a, "交换之前");//测试使用Console.Write(String.Format(" {0:D2}<-交换->{1:D2} ", a[i], a[sign]));//测试使用int b = a[i];
a[i] = a[sign];
a[sign] = b;
outPuts(a, "交换之后");//测试使用Console.WriteLine();//测试使用 }
}
Console.WriteLine();//测试使用outPuts(a, "最后数据");
Console.ReadKey();
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
结果：
三、插入排序：
插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。
思想：数组下标1开始，和前面下标为0的数据作比较，如果下标0的数据大于（或小于即从大到小排序）下标1的数据则后移，下标1的数据插入到0的位置，否则插入当前位置。数组下标m开始，和所以前面数据作比较，即下标为n(m-1>=n>=0)的数据作比较，如果下标n的数据大于（或小于即从大到小排序）下标m的数据则后移,直到n=-1,将下标为m得到数据插入到下标为0的位置，否则插入当前位置，
代码：
private static void charu()
{int[] data = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 };for (int i = 1; i < data.Length; i++)
{int d = data[i];bool result = true;//标记，表示已经比较到第一个位置for (int j = i - 1; j >= 0; j--)
{if (data[j] > d)
{
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" 从下标{0}开始 {1}<-移动->{2} ",i, j, j+1));//测试使用data[j + 1] = data[j];
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用 }else{
outPuts(data, "插入之前");//测试使用Console.Write(String.Format(" 从下标{0}开始 数据{1}<-插入到->{2} ", i, d, j + 1));//测试使用data[j + 1] = d;
result = false;
outPuts(data, "插入之后");//测试使用Console.WriteLine();//测试使用break;
}
}if (result)
{
outPuts(data, "插入之前");//测试使用Console.Write(String.Format(" 数据{0}<-插入到->{1} ", d, 0));//测试使用data[0] = d;
outPuts(data, "插入之后");//测试使用Console.WriteLine();//测试使用 }
}
Console.WriteLine();//测试使用outPuts(data, "最后数据");
Console.ReadKey();
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
//方法二private static void charu2(int[] data)
{int j;for (int i = 1; i < data.Length; i++)
{int d = data[i];for (j = i - 1; j >= 0 && data[j] > d; j--)
{
data[j + 1] = data[j];
}
data[j + 1] = d;
}
}
结果：
四、快速排序：
快速排序是一种高效排序。它包含了“分而治之”以及“哨兵”的思想。
思想：从数组中挑选一个数（一般为第一个数据）作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。
说明：25为哨兵，定义变量保存，0位置为待处理位置，从right向前找直到找到比哨兵小的，将其放入到待处理位置，left++，并设置当前为待处理位置，从left开始向后找比哨兵大的放入待处理位置，right--，并设置当前为待处理位置。直到left>right结束，此时第一个哨兵位置确定。并以哨兵为点，将数组分为两段分别继续递归实现该方法。
代码：
private static void kuaisu(int[] data, int left, int right)
{if (left >= right) return;int x = data[left];int i = left;int j = right;try{while (i < j)
{while (i < j && data[j] >= x)
{
j--;
}if (i == j) break;
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" {0}<-移动到->{1} ", j, i));//测试使用data[i++] = data[j];
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用while (i < j && data[i] <= x)
{
i++;
}if (i == j) break;
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" {0}<-移动到->{1} ", i, j));//测试使用data[j--] = data[i];
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用 }
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" 数据{0}<-移动到->{1} 数据区间{2}--{3} ", x, i,left,right));//测试使用data[i] = x;
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用kuaisu(data, left, i - 1);
kuaisu(data, i + 1, right);
}catch (Exception e)
{
Console.WriteLine(e);
}
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
结果：
五、归并排序：
使用递归方法。
思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
那么如何确定一个子序列有序呢？当然子序列个数为1时自然有序。所以将数组分为两段，一直分段递归下去，直到数组长度为1返回，此时将其归并直到结束。
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
代码：
int[] data = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 };
guibing(data, 0, data.Length - 1);
outPuts(data, "最后数据");
Console.ReadKey();
private static void guibing(int[] data, int left, int right)
{if (left < right)
{int mid = (left + right) / 2;
guibing(data, left, mid);
guibing(data, mid + 1, right);
arrayAdd(data, left, mid, right);
}
}private static void arrayAdd(int[] data, int left, int mid, int right)
{int[] d = new int[right - left + 1];int i = left;int j = mid + 1;int k = 0;while (i <= mid && j <= right)
{if (data[j] < data[i]) d[k++] = data[j++];else d[k++] = data[i++];
}while (i <= mid)
{
d[k++] = data[i++];
}while (j <= right)
{
d[k++] = data[j++];
}
i = left;for (k = 0; k < d.Length; k++)
{
outPuts(data, "赋值之前");//测试使用Console.Write(" ");//测试使用data[i++] = d[k];
outPuts(data, "赋值之后");//测试使用Console.Write(String.Format(" 赋值下标位置范围{0}--{1} 临时数组：",left,right));//测试使用foreach (int f in d) //测试使用 {
Console.Write(f + " ");
}
Console.WriteLine();//测试使用 }
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
结果：
六、希尔排序：
希尔排序是插入排序的一种更高效的改进版本。
思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数列恰被分成一组，算法便终止。
增量算法有：https://blog.csdn.net/foliciatarier/article/details/53891144
本文以：Hibbard 增量序列为例
代码：
int[] data = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 };
xier(data);
private static void xier(int[] data)
{
List<int> garArry = new List<int>();int m = 0;while (Math.Pow(2,m) - 1 <= data.Length / 2)
{
m++;
garArry.Add((int)Math.Pow(2, m) - 1);
}for (int y = garArry.Count - 1; y >= 0; y--)
{int gap = garArry[y];int j;//比较次数for (int i = gap; i < data.Length; i++)
{int d = data[i];for (j = i - gap; j >= 0 && data[j] > d; j -= gap)
{
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" {0}<-移动到->{1} 步长{2} ", j, j + gap, gap));//测试使用data[j + gap] = data[j];
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用 }
outPuts(data, "移动之前");//测试使用Console.Write(String.Format(" 数据{0}<-移动到->{1} 步长{2} ", d, j + gap, gap));//测试使用data[j + gap] = d;
outPuts(data, "移动之后");//测试使用Console.WriteLine();//测试使用 }
}
outPuts(data, "最后数据");
}private static void outPuts(int[] a, string str)
{
Console.Write(str + ":");foreach (var item in a)
{
Console.Write(item + " ");
}
}
结果：
后续添加更多排序方法