存储结构
邻接矩阵（Adjacency Matrix）
邻接链表（Adjacency List）
十字链表（Orthogonal List）
算法
插入、冒泡、选择排序、希尔排序
public class InsertSort {
@Test
public void testInsertSort()
{
int[] array={4,6,7,3,9,8,5,2};
this.insSort(array);
for(int i=0;i<array.length;i++)
{
System.out.println(array[i]);
}
}
/**
* 插入排序
* 1、将第一个元素标记为已排序
* 2、遍历每个没有排过序的元素
* 2.1、提取元素x，如果提取的元素x < 排序过的元素则交换（循环一直跳出）
* @param array
*/
private void insSort(int[] array)
{
for(int i=1;i<array.length;i++)
{
int j=i;
while (j > 0 && array[j] < array[j - 1]) {
int tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
j--;
}
}
}
}
/**
* 冒泡
* 对相邻元素进行两两比较，顺序相反，则交换
* @param array
*/
private void bubbleSort(int[] array)
{
for(int i=0;i<array.length-1;i++)
{
for(int j=0;j<array.length-1-i;j++)
{
if(array[j]>array[j+1])
{
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
}
}
}
}
/**
* 每一趟从待排序的数字中选择最小的放在已排序内容的最后，直到全部内容排序完成
* @param array
*/
private void selectionSort(int[] array){
for(int i=0;i<array.length-1;i++)
{
int min=i;
for(int j=i+1;j<array.length;j++)
{
if(array[j]<array[min])
{
min=j;
}
}
if(min!=i)
{
int tmp=array[min];
array[min]=array[i];
array[i]=tmp;
}
}
}
/**
* 希尔排序
* @param array
*/
private void shellSort(int[] array)
{
//增量gap，并逐步缩小增量
for(int gap=array.length/2;gap>0;gap/=2){
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(int i=gap;i<array.length;i++)
{
int j=i;
while (j-gap>=0 && array[j]<array[j-gap]){
//移动法
swap(array,j,j-gap);
j-=gap;
}
}
}
}
private void swap(int[] array,int a,int b)
{
int tmp=array[a];
array[a]=array[b];
array[b]=tmp;
}