简述N种排序算法
- 2020 年 3 月 15 日
- 筆記
排序算法概述
排序算法是程序员日常很常见的算法，基本上每天都会使用排序，在这里将进行一下总结。
排序算法大致可分为比较类排序和非比较类排序二种，其核心区别可以简单的理解为非比较类排序是对比较类排序之前进行了一层包装，也就是说排序的核心操作依然还是比较。
目前主流的排序算法根据分类可以分成下图所示：
简述比较类排序
冒泡排序
冒泡排序是一种老生常谈也是作为一种入门级的排序算法，其逻辑较为简单粗暴，即每次比较相邻的两个元素，如果顺序不符合就交换位置，一直不断的重复直到全部满足则停止。
算法步骤如图所示：
性能：
代码实现：
1 public class BubbleSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 ///你要想看一个人的排序算法什么的写的好不好,主要看他的OP个数 6 /// 7 //4+4+4+4+4=>20字节 8 for (var i = 0; i < data.Count; i++)//i 9 { 10 for (var j = 0; j < data.Count - 1 - i; j++)//j 11 { 12 if (data[j] > data[j + 1]) 13 { 14 var temp = data[j + 1];///空间复杂度 15 //J+1-->多了一个 16 data[j + 1] = data[j];//->j+1--> 17 data[j] = temp; 18 } 19 } 20 } 21 return data; 22 } 23 }
BubbleSort
快速排序
由刚刚的冒泡排序可以知道冒泡排序进行了太多次的重复步骤，快排就对这个事情进行了一定的改进。
快排的实现原理也十分简单，首先挑选一个基准数字，然后把比基准数字大的数字都放到一边，然后在这个分区退出后,该基准就应该在数列中间的位置,把这个操作,成为”分区”.
完事以后,再基于基准值元素进行子数列排序就好了.
算法步骤如图所示：
性能：
代码：
1 public class QuickSort 2 { 3 //排序算法---> 遍历-->判断 --->交换<-------降低 4 public static List<int> Demo(List<int> data, int left = 0, int? right = null) 5 { 6 int len = data.Count, partitionIndex; 7 right = right ?? data.Count - 1; 8 if (left < right) 9 { 10 partitionIndex = partition(data, left, right.Value); 11 Demo(data, left, partitionIndex - 1); 12 Demo(data, partitionIndex + 1, right); 13 } 14 return data; 15 } 16 //分块的 左边是啥??? 右边是啥?? 17 static int partition(List<int> data, int left, int right) 18 { 19 int pivot = left, index = pivot + 1; 20 for (var i = index; i <= right; i++) 21 { 22 if (data[i] < data[pivot]) 23 { 24 Swap(data, i, index);///交换i跟index 25 index++; 26 } 27 } 28 Swap(data, pivot, index - 1);///交换pivot与index-1 29 return index - 1; 30 } 31 32 static void Swap(List<int> data, int i, int j) 33 { 34 var temp = data[i]; 35 data[i] = data[j]; 36 data[j] = temp; 37 } 38 }
QuickSort
简单插入排序
简单插入排序也是一个十分简单的排序，比较容易相像，即拿一个元素出来，看看应该丢哪，然后丢过去即可
原理如图：
性能：
代码：
1 public class InsertSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 int preIndex, currentIndex; 6 for (var i = 1; i < data.Count; i++) 7 { 8 preIndex = i - 1; 9 currentIndex = data[i]; 10 while (preIndex >= 0 && data[preIndex] > currentIndex) 11 { 12 data[preIndex + 1] = data[preIndex]; 13 preIndex--; 14 } 15 data[preIndex + 1] = currentIndex; 16 } 17 return data; 18 } 19 }
InsertSort
希尔排序
这个相对于之前的排序会稍微复杂一点，步骤如下：
1.先把整个序列分成N个子序列.随便选一个序列xyz…增量的哦最好.
2.刚才那个序列增量序列排序一下,直接插入排序
3.循环刚才的事情.然后往前移动.一边移动一边输出.
按图来说就是第一遍循环的时候中间间隔4个，第二遍的时候间隔1个，第三遍的时候紧挨着然后将数移动到合适的位置
如图所示：
性能：
代码：
1 public class ShellSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 for (int gap =(int) Math.Floor(((decimal)(data.Count / 2))); gap > 0; gap = (int)Math.Floor(((decimal)(gap / 2)))) 6 { 7 for (var i = gap; i < data.Count; i++) 8 { 9 var j = i; 10 var current = data[i]; 11 while (j - gap >= 0 && current < data[j - gap]) 12 { 13 data[j] = data[j - gap]; 14 j = j - gap; 15 } 16 data[j] = current; 17 } 18 } 19 return data; 20 } 21 }
ShellSort
简单选择排序
这个和简单插入有点像但是略有不同。
简单选择排序过程为：
1.找一个最大/小的.
2.放到最后/前.
3.重复并慢慢缩小范围
和简单插入不同在于简单选择先找了最大最小值而简单插入为按顺序一个一个取值。
如图：
性能：
代码：
1 public class SelectSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 int minIndex, temp; 6 for (var i = 0; i < data.Count - 1; i++) 7 { 8 minIndex = i; 9 for (var j = i + 1; j < data.Count; j++) 10 { 11 if (data[j] < data[minIndex]) 12 { 13 minIndex = j; 14 } 15 } 16 temp = data[i]; 17 data[i] = data[minIndex]; 18 data[minIndex] = temp; 19 } 20 return data; 21 } 22 }
SelectSort
堆排序
这个相对而言比较复杂，实现步骤如下：
1.先随便组合成一个二叉树.
2.比较相邻二个数大小来交换相邻的二个节点的顺序，将最大的值向上推，
也就是说父节点大于下面2个各自的子节点而子节点哪个大暂时不关心。
3.将最大的根节点挪移到右下角节点并断开该节点与未排序树的连接
4.重复操作到所有节点均断开连接即排序完成。
如图所示：
性能：
代码：
1 public class HeapSort 2 { 3 static int _count; 4 5 public static List<int> Demo(List<int> data) 6 { 7 Build(data); 8 9 for (var i = data.Count - 1; i > 0; i--) 10 { 11 Swap(data, 0, i); 12 _count--; 13 Heapify(data, 0); 14 } 15 return data; 16 } 17 static void Build(List<int> data) 18 { // 建立大顶堆 19 _count = data.Count; 20 for (var i = (int)Math.Floor(((decimal)(_count / 2))); i >= 0; i--) 21 { 22 Heapify(data, i); 23 } 24 } 25 26 static void Heapify(List<int> data, int i) 27 { 28 int left = 2 * i + 1, 29 right = 2 * i + 2, 30 largest = i; 31 32 if (left < _count && data[left] > data[largest]) 33 { 34 largest = left; 35 } 36 37 if (right < _count && data[right] > data[largest]) 38 { 39 largest = right; 40 } 41 42 if (largest != i) 43 { 44 Swap(data, i, largest); 45 Heapify(data, largest); 46 } 47 } 48 49 static void Swap(List<int> data, int i, int j) 50 { 51 var temp = data[i]; 52 data[i] = data[j]; 53 data[j] = temp; 54 } 55 56 }
HeapSort
归并排序
归并排序分为二路归并和多路归并，其实本质思路是一个思路，区别只在于同时有几个并行归并操作而已。
步骤如下：
1.根据你的要求分成你喜欢的数量，形成一个个分区
2.然后每个分区各自排序
3.完事之后合并排序结果，这个步骤类似于合并二个集合，有种学校里学的集合之间合并的感觉。
如图所示：
性能：
代码：
1 public class MergeSort 2 { 3 //P=NP: 4 public static List<int> Demo(List<int> data) 5 { 6 var arr = data.ToArray(); 7 if (data.Count < 2) 8 { 9 return data; 10 } 11 int middle = (int)Math.Floor(((decimal)(data.Count / 2))); 12 var left = arr.AsSpan().Slice(0, middle).ToArray(); 13 var right = arr.AsSpan().Slice(middle).ToArray(); 14 return Merge(Demo(left.ToList()), Demo(right.ToList())); 15 } 16 17 static List<int> Merge(List<int> left, List<int> right) 18 { 19 var result = new List<int>(); 20 21 while (left.Count > 0 && right.Count > 0) 22 { 23 if (left[0] <= right[0]) 24 { 25 result.Add(left[0]); 26 left.RemoveAt(0); 27 } 28 else 29 { 30 result.Add(right[0]); 31 right.RemoveAt(0); 32 } 33 } 34 35 while (left.Count != 0) 36 { 37 result.Add(left[0]); 38 left.RemoveAt(0); 39 } 40 41 42 while (right.Count != 0) 43 { 44 45 result.Add(right[0]); 46 right.RemoveAt(0); 47 } 48 49 return result; 50 } 51 }
MergeSort
非比较类排序
计数排序
这个方案也较为简单粗暴，步骤如下：
1.选取最大最小的极值
2.遍历一遍数组，将各个数字出现的次数记录下来
3.根据大小和次数直接生成排序后集合。
如图所示：
性能：
代码：
1 public class CountingSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 var maxValue = data.Max(); 6 var bucket = new int[maxValue + 1]; 7 int sortedIndex = 0; 8 int bucketLen = maxValue + 1; 9 for (var i = 0; i < data.Count; i++) 10 { 11 if (bucket[data[i]] != 0) 12 { 13 bucket[data[i]] = 0; 14 } 15 bucket[data[i]]++; 16 } 17 18 for (var j = 0; j < bucketLen; j++) 19 { 20 while (bucket[j] > 0) 21 { 22 data[sortedIndex++] = j; 23 bucket[j]--; 24 } 25 } 26 27 return data; 28 } 29 }
CountingSort
桶排序
针对计数排序进行了改造，步骤如下：
1.预估数据平均大概需要多少个范围容器以及每个容器大概会有多少数据
2.遍历数据，根据数据所在的区间范围丢到对应的桶里
3.排序桶
4.合并数据
如图：
性能：
代码：
1 public class BucketSort 2 { 3 public static List<int> Demo(List<int> data) 4 { 5 if (data.Count == 0) 6 { 7 return data; 8 } 9 10 var minValue = data[0]; 11 var maxValue = data[0]; 12 for (var i = 1; i < data.Count; i++) 13 { 14 if (data[i] < minValue) 15 { 16 minValue = data[i]; 17 } 18 else if (data[i] > maxValue) 19 { 20 maxValue = data[i]; 21 } 22 } 23 24 var bucketSize = 3; 25 int bucketCount = (int)Math.Floor(((decimal)((maxValue - minValue) / bucketSize))) + 1; 26 var buckets = new List<int>[bucketCount]; 27 for (var i = 0; i < buckets.Length; i++) 28 { 29 buckets[i] = new List<int>(); 30 } 31 32 for (var i = 0; i < data.Count; i++) 33 { 34 buckets[(int)Math.Floor(((decimal)((data[i] - minValue) / bucketSize)))].Add(data[i]); 35 } 36 37 var res = new List<int>(); 38 for (var i = 0; i < buckets.Length; i++) 39 { 40 BubbleSort.Demo(buckets[i]); 41 for (var j = 0; j < buckets[i].Count; j++) 42 { 43 res.Add(buckets[i][j]); 44 } 45 } 46 47 return res; 48 } 49 }
BucketSort
基数排序
这个排序比较骚的地方就在于运用了数理知识，实现逻辑如下：
1.根据每个数的个位进行排序
2.然后根据十位数进行排序
用桶的思维去看就是总共一定会有10个桶，每次根据不同的规则丢到不同的桶
以2位数为例，由于第一遍的时候所有个位数的数据均排好了顺序，当排好十位数的时候，所有数字顺序就全对上了。
如图：
性能：
代码：
1 public class RadixSort 2 { 3 4 public static List<int> Demo(List<int> data) 5 { 6 var maxDigit = data.Count; 7 var mod = 10; 8 var dev = 1; 9 for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) 10 { 11 Dictionary<int, List<int>> _counter = new Dictionary<int, List<int>>(); 12 for (var j = 0; j < data.Count; j++) 13 { 14 var bucket = ((data[j] % mod) / dev); 15 if (!_counter.ContainsKey(bucket)) 16 { 17 _counter[bucket] = new List<int>(); 18 } 19 _counter[bucket].Add(data[j]); 20 } 21 var pos = 0; 22 for (var j = 0; j <= _counter.Count; j++) 23 { 24 if (_counter.ContainsKey(j)) 25 { 26 while (_counter[j].Count != 0) 27 { 28 data[pos++] = _counter[j][0]; 29 _counter[j].RemoveAt(0); 30 } 31 } 32 } 33 } 34 return data; 35 } 36 37 }
RadixSort
算法比较
算法的稳定性是什么?
简单而言：如果两个元素值一样,分别用A,B来称呼，排序后这二个元素顺序还是AB而不是BA那就是稳定的。
时间复杂度是什么?
以白话而言:排序的操作总次数,当数据的个数N变化是,操作次数是啥样子的.
空间复杂度是什么?
拿人话说:这算法在算的时候,要申请的内存大小.也就是相对于N的话的多少.所以最少也是O(1)
ps:学习参考源自ben，如有错误，轻拍。
