C# 排序算法

前言：

排序算法是我们编程中遇到的最多的算法。目前主流的算法有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 + " ");            }        }

结果：

后续添加更多排序方法

更多相关文章

随机推荐