上篇文章我们讨论了快速排序算法,它与归并算法同属分治算法的一种。
两者在实现上很相似,都使用了分治递归的策略来实现。
相信大家对快排和归并排序都不陌生,不过我们平常接触到的一般是这两种算法的递归实现方式。
以Java为例,其Arrays类中的sort在排序Object的时候用的就是归并排序。
不过其在实现上做了优化,在子问题足够小时(每个递归子序列长度不大于7)通过插入排序完成这个子序列的排序。
概括而言,Java中的Arrays.sort在排序Object对象的数组时用的是归并排序+插入排序的方式,即对插入排序结果的归并。
Java中的实现如下:
private static final int INSERTIONSORT_THRESHOLD = 7; /** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } }
上述方式通过函数递归调用实现,本文接下来要讨论的是该方案的非递归实现,实现语言是Bash。
与上篇文章中使用的方法类似,通过栈的数据结构特点,模拟函数的递归调用。
由于快排的递归操作不需要对子问题进行合并,因此只需要将问题按照一定策略分解,并将子问题解决。
而归并排序则需要将子问题的结果做进一步的处理,因此,在栈空间的使用上,不仅需要跟踪递归调用的栈,还需要记录子问题计算结果的栈,用来对子问题结果做递归合并处理。
这种方式有点像通过逆波兰式计算表达式结果的思路,具体代码如下:
#!/bin/bash declare -a inputArray=(1 3 2 4 5 9 8 7 0); ##init for large number test for i in `seq 1000` do inputArray[$i]=$RANDOM; done inputLength=${#inputArray[@]}; lastIndex=$((inputLength-1)); ## trace Stack for recursive calls declare -a traceStackStart; declare -a traceStackEnd; traceStackDeep=0; ##stack for the already sorted sub Array to merge declare -a mergeStackStart; declare -a mergeStackEnd; mergeStackDeep=0; ## begin recursive call... traceStackStart[0]=0; traceStackEnd[0]=$lastIndex; traceStackDeep=1; ## recursive call until traceStack empty while [ $traceStackDeep -ne 0 ] do #pop stack traceStackDeep=$((traceStackDeep-1)); low=${traceStackStart[$traceStackDeep]}; hig=${traceStackEnd[$traceStackDeep]}; if [ "$low" = "+" ]; then mergeStackDeep=$((mergeStackDeep-1)); l1=${mergeStackStart[$mergeStackDeep]}; h1=${mergeStackEnd[$mergeStackDeep]}; mergeStackDeep=$((mergeStackDeep-1)); l2=${mergeStackStart[$mergeStackDeep]}; h2=${mergeStackEnd[$mergeStackDeep]}; ## merge sorted subArray here i=0; j=0; desLow=0; declare -a tmp=(0); for((i=l1,j=l2;i<=h1 && j<=h2;desLow++)) do if [ ${inputArray[$i]} -le ${inputArray[$j]} ]; then tmp[$desLow]=${inputArray[$i]}; i=$((i+1)); else tmp[$desLow]=${inputArray[$j]}; j=$((j+1)); fi done if [ $i -gt $h1 ]; then for((;j<=h2;j++,desLow++)) do tmp[$desLow]=${inputArray[$j]}; done else for((;i<=h1;i++,desLow++)) do tmp[$desLow]=${inputArray[$i]}; done fi for((tmpI=0,i=l1;i<=h2;i++,tmpI++)) do inputArray[$i]=${tmp[$tmpI]}; done ## push the merge sort result to the mergeStack mergeStackStart[$mergeStackDeep]=$l1; mergeStackEnd[$mergeStackDeep]=$h2; mergeStackDeep=$((mergeStackDeep+1)); elif [ $low -lt $hig ]; then l=$low; h=$hig; space=$((h-l)); if [ $space -le 7 ]; then #insertion sort here for((i=l+1;i<=h;i++)) do for((j=i;j>l;j--)) do if [ ${inputArray[$j-1]} -gt ${inputArray[$j]} ]; then tmp=${inputArray[$j-1]}; inputArray[$j-1]=${inputArray[$j]}; inputArray[$j]=$tmp; fi done done mergeStackStart[$mergeStackDeep]=$l; mergeStackEnd[$mergeStackDeep]=$h; mergeStackDeep=$((mergeStackDeep+1)); else m=$((l+(h-l)/2)); n=$((m+1)); traceStackStart[$traceStackDeep]="+"; traceStackEnd[$traceStackDeep]="+"; traceStackDeep=$((traceStackDeep+1)); traceStackStart[$traceStackDeep]=$l; traceStackEnd[$traceStackDeep]=$m; traceStackDeep=$((traceStackDeep+1)); traceStackStart[$traceStackDeep]=$n; traceStackEnd[$traceStackDeep]=$h; traceStackDeep=$((traceStackDeep+1)); fi fi done echo ${inputArray[*]};
相关推荐
主要介绍了JAVA基于Arrays.sort()实现数组升序和降序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
主要介绍了Java Arrays.sort和Collections.sort排序实现原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了深入理解java中Arrays.sort()的用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了Java中的Arrays.sort()代码详解,涉及Arrays.sort()简单示例,策略模式,”super”的使用等相关内容,具有一定借鉴价值,需要的朋友可以参考下。
主要介绍了Java中Arrays.asList()方法将数组作为列表时的一些差异的相关资料,需要的朋友可以参考下
Java Methods-Arrays.ppt
个人研究所得,包含对其内部jdk源码的分析。 同时会结合ArrayList中对该两个方法的调用做进一步说明。...总结一句话:在允许的情况下,尽量调用System.arraycopy方法,实在不行再调用Arrays.copyOf方法。
Apress.PHP.Arrays.Single.Multi-dimensional.Associative.and.Object.Arrays.in.PHP.7.1484225554.rar 最新书籍,精讲PHP数组,文字版PDF
主要介绍了Java Arrays.asList使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
Using Java Arrays Chapter 5. Using Loops in Java Code Chapter 6. Encapsulating Data and Exposing Methods in Java Chapter 7. Using Java Methods to Communicate Chapter 8. Using Java Constructors ...
Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_Arrays.pdf Arduino项目开发 Control_Arrays_...
Gain an in-depth understanding of PHP 7 arrays. After a quick overview of PHP 7, each chapter concentrates on single, multi-dimensional, associative, and object arrays. PHP Arrays is a first of its ...
在本篇文章里小编给大家分享的是关于Java中使用Arrays.asList初始化ArrayList的知识点内容,需要的朋友们参考下。
Antenna Arrays.pdf
本文主要对Arrays.asList方法进行总结。具有很好的参考价值,下面跟着小编一起来看下吧
Arrays.sort(int[] a, int fromIndex, int toIndex) 并行排序:JDK1.8新增 Arrays.parallelSort(int[] a) Arrays.parallelSort(int[] a, int fromIndex, int toIndex) 并行计算: JDK1.8新增 支持函数式编程 根据...
在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序。例如: String[] arrays = new String[] { gyu, sdf, zf, 大同, 收到, 地方, 三等分, 的人, 反对高铁, 泛代数, 上的投入...
在Java中,Arrays类是一个实用工具类,用于在数组上执行各种操作,包括排序、搜索、比较等。它提供了一组静态方法,以便在数组中进行常见的操作。下面是一个超级详细的介绍Java中Arrays类的常用方法和功能。
网络图片地址url集合arrays.xml文件
/** *Arrays提供数组操作的一系列实用方法 *1输出 *2排序 *3二分查找 *4复制 *5扩容 */