以var a = [4,2,6,3,1,9,5,7,8,0];为例子。
1.希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。
function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i = k+gap; i < len; i=i+gap) { temp = arr[i]; tagArr.push(temp); for (j=i-gap; j >-1; j=j-gap) { if(arr[j]>temp){ arr[j+gap] = arr[j]; }else{ break; } } arr[j+gap] = temp; } console.log(tagArr,"gap:"+gap);//输出当前进行插入排序的数组。 console.log(arr);//输出此轮排序后的数组。 } gap = parseInt(gap/2); } return arr; }
过程输出：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序。
间隔为5：
[4, 9] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [2, 5] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [3, 8] "gap:5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "gap:5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 1] [4, 6, 0, 5, 8] "gap:2" [0, 2, 4, 3, 5, 9, 6, 7, 8, 1] [2, 3, 9, 7, 1] "gap:2" [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] [0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
间隔为2：
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1
排序后：
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
间隔为1：
排序后：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
2.快速排序。把一个数组以数组中的某个值为标记。比这个值小的放到数组的左边，比这个值得大的放到数组的右边。然后再递归 对左边和右边的数组进行同样的操作。直到排序完成。通常以数组的第一个值为标记。
代码:
function quickSort(arr){ var len = arr.length,leftArr=[],rightArr=[],tag; if(len<2){ return arr; } tag = arr[0]; for(i=1;i<len;i++){ if(arr[i]<=tag){ leftArr.push(arr[i]) }else{ rightArr.push(arr[i]); } } return quickSort(leftArr).concat(tag,quickSort(rightArr)); }
3.归并排序。把一系列排好序的子序列合并成一个大的完整有序序列。从最小的单位开始合并。然后再逐步合并合并好的有序数组。最终实现归并排序。
合并两个有序数组的方法：
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(gap<maxgap){ gap = Math.pow(2,n); if(gap<=maxgap){ gapArr.push(gap); } n++; } glen = gapArr.length; for (var i = 0; i < glen; i++) { gap = gapArr[i]; for (var j = 0; j < len; 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:2 left:6 right:3 left:1 right:9 left:5 right:7 left:8 right:0 left:2,4 right:3,6 left:1,9 right:5,7 left:0,8 right: left:2,3,4,6 right:1,5,7,9 left: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归并排序
你打开JDK的src.zip看一下Arrays类的原码，Arrays类的sort方法用的就是归并。
所以俺从来不费这个脑筋，吼吼~~
❸ 求java实现二路归并的程序
packagealgorithm;
publicclassMergeSort{
//privatestaticlongsum=0;
/**
*<pre>
*二路归并
*原理：将两个有序表合并和一个有序表
*</pre>
*
*@parama
*@params
*第一个有序表的起始下标
*@paramm
*第二个有序表的起始下标
*@paramt
*第二个有序表的结束小标
*
*/
privatestaticvoidmerge(int[]a,ints,intm,intt){
int[]tmp=newint[t-s+1];
inti=s,j=m,k=0;
while(i<m&&j<=t){
if(a[i]<=a[j]){
tmp[k]=a[i];
k++;
i++;
}else{
tmp[k]=a[j];
j++;
k++;
}
}
while(i<m){
tmp[k]=a[i];
i++;
k++;
}
while(j<=t){
tmp[k]=a[j];
j++;
k++;
}
System.array(tmp,0,a,s,tmp.length);
}
/**
*
*@parama
*@params
*@paramlen
*每次归并的有序集合的长度
*/
publicstaticvoidmergeSort(int[]a,ints,intlen){
intsize=a.length;
intmid=size/(len<<1);
intc=size&((len<<1)-1);
//-------归并到只剩一个有序集合的时候结束算法-------//
if(mid==0)
return;
//------进行一趟归并排序-------//
for(inti=0;i<mid;++i){
s=i*2*len;
merge(a,s,s+len,(len<<1)+s-1);
}
//-------将剩下的数和倒数一个有序集合归并-------//
if(c!=0)
merge(a,size-c-2*len,size-c,size-1);
//-------递归执行下一趟归并排序------//
mergeSort(a,0,2*len);
}
publicstaticvoidmain(String[]args){
int[]a=newint[]{4,3,6,1,2,5};
mergeSort(a,0,1);
for(inti=0;i<a.length;++i){
System.out.print(a[i]+"");
}
}
}
❹ java归并排序算法 在哪个包里
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.
public static void mergeSort(int[] a, int[] tmp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, tmp, left, mid);// 左排序
mergeSort(a, tmp, mid + 1, right);// 右排序
merge(a, tmp, left, mid + 1, right);// 左右合并
}
}
public static void merge(int[] a, int[] tmp, int left, int rightPos,
int right) {
int leftEnd = rightPos - 1;
int tmpPos = left;
int num = right - left + 1;
while (left <= leftEnd && rightPos <= right) {
if (a[left] < a[rightPos]) {
tmp[tmpPos++] = a[left++];
} else {
tmp[tmpPos++] = a[rightPos++];
}
}
while (left <= leftEnd) {
tmp[tmpPos++] = a[left++];
}
while (rightPos <= right) {
tmp[tmpPos++] = a[rightPos++];
}
for (int i = 0; i < num; i++, right--) {
a[right] = tmp[right];
}
}
❺ 归并排序java多次合并是怎么实现的就是那个merge方法是执行三次拆分后再三次归并吗
你好，其实是用了分治的思想，每次都进行拆分，直到可以比较为止，然后逐步合并，扩大排序集合！
❻ java 实现归并排序，我为什么错了！555……代码如下，没找到错误啊~~~求高手解答！！小女子不胜感激~
你是女生啊！哈哈！给我讲讲这算法的原理！我帮你看看代码！
❼ Java可以实现原地归并算法么
归并算法么，比如合并两个有序的数组成为一个新的有序数组
❽ java实现归并排序问题
public void mySort(int low,int high){
int lo=low;
int hi=high;
if (lo>=hi) {
return;
}else{
boolean flag=false;
while (lo<hi) {
if (arrs[lo]>arrs[hi]) {
int temp=arrs[lo];
arrs[lo]=arrs[hi];
arrs[hi]=temp;
flag=!flag;
}else{
if (flag) {
lo++;
}else{
hi--;
}
}
}
lo--;
hi++;
mySort(low,lo);
mySort(hi,high);
}
}
这里是复递归加二分法制(排序的方法) 希望能帮到你！！望~~点赞
❾ java实现归并排序问题，请大家帮我看代码错在哪里
在29行是数组越界。
❿ 关于归并排序的问题（java实现）
在计算机科学中，复归并排制序（通常拼写为mergesort）是一种有效的，通用的，基于比较的排序算法。 大多数实现产生稳定的排序，这意味着实现保留排序输出中相等元素的输入顺序。 合并排序是一种分而治之的算法，由John von Neumann于1945年发明。自1948年Goldstine和von Neumann的报告中出现了自下而上合并的详细描述和分析。下面小编将详细介绍该算法的原理及实现过程。
1/6 分步阅读
归并算法的具体步骤，归并排序函数如下：
MergeSort(arr[], l, r)
1、找到一个数组中中间的点将数组分成两个部分
middle m = (l+r)/2
2、递归调用MergeSort函数取第一部分
Call mergeSort(arr, l, m)
3、递归调用MergeSort函数取第二部分
Call mergeSort(arr, m+1, r)
4、使用merge函数融合排序步骤2和步骤3中的子数组
Call merge(arr, l, m, r)。