public static void main(String[] args) {
int a[]={1,8,2,6,5,4}
int[] arr= sort(a,0,a.length-1)
for(int rr=0rr<=5rr++)
System.out.printf("%d\t", arr[rr])
System.out.printf("\n")
}
public static int[] sort(int[] a,int low,int high){
int mid = (low+high)/2
if(low<high){
sort(a,low,mid)
sort(a,mid+1,high)
//左右归并
merge(a,low,mid,high)
}
return a
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1]
int i= low
int j = mid+1
int k=0
// 把较小的数先移到新数组中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++]
}else{
temp[k++] = a[j++]
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++] = a[i++]
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++] = a[j++]
}
// 把新数组中的数覆盖nums数组
for(int x=0x<temp.lengthx++){
a[x+low] = temp[x]
}
}
2、简单的数组排序
public static void main(String[] args) {
int a[]={1,8,2,6,5,4}
Arrays.sort(a)
for(int rr=0rr<=5rr++)
System.out.printf("%d\t", a[rr])
System.out.printf("\n")
}
以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),tempwhile(gap>0){ for (var k = 0k <gapk++) { var tagArr = []tagArr.push(arr[k]) for (i = k+gapi <leni=i+gap) { temp = arr[i] tagArr.push(temp) for (j=i-gapj >-1j=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=[],tagif(len<2){ return arr} tag = arr[0]for(i=1i<leni++){ 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,nwhile(gap<maxgap){ gap = Math.pow(2,n) if(gap<=maxgap){ gapArr.push(gap) } n++} glen = gapArr.lengthfor (var i = 0i <gleni++) { gap = gapArr[i] for (var j = 0j <lenj=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,31,95,78,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]
百度文库找了一个http://wenku.baidu.com/view/332fd62d453610661ed9f414.html四、合并排序 1、基本思想
合并排序的基本操作是：首先将待排序序列划分为两个长度相等的子序列；然后分别对两个子序列进行归并排序，得到两个有序的子序列；最后将两个有序的子序列合并成一个有序数列。
MergeSort(A[2*n]) {
divide A[2*n] into A[1,……,n],A[n-1,……,2*n]//划分 MergeSort(A[1,……,n])//归并排序前半个子序列
MergeSort(A[[n-1,……,2*n])//归并排序后半个子序列 Merge//合并 }
2、算法复杂度分析
合并步的时间复杂度为O(n)。合并排序算法的时间复杂度为O(nlog2n)。
3、编程实现
public int[] MergeSort(int[] A, int[] tempA, int s, int t){
//如果序列中有一个以上的元素，即s<t则进行排序
if(s <t){
int center = (s + t) / 2
MergeSort(A, tempA, s, center)
//归并排序前半个子序列
MergeSort(A, tempA, center + 1, t)
//归并排序后半个子序列
Merge(A,tempA, s, center, t)
//合并
}
return tempA
}
public int[] Merge(int[] A, int[] tempA, int s, int m, int t){int n = t- s + 1
//n为数据总个数
int i=sj=m+1k=s
while(i <= m&&j <= t){
//取A[i]和A[j]中较小者放入tempA[k]
if(A[i]<=A[j]){
tempA[k++] = A[i++] }
else{
tempA[k++] = A[j++] }}
if(i<=m) while(i<=m)
tempA[k++]=A[i++]//处理前一个子序列
else while(j<=t)
tempA[k++]=A[j++]//处理后一个子序列
return tempA
}
