学习java不可不知的几种算法
1、冒泡排序算法：编程语言算法中比较经典的算法。每个程序员都必须了解和会运用的。
程序算法基础
通过多次比较（相邻两个数）和交换来实现排序：
public class bubble {
public static void bubbleSort(int[] a) {
int temp;
for (int i = 1; i < a.length; i++) {
//将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < a.length - i; j++) {
if (a[j] > a[j + 1]) {
//交换相邻两个数
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
public static void main(String[] args) {
int[] mao= {213,123,342,543,12,67,98,320,421,4,15,54,27,34,17};
System.out.print("排序前的数组为：\n"); //输出排序前的数组
for(int i=0;i<mao.length;i++)
{
System.out.print(mao[i]+" ");
}
System.out.print("\n");
bubbleSort(mao); //排序操作
System.out.print("排序后的数组为：\n");
for(int i=0;i<mao.length;i++)
{
System.out.print(mao[i]+" "); //输出排序后的数组
}
System.out.print("\n");
}
}
2、直接插入排序
通过对未排序的数据执行逐个插入至合适的位置而完成排序
public class straight{
public static void straightInsertion(int[] arr) {
int current;//要插入的数
//从1开始第一次一个数不需要排序
for (int i = 1; i < arr.length; i++) {
current = arr[i];
int j = i - 1; //序列元素个数
//从后往前循环，将大于当前插入数的向后移动
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; //元素向后移动
j--;
}
arr[j + 1] = current; //找到位置，插入当前元素
}
}
}
3、快速选择排序
通过多次比较和交换来实现排序。首先设定一个分界值，将所有数值与分界值比较，左小右大，比较和交换数据值进而完成排序
public class quick{
static void quickSort(int[] arr,int left,int right) {
int f,t,rtemp,ltemp;
ltemp=left;
rtemp=right;
f=arr[(left+right)/2]; //分界值
while(ltemp<rtemp)
{
while(arr[ltemp]<f)
{
++ltemp;
}
while(arr[rtemp]>f)
{
--rtemp;
}
if(ltemp<=rtemp)
{
t=arr[ltemp];
arr[ltemp]=arr[rtemp];
arr[rtemp]=t;
rtemp--;
ltemp++;
}
}
if(left<rtemp)
{
quickSort(arr,left,ltemp-1); //递归调用
}
if(ltemp<right)
{
quickSort(arr,rtemp+1,right); //递归调用
}
}
}
4、希尔排序，又称Shell排序或缩小增量排序
(1)将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一对。
(2)一次循环使每一个序列对排好顺序。
(3)然后，再变为n/4个序列，再次排序。
(4)不断重复上述过程，随着序列减少最后变为一个，也就完成了整个排序。
代码如下：
public class shell{
static void shellSort(int[] a){
int h,temp,x=0;
for(int r=a.length/2;r>=1;r/= 2) //划组排序
{
for(int i=r;i<a.length;i++)
{
temp=a[i];
int j=i-r;
while(j>=0 && temp<a[j])
{
a[j+r]=a[j];
j-=r;
}
a[j+r]=temp;
}
x++;
}
}
}
5、堆排序：构造堆结构、堆排序输出来实现排序
public class pratice {
public static void heapSort(int a[],int n)
{
int i,j,h,k;
int t;
for(i=n/2-1;i>=0;i--) //将a[0,n-1]建成大根堆
{
while(2*i+1<n) //第i个结点有右子树
{
j=2*i+1 ;
if((j+1)<n)
{
if(a[j]<a[j+1]) //右左子树小于右子树，则需要比较右子树
j++; //序号增加1，指向右子树
}
if(a[i]<a[j]) //比较i与j为序号的数据
{
t=a[i]; //交换数据
a[i]=a[j];
a[j]=t;
i=j ; //堆被破坏，需要重新调整
}
else //比较左右子结点均大则堆未破坏，不再需要调整
{
break;
}
}
}
//输出构成的堆
System.out.print("原数据构成的堆:");
for(h=0;h<n;h++)
{
System.out.print(" "+a[h]); //输出
}
System.out.print("\n");
for(i=n-1;i>0;i--)
{
t=a[0]; //与第i个记录交换
a[0] =a[i];
a[i] =t;
k=0;
while(2*k+1<i) //第i个结点有右子树
{
j=2*k+1 ;
if((j+1)<i)
{
if(a[j]<a[j+1]) //右左子树小于右子树，则需要比较右子树
{
j++; //序号增加1，指向右子树
}
}
if(a[k]<a[j]) //比较i与j为序号的数据
{
t=a[k]; //交换数据
a[k]=a[j];
a[j]=t;
k=j ; //堆被破坏，需要重新调整
}
else //比较左右子结点均大则堆未破坏，不再需要调整
{
break;
}
}
}
}
}
学习编程语言，基础算法是必须掌握的。有句话说的好“算法是程序的灵魂”，作为程序员，掌握算法是成长的必经之路。
