package net.yinzhao.code;
public class Sort {
/**
* 插入排序的基本思想为：首先寻找一个有序数列，然后将数组中的每个元素插入到该有序序列中，
* 则该数组序列即可变为有序数列。具体实施办法为，首选将第一个元素看作是一个有序序列，然后
* 从第二个元素开始遍历数组，将每个元素插入到从第一个元素到前一个元素的有序序列中，即可完
* 成排序。
* @param temp
*/
/*
public static void insertSort(int[] temp)
{
int length = temp.length;
for (int i = 1; i < length; i++) // 把第一个元素看作一个有序序列，从第二个元素开始遍历
{
int tempNo = temp[i];
for (int j = 0; j < i; j++)
{
if (tempNo < temp[j])
{
for (int k = i; k > j; k--) // 将其遍历数和比较数之间的数依次向后移动一位
temp[k] = temp[k-1];
temp[j] = tempNo;
}
}
}
}
*/
/**
* javaeye上看到的另外一种写法，不同之处是其与前边数字一个一个比较，然后一次一次逐渐移动。
*/
/*
public static void insertSort(int[] a)
{
for(int i = 1; i < a.length; i++)
{
int temp = a[i];
int j = i - 1;
while (j >= 0 && temp < a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
*/
/**
* 数据结构书上原版算法的java代码实现
*/
public static void insertSort(int[] temp)
{
int j = 0;
int length = temp.length;
int[] a = new int[length+1];
System.arraycopy(temp, 0, a, 1, length);
for(int i = 2; i < a.length; i++)
{
if(a[i] < a[i-1])
{
a[0] = a[i];
a[i] = a[i-1];
for (j = i - 2; a[i] < a[i-1]; j--)
{
a[j+1] = a[j];
}
a[j+1] = a[0];
}
}
for (int i = 1; i < a.length; i++)
{
System.out.println(a[i]);
}
}
/**
* 折半插入排序算法的java实现
* @param temp
*/
public static void bInsertSort(int[] temp)
{
int length = temp.length;
for (int i = 1; i < length; i++)
{
int tempVal = temp[i];
int low = 0;
int high = i - 1;
while (low <= high)
{
int middle = (low + high) / 2;
if (tempVal < temp[middle])
high = middle - 1;
else
low = middle + 1;
}
for (int j = i; j > high + 1; j--)
temp[j] = temp[j-1];
temp[high+1] = tempVal;
}
}
public static void buddleSort(int[] temp)
{
for (int i = 0; i < temp.length - 1; i++)
{
for (int j = i + 1; j < temp.length; j++)
{
if (temp[i] > temp[j])
{
int tempVal = temp[i];
temp[i] = temp[j];
temp[j] = tempVal;
}
}
}
}
public static void main(String[] args)
{
int a[] = {113, 3, 24, 24, 78, 96};
Sort.bInsertSort(a);
//Sort.insertSort(a);
//Sort.buddleSort(a);
for (int i = 0; i < a.length; i++)
{
System.out.println(a[i]);
}
}
}