归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式,我还一直以为是一种需要意会的思想呢。
不好意思了,孤陋寡闻了,哈哈!
原理:将两个有序的数列,通过比较,合并为一个有序数列。 维基入口
为方便理解,此处实现用了List<int>的一些方法,随后有IList<int>版本。
实现如下:
public static List<int> MergeSortOnlyList(List<int> data, int low, int high) { if (low == high) return new List<int> { data[low] }; List<int> mergeData = new List<int>(); int mid = (low + high) / 2; List<int> leftData = MergeSortOnlyList(data, low, mid); List<int> rightData = MergeSortOnlyList(data, mid + 1, high); int i = 0, j = 0; while (true) { if (leftData[i] < rightData[j]) { mergeData.Add(leftData[i]); if (++i == leftData.Count) { mergeData.AddRange(rightData.GetRange(j, rightData.Count - j)); break; } } else { mergeData.Add(rightData[j]); if (++j == rightData.Count) { mergeData.AddRange(leftData.GetRange(i, leftData.Count - i)); break; } } } return mergeData; } public static List<int> MergeSortOnlyList(List<int> data) { data = MergeSortOnlyList(data, 0, data.Count - 1); //不会改变外部引用 参照C#参数传递 return data; }
过程解析:将数列分为两部分,分别得到两部分数列的有序版本,然后逐个比较,将比较出的小数逐个放进
新的空数列中。当一个数列放完后,将另一个数列剩余数全部放进去。
实现如下:
public static IList<int> MergeSort(IList<int> data) { data = MergeSort(data, 0, data.Count - 1); return data; } public static IList<int> MergeSort(IList<int> data, int low, int high) { int length = high - low + 1; IList<int> mergeData = NewInstance(data, length); if (low == high) { mergeData[0] = data[low]; return mergeData; } int mid = (low + high) / 2; IList<int> leftData = MergeSort(data, low, mid); IList<int> rightData = MergeSort(data, mid + 1, high); int i = 0, j = 0; while (true) { if (leftData[i] < rightData[j]) { mergeData[i + j] = leftData[i++]; //不能使用Add,Array Length不可变 if (i == leftData.Count) { int rightLeft = rightData.Count - j; for (int m = 0; m < rightLeft; m++) { mergeData[i + j] = rightData[j++]; } break; } } else { mergeData[i + j] = rightData[j++]; if (j == rightData.Count) { int leftleft = leftData.Count - i; for (int n = 0; n < leftleft; n++) { mergeData[i + j] = leftData[i++]; } break; } } } return mergeData; }
过程原理与上个一样,此处就不赘述了。
堆排序是根据堆这种数据结构设计的一种算法。堆的特性:父节点的值总是小于(或大于)它的子节点。近似二叉树。
原理:将数列构建为最大堆数列(即父节点总是最大值),将最大值(即根节点)交换到数列末尾。这样要排序的数列数总和减少,
同时根节点不再是最大值,调整最大堆数列。如此重复,最后得到有序数列。 维基入口 有趣的演示
实现准备:如何将数列构造为堆——父节点i的左子节点为2i+1,右子节点为2i+2。节点i的父节点为floor((i-1)/2)。
实现如下(这个实现判断和临时变量使用太多,导致效率低,评论中@小城故事提出了更好的实现):
public static void HeapSort(IList<int> data) { BuildMaxHeapify(data); int j = data.Count; for (int i = 0; i < j; ) { Swap(data, i, --j); if (j - 2 < 0) //只剩下1个数 j代表余下要排列的数的个数 break; int k = 0; while (true) { if (k > (j - 2) / 2) break; //即:k > ((j-1)-1)/2 超出最后一个父节点的位置 else { int temp = k; k = ReSortMaxBranch(data, k, 2 * k + 1, 2 * k + 2, j - 1); if (temp == k) break; } } } } public static void BuildMaxHeapify(IList<int> data) { for (int i = data.Count / 2 - 1; i >= 0; i--) //(data.Count-1)-1)/2为数列最大父节点索引 { int temp = i; temp = ReSortMaxBranch(data, i, 2 * i + 1, 2 * i + 2, data.Count - 1); if (temp != i) { int k = i; while (k != temp && temp <= data.Count / 2 - 1) { k = temp; temp = ReSortMaxBranch(data, temp, 2 * temp + 1, 2 * temp + 2, data.Count - 1); } } } } public static int ReSortMaxBranch(IList<int> data, int maxIndex, int left, int right, int lastIndex) { int temp; if (right > lastIndex) //父节点只有一个子节点 temp = left; else { if (data[left] > data[right]) temp = left; else temp = right; } if (data[maxIndex] < data[temp]) Swap(data, maxIndex, temp); else temp = maxIndex; return temp; }
过程解析:BuildMaxHeapify为排序前构建的最大堆数列方法,主要内容为从最后一个父节点开始往前将每个三角组合
(即父节点与它的两个子节点)符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大,
并返回该值之前的索引,用来判断是否进行了交换,以及原来的父节点值交换到了什么位置。在HeapSort里首先
构建了最大堆数列,然后将根节点交换到末尾,根节点不是最大值了,在while语句中对最大堆数列进行调整。
插曲:自从看了Martin Fowler大师《重构》第三版,我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切,
即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊!?上面的代码注释都是写博客的时候现加的(源代码很干净的。汗!)。
希尔排序是插入排序的一种更高效的改进版本。
在前面介绍的插入排序,我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。
希尔排序正是利用第一点,改善第二点,达到更理想的效果。
原理:通过奇妙的步长,插入排序间隔步长的元素,随后逐渐缩短步长至1,实现数列的插入排序。 维基入口
疑问:可以想象到排序间隔步长的数,会逐渐让数列变得有序,提升最后步长为1时标准插入排序的效率。在维基上看到这么
一句话“可能希尔排序最重要的地方在于当用较小步长排序后,以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是
这是个正确的命题吗?如何证明呢?看维基上也是由果推因,说是如果不是这样,就不会排序那么快了。可这我感觉还是太牵强了,
哪位大哥发现相关资料,希望能分享出来,不胜感激。
实现如下:
public static void ShellSortCorrect(IList<int> data) { int temp; for (int gap = data.Count / 2; gap > 0; gap /= 2) { for (int i = gap; i < data.Count; i++) // i+ = gap 改为了 i++ { temp = data[i]; for (int j = i - gap; j >= 0; j -= gap) { if (data[j] > temp) { data[j + gap] = data[j]; if (j == 0) { data[j] = temp; break; } } else { data[j + gap] = temp; break; } } } } }
基数排序是一种非比较型整数排序。
“非比较型”是什么意思呢?因为它内部使用的是桶排序,而桶排序是非比较型排序。
这里就要说说桶排序了。一个非常有意思的排序。
原理:取一定数量(数列中的最大值)的编好序号的桶,将数列每个数放进编号为它的桶里,然后将不是空的桶依次倒出来,
就组成有序数列了。 维基入口
好吧!聪明的人一眼就看出桶排序的破绽了。假设只有两个数1,10000,岂不是要一万个桶!?这确实是个问题啊!我也
没想出解决办法。我起初也以为桶排序就是一个通过牺牲空间来换取时间的排序算法,它不需要比较,所以是非比较型算法。
但看了有趣的演示的桶排序后,发现世界之大,你没有解决,不代表别人没解决,睿智的人总是很多。
1,9999的桶排序实现:new Int[2];总共有两个数,得出最大数9999的位数4,取10的4次幂即10000作为分母,
要排序的数(1或9999)作为分子,并乘以数列总数2,即1*2/10000,9999*2/10000得到各自的位置0,1,完成排序。
如果是1,10000进行排序的话,上面的做法就需要稍微加一些处理——发现最大数是10的n次幂,就将它作为分母,并
放在数列末尾就好了。
如果是9999,10000进行排序的话,那就需要二维数组了,两个都在位置1,位置0没数。这个时候就需要在放
入每个位置时采用其它排序(比如插入排序)办法对这个位置的多个数排序了。
涉及到了当重复的数出现的处理。
实现如下:
public static void BucketSortOnlyUnitDigit(IList<int> data) { int[] indexCounter = new int[10]; for (int i = 0; i < data.Count; i++) { indexCounter[data[i]]++; } int[] indexBegin = new int[10]; for (int i = 1; i < 10; i++) { indexBegin[i] = indexBegin[i-1]+ indexCounter[i-1]; } IList<int> tempList = NewInstance(data, data.Count); for (int i = 0; i < data.Count; i++) { int number = data[i]; tempList[indexBegin[number]++] = data[i]; } data = tempList; }
过程解析:indexCounter进行对每个数出现的频率的统计。indexBegin存储每个数的起始索引。
比如 1 1 2,indexCounter统计到0个0,2个1,1个2。indexBegin计算出0,1,2的起始索引分别为
0,0,2。当1个1已取出排序,那索引将+1,变为0,1,2。这样就通过提前给重复的数空出位置,解决了
重复的数出现的问题。当然,你也可以考虑用二维数组来解决重复。
下面继续基数排序。
基数排序原理:将整数按位数切割成不同的数字,然后按每个位数分别比较。
取得最大数的位数,从低位开始,每个位上进行桶排序。
实现如下:
public static IList<int> RadixSort(IList<int> data) { int max = data[0]; for (int i = 1; i < data.Count; i++) { if (data[i] > max) max = data[i]; } int digit = 1; while (max / 10 != 0) { digit++; max /= 10; } for (int i = 0; i < digit; i++) { int[] indexCounter = new int[10]; IList<int> tempList = NewInstance(data, data.Count); for (int j = 0; j < data.Count; j++) { int number = (data[j] % Convert.ToInt32(Math.Pow(10, i + 1))) / Convert.ToInt32(Math.Pow(10, i)); //得出i+1位上的数 indexCounter[number]++; } int[] indexBegin = new int[10]; for (int k = 1; k < 10; k++) { indexBegin[k] = indexBegin[k - 1] + indexCounter[k - 1]; } for (int k = 0; k < data.Count; k++) { int number = (data[k] % Convert.ToInt32(Math.Pow(10, i + 1))) / Convert.ToInt32(Math.Pow(10, i)); tempList[indexBegin[number]++] = data[k]; } data = tempList; } return data; }
过程解析:得出最大数的位数,从低位开始桶排序。我写的这个实现代码并不简洁,但逻辑更清晰。
后面测试的时候我们就会发现,按理来说这个实现也还行吧! 但并不如想象的那么快!
循环的次数太多?(统计频率n次+9次计算+n次放到新的数组)*位数。
创建的新实例太多?(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数
添加随机数组,数组有序校验,微软Linq排序
代码如下:
public static int[] RandomSet(int length, int max) { int[] result = new int[length]; Random rand = new Random(); for (int i = 0; i < result.Length; i++) { result[i] = rand.Next(max); } return result; } public static bool IsAscOrdered(IList<int> data) { bool flag = true; for (int i = 0; i < data.Count - 1; i++) { if (data[i] > data[i + 1]) flag = false; } return flag; } public static void TestMicrosoft(IList<int> data) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); List<int> result = data.OrderBy(a => a).ToList(); stopwatch.Stop(); string methodName = "TestMicrosoft"; int length = methodName.Length; for (int i = 0; i < 40 - length; i++) { methodName += " "; } Console.WriteLine(methodName + " IsAscOrdered:" + IsAscOrdered(result) + " Time:" + stopwatch.Elapsed.TotalSeconds); }
测试主体如下:
static void Main(string[] args) { int[] aa = RandomSet(50000, 99999); //int[] aa = OrderedSet(5000); Console.WriteLine("Array Length:" + aa.Length); RunTheMethod((Action<IList<int>>)SelectSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)BubbleSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)BubbleSortImprovedWithFlag, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)BubbleCocktailSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)InsertSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)InsertSortImprovedWithBinarySearch, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)QuickSortStrict, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)QuickSortRelax, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)QuickSortRelaxImproved, aa.Clone() as int[]); RunTheMethod((Func<IList<int>, IList<int>>)MergeSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)ShellSort, aa.Clone() as int[]); RunTheMethod((Func<IList<int>, IList<int>>)RadixSort, aa.Clone() as int[]); RunTheMethod((Action<IList<int>>)HeapSort, aa.Clone() as int[]); TestMicrosoft(aa.Clone() as int[]); Console.Read(); } public static void RunTheMethod(Func<IList<int>, IList<int>> method, IList<int> data) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); IList<int> result = method(data); stopwatch.Stop(); string methodName = method.Method.Name; int length = methodName.Length; for (int i = 0; i < 40 - length; i++) { methodName += " "; } Console.WriteLine(methodName + " IsAscOrdered:" + IsAscOrdered(result) + " Time:" + stopwatch.Elapsed.TotalSeconds); } public static void RunTheMethod(Action<IList<int>> method, IList<int> data) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); method(data); stopwatch.Stop(); string methodName = method.Method.Name; int length = methodName.Length; for (int i = 0; i < 40 - length; i++) { methodName += " "; } Console.WriteLine(methodName + " IsAscOrdered:" + IsAscOrdered(data) + " Time:" + stopwatch.Elapsed.TotalSeconds); }
剩余代码折叠在此处
public static void Swap(IList<int> data, int a, int b) { int temp = data[a]; data[a] = data[b]; data[b] = temp; } public static int[] OrderedSet(int length) { int[] result = new int[length]; for (int i = 0; i < length; i++) { result[i] = i; } return result; } public static IList<int> NewInstance(IList<int> data, int length) { IList<int> instance; if (data is Array) { instance = new int[length]; } else { instance = new List<int>(length); for (int n = 0; n < length; n++) { instance.Add(0); // 初始添加 } } return instance; }
联系客服