知名的网页制作公司欢迎咨询,网站建设优化培训班,专门做艺术字的网站,wordpress页面跳舞一、冒泡排序 冒泡排序#xff08;Bubble Sort#xff09;是一种简单直观的排序算法。它重复地走访要排序的数列#xff0c;一次比 较两个元素#xff0c;如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换#xff0c;也就是说该数列已经…一、冒泡排序 冒泡排序Bubble Sort是一种简单直观的排序算法。它重复地走访要排序的数列一次比 较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经交换慢慢浮到数列的头部。
/*** 冒泡排序*/
public class BubbleSort {public void sort(int[] arr) {if (arr null || arr.length 0) {return;}for (int i 1; i arr.length; i) { //比较的轮数for (int j 0; j arr.length - i; j) { // 每轮比较的次数if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}}
}二、选择排序 选择排序也是一种简单直观的排序算法无论什么数据进去都是 O(n²) 的时间复杂度。所以 用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
public class SelectionSort {public void sort(int[] arr) {if (arr null || arr.length 0) {return;}for (int i 0; i arr.length - 1; i) { //比较的轮数int min i;// 记录最小值的索引for (int j i 1; j arr.length; j) {if (arr[min] arr[j]) {min j;}}// 将最小值放置在索引为i的位置if (min ! i) {int temp arr[i];arr[i] arr[min];arr[min] temp;}}}
}
三、插入排序 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴但它的原理应该是最容易理 解的了因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
public class InsertSort {public void sort(int[] arr) {if (arr null || arr.length 0) {return;}for (int i 1; i arr.length; i) {int instartVal arr[i];int j i - 1; // 有序区最后一个元素while (j 0) {if (arr[j] instartVal) {arr[j 1] arr[j];j--;} else {break;}}arr[j 1] instartVal;}}
}
四、希尔排序 希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的 • 插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率 • 但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排 序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。 public class ShellSort {public void sort(int[] arr) {if (arr null || arr.length 0) {return;}int length arr.length;// step:表示希尔增量for (int step length / 2; step 1; step / 2) {//从setp位置开始进行插入排序直至完毕for (int i step; i arr.length; i) {int instartVal arr[i];int j i - step; // 有序区最后一个元素while (j 0) {if (arr[j] instartVal) {arr[j step] arr[j];j - step;} else {break;}}arr[j step] instartVal;}}}
} 五、 归并排序 归并排序Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 Divide and Conquer的一个非常典型的应用。 1. 算法步骤 1. 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 2. 设定两个指针最初位置分别为两个已经排序序列的起始位置 3. 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 4. 重复步骤 3 直到某一指针达到序列尾 5. 将另一序列剩下的所有元素直接复制到合并序列尾。
import java.util.Arrays;/*** 归并排序*/
public class MergeSort {public int[] sort(int[] arr) {if (arr null || arr.length 2) {return arr;}int middle (int) Math.floor(arr.length / 2);int[] left Arrays.copyOfRange(arr, 0, middle );int[] right Arrays.copyOfRange(arr, middle , arr.length);return merge(sort(left), sort(right));}protected int[] merge(int[] left, int[] right) {int[] result new int[left.length right.length];int i 0;int m 0;int n 0;while (m left.length n right.length) {if (left[m] right[n]) {result[i] left[m];} else {result[i] right[n];}}while (m left.length) {result[i] left[m];}while (n right.length) {result[i] right[n];}return result;}
}
六、 快速排序
1. 算法步骤 1. 从数列中挑出一个元素称为 基准pivot; 2. 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 3. 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序 /*** 快速排序*/
public class FastSort {public void sort(int[] arr) {if (arr null || arr.length 2) {return;}// 排序fastSort(arr, 0, arr.length - 1);}// 对[left,right]区间进行排序private void fastSort(int[] arr, int left, int right) {// 递归到底的情况if (left right) {return;}// 递归操作int pivot arr[left];int i left;int j right;while (i j) {// 从右边开始找到第一个小于pivot的元素while (i j arr[j] pivot) {j--;}// 替换if (i j) {arr[i] arr[j];i;}// 从左边开始找到第一个比pivot大的元素while (i j arr[i] pivot) {i;}// 替换if (i j) {arr[j] arr[i];j--;}}arr[i] pivot;fastSort(arr, left, i - 1);fastSort(arr, i 1, right);}
}七、 堆排序 堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法 大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列 小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列 堆排序的平均时间复杂度为 Ο(nlogn)。 1. 算法步骤 1. 创建一个堆 H[0……n-1] 2. 把堆首最大值和堆尾互换 3. 调用 shift_down方法使除过堆尾元素的树满足最大堆的性质 4. 重复步骤 2直到堆中只有一个元素。 // 堆排序
public class HeapSort {private int getParentIndex(int index) {if (index 0) {throw new IllegalArgumentException(index is invalid!);}if (index 0) { // 处理根节点return -1;}return (index - 1) / 2;}// 根据当前结点所在数组的索引获取左孩子结点的索引private int getLeftChildIndex(int index) {return 2 * index 1;}public void sort(int[] arr) {if (arr null || arr.length 0) {return;}// 将完全二叉树整理成堆heapify(arr);// 排序for (int i arr.length - 1; i 0; i--) {// 将堆尾元素与堆首元素互换int temp arr[0];arr[0] arr[i];arr[i] temp;// 整理成堆siftDown(0, arr, i);}}private void heapify(int[] arr) {// 1、找到最后一个元素的父节点int parentIndex getParentIndex(arr.length - 1);// 2、从最后一个元素的父节点开始下沉操作直到根节点for (; parentIndex 0; parentIndex--) {siftDown(parentIndex, arr, arr.length);}}private void siftDown(int curIndex, int[] arr, int length) {int leftChildIndex getLeftChildIndex(curIndex);int chageIndex leftChildIndex;while (leftChildIndex length) {int rigthChildIndex leftChildIndex 1;if (rigthChildIndex length arr[rigthChildIndex] arr[leftChildIndex]) {chageIndex rigthChildIndex;}if (arr[chageIndex] arr[curIndex]) {// 交换操作int temp arr[curIndex];arr[curIndex] arr[chageIndex];arr[chageIndex] temp;curIndex chageIndex;leftChildIndex getLeftChildIndex(curIndex);chageIndex leftChildIndex;} else {break;}}}
}八、 计数排序 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。 1. 计数排序的特征当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 O(n k)。计数排序不是比较排序排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上1这使得计数排序对于数据范围很大的数组需要大量时间和内存。通俗地理解例如有 10 个年龄不同的人统计出有 8 个人的年龄比 A 小那 A 的年龄就排在第9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然年龄有重复时需要特殊处理保证稳定性这就是为什么最后要反向填充目标数组以及将每个数字的统计减去 1 的原因。2、算法步骤 1找出待排序的数组中最大和最小的元素 2统计数组中每个值为i的元素出现的次数存入数组C的第i项 3对所有的计数累加从C中的第一个元素开始每一项和前一项相加 4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1
public class CountingSort {public void sort(int[] arr) {if (arr null || arr.length 2) {return;}// 获取数组中最大的值int maxVal getMaxVal(arr);// 创建一个数组用来计数int[] counts new int[maxVal 1];// 计数for (int i 0; i arr.length; i) {counts[arr[i]];}// 反向填充int index 0;for (int i 0; i counts.length; i) {while (counts[i] 0) {arr[index] i;counts[i]--;}}}private int getMaxVal(int[] arr) {int max arr[0];for (int i 1; i arr.length; i) {max Math.max(max, arr[i]);}return max;}
}
九、 桶排序 桶排序是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效我们需要做到这两点 • 在额外空间充足的情况下尽量增大桶的数量 • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时对于桶中元素的排序选择何种比较排序算法对于性能的影响至关重要。 1. 什么时候最快 当输入的数据可以均匀的分配到每一个桶中。 2. 什么时候最慢 当输入的数据被分配到了同一个桶中。 import java.util.ArrayList;
import java.util.List;// 桶排序
public class BucketSort {public void sort(int[] arr) {if (arr null || arr.length 2) {return;}// 创建桶ListInteger[] buckets new ArrayList[10];// 初始化桶for (int i 0; i buckets.length; i) {buckets[i] new ArrayList();}// 将数据放入桶中for (int i 0; i arr.length; i) {int index arr[i] / 10;buckets[index].add(arr[i]);}//分别堆每个桶进行排序for (int i 0; i buckets.length; i) {buckets[i].sort(null);}// 将桶中的元素反向填充到arr中int index 0;for (int i 0; i buckets.length; i) {ListInteger item buckets[i];while (!item.isEmpty()) {arr[index] item.remove(0);}}}
}十、 基数排序 原理是将整数按位数切割成不同的数字然后按每个位数分别比较。基数排序的方式可以采用 LSDLeast significant digital或MSDMost significant digitalLSD的排序方式由键值的最右边开始而MSD则相反由键值的最左边开始。
MSD先从高位开始进行排序在每个关键字上可采用计数排序 LSD先从低位开始进行排序在每个关键字上可采用桶排序 1. 基数排序 vs 计数排序 vs 桶排序 基数排序有两种方法 这三种排序算法都利用了桶的概念但对桶的使用方法上有明显差异 • 基数排序根据键值的每位数字来分配桶 • 计数排序每个桶只存储单一键值 • 桶排序每个桶存储一定范围的数值 import java.util.ArrayList;
import java.util.List;/*** 计数排序*/
public class RadixSort {public void sort(int[] arr) {if (arr null || arr.length 2) {return;}// 获取最大值int maxValue getMaxVal(arr);// 获取最大位数int maxDigit getMaxDigit(maxValue);radixSort(arr, maxDigit);}private void radixSort(int[] arr, int maxDigit) {int mod 10;// 模数int dev 1;for (int i 0; i maxDigit; i) { // 比较轮数// 创建桶ListInteger[] bucket new ArrayList[10];// 对桶进行初始化for (int n 0; n bucket.length; n) {bucket[n] new ArrayList();}for (int j 0; j arr.length; j) {int bucketIndex (arr[j] / dev) % mod;bucket[bucketIndex].add(arr[j]);}// 对桶进行排序//分别堆每个桶进行排序for (int k 0; k bucket.length; k) {bucket[k].sort(null);}// 将桶中的元素反向填充到arr中int index 0;for (int m 0; m bucket.length; m) {ListInteger item bucket[m];while (!item.isEmpty()) {arr[index] item.remove(0);}}dev dev * 10;}}private int getMaxDigit(int maxValue) {int length 1;int curNum maxValue;while (curNum / 10 ! 0) {curNum curNum / 10;length;}return length;}private int getMaxVal(int[] arr) {int max arr[0];for (int i 1; i arr.length; i) {max Math.max(max, arr[i]);}return max;}
}
