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]);
}
}
}