wordpress友情链接分类显示,昆明seo技术培训,手机网站建设如何,公司网站上荣誉墙怎么做排序算法 前置知识 [排序稳定性]一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序七、归并排序八、计数排序#xff08;非比较排序#xff09;排序复杂度和稳定性总结 前置知识 [排序稳定性]
假定在待排序的记录序列中#xff0c;存在多个… 排序算法 前置知识 [排序稳定性]一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序七、归并排序八、计数排序非比较排序排序复杂度和稳定性总结 前置知识 [排序稳定性]
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且 r[i] 在 r[j] 之前而在排序后的序列中r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。 前要说明[以下所有排序均以升序排序为例]
一、直接插入排序
直接插入排序Insertion Sort是一种简单直观的排序算法它的工作原理类似于我们 整理一组扑克牌的 方法。该算法的特点是 排第 i 个的时候说明前 i-1 个已经有序了 该算法逐个将待排序的元素插入到已排序序列中的正确位置从而逐步构建有序序列。 实现思路 从第二个元素开始默认第一个元素本身是有序的将它与已排序序列进行比较寻找插入位置。如果 待插入元素 小于前一个元素将前一个元素后移一位腾位置。如果 待插入元素 大于前一个元素则找到了插入位置。如果 待插入元素 小于所有已排序序列则插入到第一个位置。重复步骤 1、2、3直到所有元素都被插入到正确的位置为止。 public static void insertSort(int[] array) {// 从 1 下标开始向前插入for (int i 1; i array.length; i) {// 记录待插入下标 i 的值int tmp array[i];// 将 i 下标对应值分别和 i 下标之前的元素比较int j i - 1;for (; j 0; j--) {if (tmp array[j]) {// 升序排序如果 value(i) 小于之前元素该元素向后挪动array[j 1] array[j];} else {// 如果 value(i) 前面的某一个元素值即找到插入位置跳出循环break;}}// 代码走到这里表示// 1.break跳出循环即在[0,i]下标之间找到小于value(i)的元素// 2.value(i) 在 [0,i]下标之间是最小的array[j 1] tmp;}
}插入排序特性分析
时间复杂度 最坏情况对于上述插入排序最坏情况下的时间复杂度是一个等差数列 O ( 1 2 . . . N ) O ( N 2 ) O(12...N)O(N^2) O(12...N)O(N2) 最好情况最好的情况即待排序列本身就是有序的插入排序算法仅遍历比较一次时间复杂度为 O ( N ) O(N) O(N) 因此对于插入排序来说元素集合越接近有序直接插入排序算法的时间效率越高空间复杂度 由于没有使用额外空间故空间复杂度为 O ( 1 ) O(1) O(1)稳定性 上述插入排序算法是稳定的。但是如果将 tmp array[j] 改为 tmp array[j]那么排序就不在稳定了。因为得出结论如果一个排序时稳定的那么可以实现为不稳定如果一个排序本身就不稳定无法实现为稳定排序。
二、希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是选定一个整数增量 g a p gap gap把待排序序列中所有记录分成多个组所有距离为增量 g a p gap gap 的记录分在同一组内并对每一组内的记录进行排序。然后减小增量重复上述分组和排序的工作。当增量 g a p gap gap 缩小至 1 时所有记录在统一组内排好序。
希尔排序当 g a p 1 gap 1 gap1 时都是预排序目的是让数组更接近于有序。对于插入排序来说元素趋于有序插入排序时间复杂度就趋于 O(N)。所以希尔排序是对直接插入排序的优化。 实现思路 首先确定初始的增量 gap可以选择将数组长度的一半作为初始值。对每个增量进行分组代码控制和排序操作插入排序。每次增量减少一半即 gap gap / 2直到 gap 缩小至 1 时执行最后一次分组和排序操作。 public static void shellSort(int[] array) {// 确定增量 gapint gap array.length/2;while (gap 1) {shell(array, gap);// 每次增量减少gap gap / 2;}// 增量为1时再排一次shell(array, gap);}// 这段代码利用 下标 i、j 和 gap 之间的关系实现每一组的交替插入排序
private static void shell(int[] array, int gap) {// 初始时 i gap 使下标 i 指向第 1 组的第 2 个元素// 便于对每一组执行插入排序for (int i gap; i array.length; i) {// 记录待插入下标 i 的值int tmp array[i];// 下标 j 指向每组的已排序序列int j i - gap;// 寻找每组 value(i) 的插入位置for (; j 0; j - gap) {if (array[j] tmp) {array[j gap] array[j];} else {break;}}// 代码走到这里表示找到插入位置array[j gap] tmp;}
}希尔排序特性分析
时间复杂度 希尔排序的时间复杂度涉及数学上尚未解决的难题因此我们暂时无法得出希尔排序准确的时间复杂度这里给出一个范围 O ( N 1.3 ) ∼ O ( N 1.5 ) O(N^{1.3}) \sim O(N^{1.5}) O(N1.3)∼O(N1.5)空间复杂度 由于排序过程没有使用额外的空间因此空间复杂度为 O ( 1 ) O(1) O(1)稳定性 在希尔排序中元素按照增量分组并进行插入排序这可能导致相等的元素在排序后的相对顺序发生变化因此希尔排序是一个不稳定的排序算法
三、直接选择排序
直接选择排序思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在待排序列的起始位置直到全部待排序的数据元素排完 。 实现思路 记录待排序列起始下标 i遍历待排序列每次找到待排元素中的最小值下标 minIndex交换下标值将最小值放到待排序列的起始位置并且 i 缩小待排序列范围重复步骤1、2 直到排序完待排序列序列即为有序 // 交换函数swap()
public static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}public static void selectSort(int[] array) {// 待排序列起始下标 ifor (int i 0; i array.length; i) {// 初始化最小值下标int minIndex i;// 寻找待排元素中最小值for (int j i 1; j array.length; j) {if (array[j] array[minIndex]) {//更新最小值下标minIndex j;}}// 此时minIndex放的是最小元素的下标swap(array, minIndex, i);}
}直接选择排序变种 上述直接选择排序的思路是每次寻找最小值放到待排序列起始位置从而实现排序。这里还有另外一种实现思路 同时记录待排序列的起始下标 left 和终止下标 right即限制待排序列范围 [leftright]每次遍历待排序列同时记录最大值下标 maxIndex 和最小值下标 minIndex交换下标值将最大值放到待排序列的终止位置最小位置放到待排序列的起始位置每次交换缩小待排序列范围 left 、right --直到待排序列范围为 0即 left right public static void selectSort2(int[] array) {// 待排序列起始下标int left 0;// 待排序列终止下标int right array.length - 1;// 遍历待排序列while (left right) {// 初识值假定最小最大值下标都在最左边int maxIndex left;int minIndex left;//每次找到当前范围内的最大值下标maxIndex最小值下标minIndexfor (int i left 1; i right; i) {if (array[i] array[minIndex]) {minIndex i;}if (array[i] array[maxIndex]) {maxIndex i;}}// 确定最小值位置swap(array, left, minIndex);// 如果最大值对应待排序列的起始下标需要特殊处理// 因为上面的交换会将最大值换到下标 minIndex 处if (maxIndex left) {maxIndex minIndex;}// 确定最大值位置swap(array, right, maxIndex);// 缩小待排序列范围left;right--;}
}直接选择排序特性分析 时间复杂度 无论是 直接选择排序 还 是直接选择排序 的变种作为一种非常“暴力”的排序不管待排序列本身是否有序每一趟都会遍历待排序列时间复杂度都是一个等差数列相加即 O ( N 2 ) O(N^2) O(N2) 空间复杂度 由于没有使用额外空间故空间复杂度为 O ( 1 ) O(1) O(1) 稳定性 在选择排序中每次会选择未排序序列中的最小或最大元素然后将其与未排序序列的第一个位置交换。这个操作可能会破坏相等元素之间的相对顺序导致排序后它们的相对位置发生改变。因此直接选择排序是不稳定的。
四、堆排序
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。它的原理是利用堆的性质即堆顶元素为堆中的最大值最小值的特性每次确定一个有序序列元素的位置逐渐构建有序序列。 注意排升序需要构建大根堆排降序需要构建小根堆。 实现原理 构建源待排序列为大顶堆。将堆顶元素和待排序列的最后一个元素交换。重新确定待排序列范围并将新待排序列使用向下调整算法构建为大根堆。重复上述步骤2、3直到序列有序。 public static void heapSort(int[] array) {// 将源序列构建为大根堆creatHeap(array);// 进行堆排序// 从后向前调整待排序列int end array.length - 1;while (end 0) {swap(array, 0, end);shiftDown(array, 0, end);end--;}
}//这里是建立大根堆-升序排序
private static void creatHeap(int[] array) {for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}
}
// 向下调整算法
private static void shiftDown(int[] array, int parent, int len) {int child 2 * parent 1;//一定有左孩子while (child len) {//有左孩子和右孩子if (child 1 len array[child] array[child 1]) {child;}// 此时child拿到最大值孩子下标if (array[child] array[parent]) {swap(array, child, parent);parent child;child 2 * parent 1;} else {break;}}
}堆排序特性分析 时间复杂度 在构建大根堆creatHeap的过程中需要对每个非叶子节点进行向下调整操作shiftDown这部分的时间复杂度为 O ( n ) O(n) O(n)。在堆排序过程中需要将堆顶元素与当前待排序的最后一个元素交换并对堆顶元素进行向下调整操作。重复这个过程直到所有元素都被排序这部分的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。并且无论输入序列的初始状态如何堆排序都需要进行完整的堆构建和元素交换操作。因此整个堆排序的时间复杂度为 O ( n n l o g n ) O(n nlogn) O(nnlogn)即 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度 堆排序是一种原地排序算法不需要额外的辅助空间空间复杂度为 O ( 1 ) O(1) O(1) 稳定性 在堆排序中交换节点的操作可能会改变具有相同值的元素之间的相对顺序因此堆排序是一个不稳定的排序算法。
五、冒泡排序
冒泡排序是一种简单的排序算法它重复地比较相邻的两个元素并按照升序降序交换位置直到整个序列有序。冒泡排序的过程类似于气泡不断往上升的过程较大的元素会像气泡一样逐渐“浮”到序列的末尾因此得名冒泡排序。
实现思路 从序列的第一个元素开始依次比较相邻的两个元素。如果当前元素大于后一个元素则交换这两个元素的位置直到完成一轮比较。重复步骤 2 直到整个序列有序。因为每一轮比较都会将本轮最大的元素移动到末尾故每次比较的元素个数减少 1优化。 public static void bubbleSort(int[] array) {// 外层循环控制比较的轮数for (int i 0; i array.length - 1; i) {// 判断是否有序的标志boolean flag true;// 内层循环进行相邻元素的比较和交换每一轮次比较个数少1优化1for (int j 0; j array.length - 1 - i; j) {// 这里是升序if (array[j] array[j 1]) {swap(array, j, j 1);// 只要进入比较就说明还不一定有序flag false;}}//如果在一趟比较中一次都不比较说明已经有序不需要继续遍历优化2if (flag) {break;}}
}冒泡排序特性分析 时间复杂度 加入两个优化后最坏情况下上述冒泡排序的时间复杂度为 O ( n − 1 n − 2 . . . 1 ) O ( n 2 ) O(n-1n-2...1)O(n^2) O(n−1n−2...1)O(n2)。最好情况下即序列本身有序此时仅遍历序列 1 次时间复杂度为 O ( 1 ) O(1) O(1). 不加入优化的情况下最好情况和最坏情况的时间复杂度均为 O ( n 2 ) O(n^2) O(n2). 空间复杂度 冒泡排序是一种原地排序算法不需要额外的辅助空间空间复杂度为 O ( 1 ) O(1) O(1). 稳定性 冒泡排序是一种稳定的排序算法保持了相等元素的相对顺序。
六、快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元 素作为基准值按照该基准值将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有 元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
注意快速排序每次划分都可以确定序列中一个元素的有序位置。
实现思路 首先根据基准值对待排序列进行划分使左子序列小于基准值右子序列大于基准值。然后递归排左子序列和右子序列 直到子序列为空 或者 子序列仅剩1个元素默认有序。 public static void quickSort(int[] array) {quick(array,0,array.length-1);
}
// 为了接口的统一抽象出一个方法
private static void quick(int[] array,int start,int end) {// 递归终止条件// start end 表示子序列为空// start end 表示子序列仅剩1个元素if (start end) {return;}// 按照基准值对array数组的 [left, right)区间中的元素进行划分// 返回基准值下标便于递归左右子序列int pivotIndex partition(array,start, end);// 划分成功后以div为边界形成了左右两部分 [pivot, div) 和 [pivot1, right)// 递归排[left, pivotIndex)quick(array,start,pivotIndex-1);// 递归排[pivotIndex1, right)quick(array,pivotIndex1,end);
}快排的一个核心函数是划分 partition() 根据按照基准值划分区间的方式主要有以下 3 种实现方法
1. Hoare版 Hoare 划分实现思想 首先确定基准值 pivot一般选取序列区间 [leftright] 最左边元素或最右边元素为基准值。这里选择value(left) 为基准值。让 left 指针向右走直到找到大于基准值 pivot 的值right 指针向左走直到找到小于基准值 pivot 的值。分别找到之后让left、right下标值交换使比基准值小的在 left 下标处比基准值大的在 right 下标处。当某一时刻left right时此时 left 和 right 下标均指向小于基准值的下标此时将基准值 pivot 和 left/right 下标对应值交换即完成该序列划分。 private static int partition(int[] array, int left, int right) {// 记录初始时pivot下标int i left;// 记录基准值int pivot array[left];while (left right) {// 注意取等否则可能会出现左右横跳的死循环[left和right相等时]// 注意取左边为基准值就右边 right 先走// 1.寻找右边小于piovt的值while (left right array[right] pivot) {right--;}// 2.寻找左边大于pivot的值while (left right array[left] pivot) {left;}// 交换swap(array, left, right);}// left right 时让下标值交换swap(array, left, i);// 此时 left 和 right 均指向pivot基准值返回即可return left;
}1为什么以序列最左为基准值时需要 right 先走left 后走
这里我们假设每次 right 先走right 后走此时当 left right 时指向的下标对应大于基准值 pivot 的元素如果此时将下标交换就会导致大于基准值的元素出现在 pivot 的左边这是一个隐蔽的 bug我们应该避免 2为什么 array[right] pivot 寻找小于基准值 和 array[left] pivot 寻找大于基准值时必须取等 2. 挖坑法 挖坑法 划分实现思想 首先保存基准值 pivot pivot对应下标为第一个坑位。这里假设在区间 [leftright] 中 value(left) 为基准值则坑位对应下标为 left.right 开始向前移动找到大于 pivot 的的位置找到后将该位置值放入坑位中该位置形成新的坑位。left 开始向后移动找到小于 pivot 的位置找到后将该位置值放入到坑位中该位置形成新的坑位。重复步骤2、3直到 left right 时将保存的 pivot 值放到当前坑位划分结束。 private static int partition2(int[] array, int left, int right) {// 保存基准值int pivot array[left];while (left right) {//注意条件取等(原因同 hoare)// 1.寻找右边小于piovt的值while (left right array[right] pivot) {right--;}// 入坑array[left] array[right];// 2.寻找左边大于piovt的值while (left right array[left] pivot) {left;}// 入坑array[right] array[left];}// pivot 值入坑array[left] pivot;// 返回pivot值对应下标return left;
}3. 前后指针了解 前后指针 划分实现思想 设置两个指针 cur 、prev初始时prev 指向序列开头cur 指向 prev 的后一个位置。判断 cur 指针指向数据是否大于基准值 pivot 如果大于cur向后移动直到找到小于基准值 pivot 的位置。通过步骤2此时cur指针指向数据小于基准值 pivot 。prev 向后移动 1 位 并判断此时指针 cur 是否等于 prev如果 cur ! prev则说明 prev 和 cur 之间存在大于 pivot 的值并且prev此时指向大于pivot的值然后让value(prev) 和 value(cur) 交换即可如果 cur prev说明prev和cur之间不存在大于 pivot 的值即 prev 和 cur 相邻不进行交换cur 继续向后移动。直到 cur 越界将 基准值 pivot 同 value(prev) 交换。完成划分。 前后指针法非常巧妙通过控制cur 指针 和 prev 指针的位置实现序列划分 private static int partition3(int[] array,int left,int right) {// 初始化指针位置int prev left;int cur left1;while(cur right) {// 条件限制保证不相邻时 prev 下标记录的是左边小于基准值的最后一个if (array[cur]array[left] array[prev]!array[cur]) {swap(array,prev,cur);}cur;}// 上面走完了需要把基准值放到 prev 下标下swap(array,prev,left);// 返回基准值下标return prev;
}快速排序的非递归实现 快排的非递归实际上是使用栈来模拟递归操作。因此首先需要创建一个栈。将待排序序列的起始位置 left 和结束位置 right 压入栈中。循环出栈判断栈是否为空如果不为空从栈中弹出 right 和 left并调用 partition 函数对当前范围内的子序列进行划分得到基准元素的正确位置 pivotIndex。如果 pivotIndex 左边的范围仍然有两个以上的元素则将左边的起始位置 left 和 pivotIndex - 1 压入栈中下一轮循环将对其进行划分。如果 pivotIndex 右边的范围仍然有两个以上的元素则将 pivotIndex 1 和右边的结束位置 right 压入栈中下一轮循环将对其进行划分。循环结束后所有序列划分完毕排序完成。 public static void quickSort2(int[] array) {// 创建栈DequeInteger stack new LinkedList();// 将待排序列起始和终止位置压栈int left 0;int right array.length - 1;// 初始时如果leftright直接返回if (left right) {stack.push(left);stack.push(right);} else {return;}// 循环出栈while (!stack.isEmpty()) {right stack.pop();left stack.pop();// 对子序列进行划分int pivotIndex partition(array,left,right);// 判断左子序列是否存在两个以上元素if (pivotIndex left 1) {stack.push(left);stack.push(pivotIndex - 1);}// 判断右子序列是否存在两个以上元素if (pivotIndex right - 1) {stack.push(pivotIndex 1);stack.push(right);}}
}快速排序特性分析 时间复杂度 最好情况最好情况下即每次都能均衡地划分序列将序列划分成两个子序列最终递归的高度为一颗完全二叉树的高度为 l o g 2 ( N ) log_2(N) log2(N)每一层需要比较交换 n 次故时间复杂度为 O ( N . l o g 2 ( N ) ) O(N.log_2(N)) O(N.log2(N)). 最坏情况当序列本身为升序或逆序的情况下每次划分只有右子序列或左子序列则最终递归的高度为一颗n层高的单分支二叉树的高度第一层需比较交换 n 次第二层比较交换 n-1 次……故时间复杂度为 O ( N 2 ) O(N^2) O(N2) 空间复杂度 最好情况下同上递归的高度为 l o g 2 ( N ) log_2(N) log2(N)即空间复杂度为 O ( l o g 2 ( N ) ) O(log_2(N)) O(log2(N)). 最坏情况下同上递归的高度为 N N N即空间复杂度为 O ( N ) O(N) O(N). 稳定性 由于在划分的过程中相等的元素之间可能会发生位置的交换导致原本相等的元素的相对顺序发生改变。因此快速排序是不稳定的。
1快速排序优化一三数取中法确定基准值 2快速排序优化二后期递归改用直接插入排序 通过上面的分析我们已知平均情况下快速排序的递归类似于一颗完全二叉树而对于一颗完全二叉树来说它的最后几层结点的个数基本上占据了整个二叉树结点的 3 / 4 3/4 3/4也就是说快速排序递归深度越深递归的次数就越多。再者对于快速排序来说当递归来到后几层时子序列序列已经基本上趋于有序了。
因此为了减少快速排序后期的递归的次数同时利用插入排序特性插入排序适用于小规模或近乎有序的序列在小规模序列上运行时有着较好的性能。所以当划分得到的子序列长度小于等于一个阈值时可以选择直接使用插入排序来对子序列进行排序。
经过上述 2 2 2 次优化最终快速排序可实现为 public static void quickSort(int[] array) {quick(array,0,array.length-1);}// 为了接口的统一抽象出一个方法private static void quick(int[] array,int start,int end) {// 递归终止条件// start end 表示子序列为空// start end 表示子序列仅剩1个元素if (start end) {return;}// 优化二递归到小的子区间时可以考虑使用直接插入排序if (end-start116) {quickInsert(array,start,end);return;}// 优化一三数取中法选 pivot 防止单枝树int index midThree(array,start,end);// 每次将 pivot 值换到 start 位置swap(array,start,index);// 按照基准值对array数组的 [left, right)区间中的元素进行划分// 返回基准值下标便于递归左右子序列int pivotIndex partition(array,start, end);// 划分成功后以div为边界形成了左右两部分 [pivot, div) 和 [pivot1, right)// 递归排[left, pivotIndex)quick(array,start,pivotIndex-1);// 递归排[pivotIndex1, right)quick(array,pivotIndex1,end);}/*优化*/// 1.三数取中法选 pivot防止单枝树private static int midThree(int[] array,int left,int right) {int mid (leftright)/2;if (array[left]array[right]) {if (array[mid]array[right]) {return right;} else if (array[mid]array[left]) {return left;} else {return mid;}} else {//array[left]array[right]的情况if (array[mid]array[left]) {return left;} else if (array[mid]array[right]) {return right;} else {return mid;}}}// 2. 递归到小的子区间时可以考虑使用插入排序[利用越有序越快的特点]public static void quickInsert(int[] array,int left,int right) {for (int i left1; i right; i) {int tmp array[i];//将i下标对应值分别和i下标后元素比较int j i - 1;for (; j left; j--) {//升序排序如果小于其后元素向后挪动if (array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}}七、归并排序
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列。过程主要包括分解、合并排序。 归并排序递归实现 将待排序列递归分解每次分解为左子序列 [leftmid]右子序列 [mid1right]。分解到每个子序列仅剩1个元素时开始合并排序的回溯过程每次合并将两个有序序列合并为1个有序序列。 public static void mergeSort(int[] array) {// 为了接口的统一性这里将归并排序抽象出一个方法mergeSortFunc(array,0,array.length-1);
}
// 归并排序
private static void mergeSortFunc(int[] array, int start,int end){// 当元素个数小于等于1时分解停止if (start end) {return;}// 递归分解int mid (startend)/2;// 左子序列[left,mid]mergeSortFunc(array,start,mid);// 右子序列[mid1,right]mergeSortFunc(array,mid1,end);// 合并排序merge(array,start,end,mid);
}// 递归完成后的合并排序过程
private static void merge(int[] array,int left,int right,int mid) {// 定义两个变量分别指向两个子序列的头int s1 left;int s2 mid1;// 定义一个临时数组用来存储“和并排序”的数据int[] tmp new int[right-left1];// 临时数组下标int k 0;// 进行“合并排序”的条件是两个子数组均不越界while (s1mid s2right) {if (array[s1]array[s2]) {tmp[k] array[s1];} else {tmp[k] array[s2];}}// 将还没走完的数组全部排入临时数组中while (s1mid) {tmp[k] array[s1];}while (s2right) {tmp[k] array[s2];}// 将排好的数据放入原来的数组中-注意: ileft找到原数组对应下标for (int i 0; i tmp.length; i) {array[ileft] tmp[i];}
}归并排序非递归实现 记录每组有序个数gap省去递归分解过程直接从每组1个元素开始合并排序当每组仅有1个元素时默认有序。通过确定每两组有序序列的 left、mid、right 下标调用 merge 方法两组两组进行合并排序。每趟排序过后每组有序个数乘 2.重复步骤2、3 直到序列有序。 public static void mergeSort2(int[] array) {// gap 表示当前每组多少个有序元素int gap 1;// 合并过程// 因为每组最多为 array.length 个所以 gap array.lengthwhile (gap array.length) {// 两组两组的合并序列// i gap * 2 表示去合并另外两组有序序列 for (int left 0; left array.length; left gap * 2) {int mid leftgap-1;// 有可能会越界处理越界情况if(mid array.length) {mid array.length-1;}int right midgap;// 有可能会越界处理越界情况if(right array.length) {right array.length-1;}// 进行合并排序merge(array,left,right,mid);}// 当前为每2个一组有序下次变成4个一组有序gap * 2;}
}这里需要注意的是mid 和 right 下标可能会越界需要处理越界情况。例如如下情况就会越界 快速排序特性分析 时间复杂度 在分解时需要对序列进行二分对于长度为n的序列需要进行 l o g 2 ( n ) log_2(n) log2(n) 次划分。在每一次合并排序操作中需要每一次分解的元素进行比较和合并时间复杂度为 O ( n ) O(n) O(n)。总的时间复杂度为 O ( n l o g 2 ( n ) ) O(nlog_2(n)) O(nlog2(n)). 空间复杂度 归并排序需要额外的空间来存储临时的合并结果因此空间复杂度为 O(n). 稳定性 归并排序保持了相等元素的相对顺序是稳定的排序。
归并排序的应用场景 归并排序可以通过外部排序的方式处理海量数据的排序问题。外部排序是一种针对无法一次性载入内存的大规模数据进行排序的技术。 将海量数据划分为多个能够载入内存的小块。对每个小块因为内存已经可以放的下所以任意排序方式都可以。将结果生成有序的子文件。将每个子文件归并成一个更大的有序文件。如果仍然无法一次性载入内存重复步骤2和步骤3直到所有的子文件都被归并成一个完整的有序文件。 八、计数排序非比较排序
计数排序是一种非比较排序算法其基本思想是统计待排序序列中每个元素的出现次数然后根据这些统计信息将元素放置到正确的位置上从而达到排序的目的。 计数排序的主要实现思想如下 找出待排序序列 arr 中的最大值 max 和最小值 min并确定计数数组 count 的长度 len max - min 1。计数数组用于存储每个元素的出现次数。遍历待排序序列 arr统计每个元素出现的次数并在计数数组中相应的位置 arr[i] - min 进行累加。根据计数数组中统计的信息重新构建排序后的序列。具体方法是遍历计数数组根据元素的累加次数将对应元素放入待排序列中。 public static void countSort(int[] array) {//1. 遍历数组 找到最大值 和 最小值int min array[0];int max array[0];for (int i 1; i array.length; i) {if (array[i]min) {min array[i];}if (array[i]max) {max array[i];}}//2. 根据范围 确定计数数组的长度int len max - min 1;int[] count new int[len];//3.遍历数组在计数数组当中 统计每个元素出现的次数for (int i 0; i array.length; i) {// 下标值 i - min 表示相对位置int index array[i]-min;count[index];}int k0;//4.遍历计数数组根据元素的累加次数将对应元素放入待排序列中for (int i 0; i count.length; i) {while (count[i]!0) {// 下标值 i min 表示真实的数据array[k] imin;count[i]--;}}
}计数排序特性分析
时间复杂度 计数排序的时间复杂度为 O ( n k ) O(nk) O(nk)其中 n 表示待排序序列的长度k 表示计数数组的长度也就是待排序列的范围。空间复杂度 计数排序的空间复杂度为O(k)k表示计数数组的长度即待排序列的范围。稳定性 当前上面这种实现方式下没有稳定性可言。适用场景 对于计数排序来说当取值范围较大时或者数据不集中需要耗费较大的空间来创建计数数组。因此对于计数排序来说它适用于 已知一定范围内相对集中的整数排序。
排序复杂度和稳定性总结
排序方法最好情况时间复杂度平均情况时间复杂度最坏情况时间复杂度空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定希尔排序O(n)O(n^1.3)O(n^2)O(1)不稳定堆排序O(n * log(n))O(n * log(n))O(n * log(n))O(1)不稳定快速排序O(n * log(n))O(n * log(n))O(n^2)O(log(n)) ~ O(n)不稳定归并排序O(n * log(n))O(n * log(n))O(n * log(n))O(n)稳定 文章转载自： http://www.morning.pkrtz.cn.gov.cn.pkrtz.cn http://www.morning.rwcw.cn.gov.cn.rwcw.cn http://www.morning.wclxm.cn.gov.cn.wclxm.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.txysr.cn.gov.cn.txysr.cn http://www.morning.dmlsk.cn.gov.cn.dmlsk.cn http://www.morning.phwmj.cn.gov.cn.phwmj.cn http://www.morning.mtrrf.cn.gov.cn.mtrrf.cn http://www.morning.hylbz.cn.gov.cn.hylbz.cn http://www.morning.nhlyl.cn.gov.cn.nhlyl.cn http://www.morning.pqqhl.cn.gov.cn.pqqhl.cn http://www.morning.frsxt.cn.gov.cn.frsxt.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.jfwrf.cn.gov.cn.jfwrf.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.ghryk.cn.gov.cn.ghryk.cn http://www.morning.wjxtq.cn.gov.cn.wjxtq.cn http://www.morning.jmspy.cn.gov.cn.jmspy.cn http://www.morning.jrhcp.cn.gov.cn.jrhcp.cn http://www.morning.crsqs.cn.gov.cn.crsqs.cn http://www.morning.pgmyn.cn.gov.cn.pgmyn.cn http://www.morning.mzkn.cn.gov.cn.mzkn.cn http://www.morning.qggm.cn.gov.cn.qggm.cn http://www.morning.fy974.cn.gov.cn.fy974.cn http://www.morning.dwkfx.cn.gov.cn.dwkfx.cn http://www.morning.crqpl.cn.gov.cn.crqpl.cn http://www.morning.yfphk.cn.gov.cn.yfphk.cn http://www.morning.qmmfr.cn.gov.cn.qmmfr.cn http://www.morning.tkgjl.cn.gov.cn.tkgjl.cn http://www.morning.rrbhy.cn.gov.cn.rrbhy.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.lhxdq.cn.gov.cn.lhxdq.cn http://www.morning.bbxbh.cn.gov.cn.bbxbh.cn http://www.morning.kjrlp.cn.gov.cn.kjrlp.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.srckl.cn.gov.cn.srckl.cn http://www.morning.dhtdl.cn.gov.cn.dhtdl.cn http://www.morning.kjrlp.cn.gov.cn.kjrlp.cn http://www.morning.mgbsp.cn.gov.cn.mgbsp.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.tjjkn.cn.gov.cn.tjjkn.cn http://www.morning.fkgqn.cn.gov.cn.fkgqn.cn http://www.morning.jrbyz.cn.gov.cn.jrbyz.cn http://www.morning.qnzld.cn.gov.cn.qnzld.cn http://www.morning.txhls.cn.gov.cn.txhls.cn http://www.morning.bnxfj.cn.gov.cn.bnxfj.cn http://www.morning.ygth.cn.gov.cn.ygth.cn http://www.morning.jlschmy.com.gov.cn.jlschmy.com http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.hmqmm.cn.gov.cn.hmqmm.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.wttzp.cn.gov.cn.wttzp.cn http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.njnqn.cn.gov.cn.njnqn.cn http://www.morning.zbkwj.cn.gov.cn.zbkwj.cn http://www.morning.qinhuangdjy.cn.gov.cn.qinhuangdjy.cn http://www.morning.pqjlp.cn.gov.cn.pqjlp.cn http://www.morning.wttzp.cn.gov.cn.wttzp.cn http://www.morning.nxfuke.com.gov.cn.nxfuke.com http://www.morning.qpsxz.cn.gov.cn.qpsxz.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.dswtz.cn.gov.cn.dswtz.cn http://www.morning.pfnwt.cn.gov.cn.pfnwt.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.bgdk.cn.gov.cn.bgdk.cn http://www.morning.sypby.cn.gov.cn.sypby.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.qhczg.cn.gov.cn.qhczg.cn http://www.morning.qpxrr.cn.gov.cn.qpxrr.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.rrdch.cn.gov.cn.rrdch.cn http://www.morning.nlgmr.cn.gov.cn.nlgmr.cn http://www.morning.ffptd.cn.gov.cn.ffptd.cn http://www.morning.pjftk.cn.gov.cn.pjftk.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.mkyny.cn.gov.cn.mkyny.cn http://www.morning.gcbhh.cn.gov.cn.gcbhh.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn
