用java實作的疊代和遞歸插入排序

下面使用一個java實作的疊代版的遞歸版的插入排序。

package sort;

import java.util.Date;

import java.util.Random;

/*

* 插入排序

*/

public class InsertSort{

public static void main(String args[])

{

int len = 20;

Date date = new Date();

Random random = new Random(date.getSeconds());

int data[]=new int[len];

for(int i = 0; i < len; i++)

{

data[i]=(int)(random.nextFloat()*100+1);

}

show(data);

insertSort(data,data.length);

show(data);

System.out.println(binarySearch(data,1,data.length,55));

System.out.println(binarySearch2(data,55));

insertSortDesc(data);

show(data);

System.out.println(binarySearch(data,1,data.length,55));

System.out.println(binarySearch2(data,55));

}

/*

* 插入排序核心

*/

private static void insertSortDesc(int[] data)

{

int length = data.length;

for(int i = 1; i < length; i++)

{

int temp = data[i];

int j = i-1;

while(j >= 0 && data[j] < temp)

{

data[j+1] = data[j];

j--;

}

data[j+1] = temp;

}

}

private static void insertSortAsc(int[] data)

{

int length = data.length;

for(int i = 1; i < length; i++)

{

int temp = data[i];

int j = i-1;

while(j >= 0 && data[j] > temp)

{

data[j+1] = data[j];

j--;

}

data[j+1] = temp;

}

}

private static void show(int[] data)

{

System.out.println("========================");

for(int i = 0; i < data.length; i++)

{

System.out.print(data[i] + " ");

}

System.out.println();

System.out.println("========================");

}

/*

* 使用遞歸實作的插入排序算法

*/

private static void insertSort(int[] data,int n)

{

if(n>1)

{

insertSort(data,n-1);

merge(data,n-1,n);

}

}

private static void merge(int[] data,int end,int n)

{

int temp=data[n-1];

int i;

for( i=end-1; i>=0; i--)

{

if(data[i]>temp)

data[i+1]=data[i];

else

break;

}

data[i+1]=temp;

}

/*

* 遞歸版的二分查找算法,隻能是按照升序排列的數組

*/

private static int binarySearch(int[] data,int start,int end,int value)

{

if(end>=start)

{

int pos=(start+end)/2;

if(value==data[pos-1])

return pos;

else if(value>data[pos-1])

return binarySearch(data,pos+1,end,value);

else

return binarySearch(data,start,pos-1,value);

}

return -1;

}

/*

* 疊代版二分查找算法，隻能查找按照升序排列的數組

*/

private static int binarySearch2(int[] data,int value)

{

int start = 0 ;

int end = data.length-1;

int mid;

while(end>=start)

{

mid=(end+start)/2;

if(value>data[mid])

start=mid+1;

else if(value<data[mid])

end=mid-1;

else

return mid+1;

}

return -1;

}

}