锐客网

  1. 首页 > 睿知 > it技术 > >

合并排序算法代码JAVA java合并数组排序( 二 )

IT技术排序


合并两个有序数组的方法：
function subSort(arr1,arr2){var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice();while(bArr1.length!=0 || bArr2.length!=0){if(bArr1.length == 0){arr3 = arr3.concat(bArr2);bArr2.length = 0;}else if(bArr2.length == 0){arr3 = arr3.concat(bArr1);bArr1.length = 0;}else{if(bArr1[0]=bArr2[0]){arr3.push(bArr1[0]);bArr1.shift();}else{arr3.push(bArr2[0]);bArr2.shift();}}}return arr3;}
归并排序：
function mergeSort(arr){var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,n;while(gapmaxgap){gap = Math.pow(2,n);if(gap=maxgap){gapArr.push(gap);}n++;}glen = gapArr.length;for (var i = 0; iglen; i++) {gap = gapArr[i];for (var j = 0; jlen; j=j+gap*2) {arrleft = arr.slice(j, j+gap);arrright = arr.slice(j+gap,j+gap*2);console.log("left:"+arrleft,"right:"+arrright);arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2));}}return arr;}
排序[4,2,6,3,1,9,5,7,8,0]输出：
left:4 right:2left:6 right:3left:1 right:9left:5 right:7left:8 right:0left:2,4 right:3,6left:1,9 right:5,7left:0,8 right:left:2,3,4,6 right:1,5,7,9left:0,8 right:left:1,2,3,4,5,6,7,9 right:0,8
看出来从最小的单位入手 。
第一轮先依次合并相邻元素：4,2;6,3; 1,9; 5,7; 8,0
合并完成之后变成： [2,4,3,6,1,9,5,7,0,8]
第二轮以2个元素为一个单位进行合并：[2,4],[3,6];[1,9],[5,7];[0,8],[];
合并完成之后变成：[2,3,4,6,1,5,7,9,0,8]
第三轮以4个元素为一个单位进行合并：[2,3,4,6],[1,5,7,9];[0,8],[]
合并完成之后变成： [1,2,3,4,5,6,7,9,0,8];
第四轮以8个元素为一个单位进行合并： [1,2,3,4,5,6,7,9],[0,8];
合并完成 。[0,1,2,3,4,5,6,7,8,9];
请给出java几种排序方法java常见的排序分为：
1 插入类排序
主要就是对于一个已经有序的序列中 ， 插入一个新的记录 。它包括：直接插入排序，折半插入排序和希尔排序
2 交换类排序
这类排序的核心就是每次比较都要“交换”，在每一趟排序都会两两发生一系列的“交换”排序，但是每一趟排序都会让一个记录排序到它的最终位置上 。它包括：起泡排序，快速排序
3 选择类排序
每一趟排序都从一系列数据中选择一个最大或最小的记录 ， 将它放置到第一个或最后一个为位置交换，只有在选择后才交换，比起交换类排序 ， 减少了交换记录的时间 。属于它的排序：简单选择排序，堆排序
4 归并类排序
将两个或两个以上的有序序列合并成一个新的序列
5 基数排序
主要基于多个关键字排序的 。
下面针对上面所述的算法 ， 讲解一些常用的java代码写的算法
二 插入类排序之直接插入排序
直接插入排序,一般对于已经有序的队列排序效果好 。
基本思想：每趟将一个待排序的关键字按照大小插入到已经排序好的位置上 。
算法思路，从后往前先找到要插入的位置 ， 如果小于则就交换，将元素向后移动，将要插入数据插入该位置即可 。时间复杂度为O(n2),空间复杂度为O(1)
package sort.algorithm;
public class DirectInsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
int temp, j;
for (int i = 1; idata.length; i++) {
temp = data[i];
j = i - 1;
// 每次比较都是对于已经有序的
while (j = 0data[j]temp) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
// 输出排序好的数据
for (int k = 0; kdata.length; k++) {
System.out.print(data[k] + "");
}
}
}
三 插入类排序之折半插入排序(二分法排序)

推荐阅读


上一篇：chatgpt是微软公司的吗，微软是什么车

下一篇：电脑黑屏键盘不正常怎么办，电脑黑屏键盘不管用