单位网站建设和维护,免费设计室内装修软件,wordpress首页排序,wordpress系统通知邮箱#x1f353;个人主页#xff1a;bit.. #x1f352;系列专栏#xff1a;Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法 HTML和CSS3 目录 1.6 快速排序
1. 算法步骤
2. 动图演示
3.代码实现 1.7 堆排序
1. 算法步骤
2. 动图演示
3. 代码实现
1.8 计数排… 个人主页bit.. 系列专栏Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法 HTML和CSS3 目录 1.6 快速排序
1. 算法步骤
2. 动图演示
3.代码实现 1.7 堆排序
1. 算法步骤
2. 动图演示
3. 代码实现
1.8 计数排序
1. 计数排序的特征
2. 动图演示
3.代码实现 1.9 桶排序
1. 什么时候最快
2. 什么时候最慢
3. 示意图
3.代码实现 1.10 基数排序
1. 基数排序 vs 计数排序 vs 桶排序
2. LSD 基数排序动图演示
3.代码实现 1.6 快速排序
快速排序一种排序很快的方法使用分治思想就是说快速排序是通过把数据分成几部分来处理的一种算法。快排本身和其使用的分治思想都很重要也是面试可能出现的一大难点。
1. 算法步骤 从数列中挑出一个元素称为 基准pivot; 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序
2. 动图演示 3.代码实现
public class QuickSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);return quickSort(arr, 0, arr.length - 1);}private int[] quickSort(int[] arr, int left, int right) {if (left right) {int partitionIndex partition(arr, left, right);quickSort(arr, left, partitionIndex - 1);quickSort(arr, partitionIndex 1, right);}return arr;}private int partition(int[] arr, int left, int right) {// 设定基准值pivotint pivot left;int index pivot 1;for (int i index; i right; i) {if (arr[i] arr[pivot]) {swap(arr, i, index);index;}}swap(arr, pivot, index - 1);return index - 1;}private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}} 1.7 堆排序
堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法
大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列
1. 算法步骤 创建一个堆 H[0……n-1] 把堆首最大值和堆尾互换 把堆的尺寸缩小 1并调用 shift_down(0)目的是把新的数组顶端数据调整到相应位置 重复步骤 2直到堆的尺寸为 1。
2. 动图演示 3. 代码实现
public class HeapSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);int len arr.length;buildMaxHeap(arr, len);for (int i len - 1; i 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0, len);}return arr;}private void buildMaxHeap(int[] arr, int len) {for (int i (int) Math.floor(len / 2); i 0; i--) {heapify(arr, i, len);}}private void heapify(int[] arr, int i, int len) {int left 2 * i 1;int right 2 * i 2;int largest i;if (left len arr[left] arr[largest]) {largest left;}if (right len arr[right] arr[largest]) {largest right;}if (largest ! i) {swap(arr, i, largest);heapify(arr, largest, len);}}private void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}}
1.8 计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。
1. 计数排序的特征
当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 Θ(n k)。计数排序不是比较排序排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1这使得计数排序对于数据范围很大的数组需要大量时间和内存。例如计数排序是用来排序0到100之间的数字的最好的算法但是它不适合按字母顺序排序人名。但是计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
通俗地理解例如有 10 个年龄不同的人统计出有 8 个人的年龄比 A 小那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然年龄有重复时需要特殊处理保证稳定性这就是为什么最后要反向填充目标数组以及将每个数字的统计减去 1 的原因。 算法的步骤如下
1找出待排序的数组中最大和最小的元素2统计数组中每个值为i的元素出现的次数存入数组C的第i项3对所有的计数累加从C中的第一个元素开始每一项和前一项相加4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
2. 动图演示 3.代码实现
public class CountingSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);int maxValue getMaxValue(arr);return countingSort(arr, maxValue);}private int[] countingSort(int[] arr, int maxValue) {int bucketLen maxValue 1;int[] bucket new int[bucketLen];for (int value : arr) {bucket[value];}int sortedIndex 0;for (int j 0; j bucketLen; j) {while (bucket[j] 0) {arr[sortedIndex] j;bucket[j]--;}}return arr;}private int getMaxValue(int[] arr) {int maxValue arr[0];for (int value : arr) {if (maxValue value) {maxValue value;}}return maxValue;}} 1.9 桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效我们需要做到这两点
在额外空间充足的情况下尽量增大桶的数量使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时对于桶中元素的排序选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
3. 示意图
元素分布在桶中 然后元素在每个桶中排序 3.代码实现
public class BucketSort implements IArraySort {private static final InsertSort insertSort new InsertSort();Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);return bucketSort(arr, 5);}private int[] bucketSort(int[] arr, int bucketSize) throws Exception {if (arr.length 0) {return arr;}int minValue arr[0];int maxValue arr[0];for (int value : arr) {if (value minValue) {minValue value;} else if (value maxValue) {maxValue value;}}int bucketCount (int) Math.floor((maxValue - minValue) / bucketSize) 1;int[][] buckets new int[bucketCount][0];// 利用映射函数将数据分配到各个桶中for (int i 0; i arr.length; i) {int index (int) Math.floor((arr[i] - minValue) / bucketSize);buckets[index] arrAppend(buckets[index], arr[i]);}int arrIndex 0;for (int[] bucket : buckets) {if (bucket.length 0) {continue;}// 对每个桶进行排序这里使用了插入排序bucket insertSort.sort(bucket);for (int value : bucket) {arr[arrIndex] value;}}return arr;}/*** 自动扩容并保存数据** param arr* param value*/private int[] arrAppend(int[] arr, int value) {arr Arrays.copyOf(arr, arr.length 1);arr[arr.length - 1] value;return arr;}} 1.10 基数排序
基数排序是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。
1. 基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法
这三种排序算法都利用了桶的概念但对桶的使用方法上有明显差异
基数排序根据键值的每位数字来分配桶计数排序每个桶只存储单一键值桶排序每个桶存储一定范围的数值
2. LSD 基数排序动图演示 3.代码实现
/*** 基数排序* 考虑负数的情况还可以参考 https://code.i-harness.com/zh-CN/q/e98fa9*/
public class RadixSort implements IArraySort {Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝不改变参数内容int[] arr Arrays.copyOf(sourceArray, sourceArray.length);int maxDigit getMaxDigit(arr);return radixSort(arr, maxDigit);}/*** 获取最高位数*/private int getMaxDigit(int[] arr) {int maxValue getMaxValue(arr);return getNumLenght(maxValue);}private int getMaxValue(int[] arr) {int maxValue arr[0];for (int value : arr) {if (maxValue value) {maxValue value;}}return maxValue;}protected int getNumLenght(long num) {if (num 0) {return 1;}int lenght 0;for (long temp num; temp ! 0; temp / 10) {lenght;}return lenght;}private int[] radixSort(int[] arr, int maxDigit) {int mod 10;int dev 1;for (int i 0; i maxDigit; i, dev * 10, mod * 10) {// 考虑负数的情况这里扩展一倍队列数其中 [0-9]对应负数[10-19]对应正数 (bucket 10)int[][] counter new int[mod * 2][0];for (int j 0; j arr.length; j) {int bucket ((arr[j] % mod) / dev) mod;counter[bucket] arrayAppend(counter[bucket], arr[j]);}int pos 0;for (int[] bucket : counter) {for (int value : bucket) {arr[pos] value;}}}return arr;}/*** 自动扩容并保存数据** param arr* param value*/private int[] arrayAppend(int[] arr, int value) {arr Arrays.copyOf(arr, arr.length 1);arr[arr.length - 1] value;return arr;}
}
