java 自己总结的算法

选择排序
原理：选择最小的元素并，将它和第一个位置上的元素交换。然后从，data[1],...data[n-1]中的元素，并将它放到第二个位置。
public static void selectionSort(int[] data)
{
int i, j;
int least;
int temp;
for (i = 0; i < data.length-1; i++)
{
for (j = i+1,least = i; j < data.length; j++)
{
if (data[j] < data[least])
{
least = j;
}
}
temp = data[i];
data[i]=data[least];
data[least]=temp;
}
for (i = 0; i < data.length; i++)
{
System.out.println("data[" + i + "]=" + data[i]);
}
}
节约了交换的次数。
插入排序
原理：从数组的前两个元素data[0]和data[1]着手。次序不对就进行交换
然后，扩展到前三个元素比较。data[1]和data[2]比较，交换位置。
public static void insertionSort(int[] data)
{
int temp;
int i, j;
for (i = 1; i < data.length; i++)
{
temp = data[i];
/*for (j = i; j > 0&&temp<data[j-1]; j--)
{
data[j] = data[j - 1];
}*/
for (j = i; j > 0; j--)
{
if(temp<data[j-1]){
data[j] = data[j - 1];
}else{
break;
}
}
data[j] = temp;
}
for (i = 0; i < data.length; i++)
{
System.out.println("data["+i+"]="+data[i]);
}
}
对于随机的数组，它的移动和比较此时更接近最坏情况。当数组的大小翻番，工作量是原来的四倍。
起泡排序
原理：自底向上扫描数组，如果找到相邻的两个元素顺序不对，将它们交换。最小的元素像气泡一样浮到数组的顶部。
public static void bubbleSort(int[] data){
int i,j;
int swap;
for(i=0;i<data.length;i++){
for(j=data.length-1;j>i;j--){
if(data[j]<data[j-1]){
swap = data[j];
data[j] = data[j-1];
data[j-1] = swap;
}
}
}
for (i = 0; i < data.length; i++)
{
System.out.println("data[" + i + "]=" + data[i]);
}
}
需要和数组的每个元素都执行交换，而不像选择排序可以跳过它们。
平均情况，起泡的比较次数是插入的两倍，和选择排序相同；移动次数和插入排序相同，是选择的n倍。

希尔排序
static void shellSort(int[] data)
{
int i, j, k, h, hCnt, increments[] = new int[20];
int temp;
for (h = 1, i = 0; h < data.length; i++)
{
increments[i] = h;
h = 3 * h + 1;
}
for (i--; i >= 0; i--)
{
h = increments[i];
for (hCnt = h; hCnt < 2 * h; hCnt++)
{
for (j=hCnt;j<data.length;)
{
temp = data[j];
k = j;
while(k-h>=0&&temp<data[k-h]){
data[k]=data[k-h];
k-=h;
}
data[k]=temp;
j+=h;
}
}
}
for (i = 0; i < data.length; i++)
{
System.out.println("data["+i+"]="+data[i]);
}
}