本文主要是介绍变形的合并排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法要求：
输入一串数字（int），保存到数组中，比如[1,2,4,2,7,8,5,6,9,2,0,1]。
扫描一遍数组获取到已经排好序的数字序列，上面的例子就是[1,2,4],[2,7,8],[5,6,9],[2],[0,1]。
然后将第一个和第二个已经排好序的序列进行排序，将第三个和第四个进行排序，依次类推。
第一遍排完后，按照上面那个规则进行排序。直到排好序。
好像称之为合并排序的变形。
代码使用Java写的。代码并不好看，因为技术的原因，用了很多的控制变量，导致程序的阅读
比较难受。第一次写这种算法程序，希望以后能够写的好点。
代码如下：
public class Qsort {
<span style="white-space:pre"> </span>//主方法public static void main(String[] args) {//int n[] = new int[]{1,2,3,4,3,2,1,7,8,5,14,16,13};<span style="white-space:pre"> </span>//方便测试就没有输入，直接把数组写死了。//int n[] = new int[]{1,2,3,4,100,23,213,77,43,5,9,11,11};int n[] = new int[]{10,9,8,7,6,5,4,3,2,1};//int n[] = new int[]{1,1,1,1,1,1,1,1,1,1,1}; int[] b = getCount(n);sort(n, b);<span style="white-space:pre"> </span>//将需要被排序的n和保存已经排好序的序列个数的数组b传递进去。}//获取数组中已经排好序的每个序列的个数，将结果保存在数组中。public static int[] getCount(int[] n){int i = 0, count = 0, j = -1;int[] b = new int[n.length+1];//遍历一遍，获取到每个排好序的序列的个数，保存在b[]中while((i+1) < n.length){if(n[i] <= n[i+1]){i++;}else{ b[count++] = (i - j);j = i++;}}b[count] = (n.length-1 - j);count++;if(count == 1){<span style="white-space:pre"> </span>//如果count为1，说明输入的数组已经排好序了。System.out.print("\n排序结束:");print(n);System.exit(0);}//print(b);return b;<span style="white-space:pre"> </span>//将b数组返回}//打印数组方法public static void print(int n[]){for(int j = 0; j < n.length; j++){ System.out.print(n[j]+" ");}System.out.println();}//排序方法public static void sort(int[] n, int[] b){int i = 0, j = 0, q = 0;<span style="white-space:pre"> </span>//控制变量太多，我已经无力吐槽自己了。int count = 0, k = 0;while(b[k++] != 0){ //获取count：已经排好序的数组个数count++;<span style="white-space:pre"> </span>//这个值可以从getCount()方法中传递过来的，所以这个循环是多余的}k = 0;for(i = count/2; i >= 1; i--){<span style="white-space:pre"> </span>//根据count值可以知道每轮需要循环排序几次int[] sortA = new int[b[j]]; //生成两个新的数组，数组大小为b[i]int[] sortB = new int[b[j+1]];//给两个数组赋值int indexA = 0;int indexB = 0;for( ; indexA < sortA.length; indexA++){sortA[indexA] = n[k++];}for( ; indexB < sortB.length; indexB++){sortB[indexB] = n[k++];}//排序indexA = 0; indexB = 0;while(indexA < sortA.length && indexB < sortB.length){if(sortA[indexA] <= sortB[indexB]){n[q++] = sortA[indexA++];}else{n[q++] = sortB[indexB++];} }if(indexA < sortA.length){for(; indexA < sortA.length; indexA++){n[q++] = sortA[indexA];}}else if(indexB < sortB.length){for(; indexB < sortB.length; indexB++){n[q++] = sortB[indexB];}}j = j+2;}print(n);b = getCount(n);sort(n, b); }
}
程序写的一般，最近在看《代码之美》这本书，希望以后能够改善吧。
还有我想说，写算法还是用C写比较好。
这篇关于变形的合并排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
