选择排序
package day07;
public class try_1 {
public static void main(String[] args) {
int array[] = new int[]{12,14,2365,57,79,35};
int x;
int y;
int i;
int temp;
for(x=0;x<array.length-1;x++)
{
for(y=x+1;y<array.length;y++)
{
if(array[y]<array[x])
{
temp=array[y];
array[y]=array[x];
array[x]=temp;
}
}
}
for(i=0;i<array.length;i++)
{
System.err.print(array[i]+" ");
}
}
}
12 14 35 57 79 2365
从选择排序的思想或者是上面的代码中，我们都不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。
选择最大或者最小的那个，与前面按顺序排好的后面一位交换位置。时间复杂度为o(n2),空间复杂度为o(1),是不稳定排序
冒泡排序
for(x=0;x<array.length-1;x++)
{
for(y=0;y<array.length-1-x;y++)
{
if(array[y]>array[y+1])
{temp=array[y];
array[y]=array[y+1];
array[y+1]=temp;
}}
}
大的往后沉，逐轮比较元素递减。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。是稳定排序，最好的情况时间复杂度为o(n)最坏的情况时间复杂度为o(n2).
用Arrays.sort()函数进行排序也是非常快的，一般在开发的时候就不用再自己写排序函数，用java给封装好的函数就可以
二分查找
二分查找作为O(log(n))时间复杂度的查找算法得到了广泛的使用。
1.在已排序的数组中查找特定的元素。或者是满足条件的第一个元素
2.数学常用的求解方程的解，也是数学家所指的对半查找。
3.程序调试中用来定位错误语句
4….
package day07;
import java.util.Arrays;
public class try_3 {
public static void main(String[] args) {
int array[] = new int[]{12,14,2365,57,79,35};
Arrays.sort(array);
int key=79;
int min=0;
int max=array.length-1;
while(min<=max)
{ int mid=(min+max)>>1;
if(key>array[mid])
min=mid+1;
else if(key<array[mid])
max=mid-1;
else
{
System.out.println("bingo~~~ "+array[mid]);
break;
}
}
}
}
int mid=(min+max)/2; 一定写在循环的里面，不然mid位置不变就会出现死循环。
min=mid+1 max = mid-1千万不要写成 min=mid max=mid
在最后找到结果的时候一定要注意return 或者break不然会死循环
记得是while(min<=max)而不是while(min<max)
二分算法是我们经常会用到的一个算法。它是分治法的一个应用。不过，虽然他写起来貌似很简单，但是却很容易写错。
关于溢出问题：师哥，这个问题，举个特例：比如short类型的mid 假如min=65534,max=65535，那么用mid = (min+max)>>1一加肯定就超了，但是用mid = min+(max-min)>>1就不会超.但是要注意的是在java当中是不能连加的，也就是说不能做连续运算。所以如果想使用mid = min+(max-min)>>1，那么可以定义一个中间变量，int ca = (max-min)>>1; int mid = ca+min;一般不会溢出，所以用（min+max）>>1足矣。
数组逆转
将一个数组逆转，你会怎么想？用链表？线性表？如果简单点想的话：如果是一个有序的数组，那么直接头尾交换，然后指向头和尾的指针分别向中间移动，如果不是一个有序的数组那么先排序，然后指向头和尾的指针分别向中间移动。
package day07;
public class try_9 {
public static void main(String[] args) {
int[] arr = {1,3,4,7,8,9,20,33,33,48};
change(arr);
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void change(int[]a)
{
int head = 0;
int end = a.length-1;
while((a[head]<a[end])&&(head<end))
{
int temp = a[head];
a[head]= a[end];
a[end]= temp;
head+=1;
end-=1;
}
}
}
48 33 33 20 9 8 7 4 3 1
也就是说：
1、反转其实就是头尾角标的元素进行位置的置换
2、然后让头角标自增，尾角标自减，再继续位置转换
3、依次类推，直到头角标和尾角标相等或者头角标大于尾角标的时候结束
查表法
关于十进制转十六进制的示例：
package day4; import java.lang.reflect.Array; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { toHex(26); } public static void toHex(int num) { char[]ch = new char[8]; int pos = ch.length; while(num!=0) { pos--; int temp = num&15;//因为四个二进制位是一个十六进制位，15是二进制的0000000000001111 if(temp>9) { ch[pos]=(char)(temp-10+'A'); } else ch[pos]=(char)(temp+'0');//将字符转化成数字之后再转成字符 num=num>>>4;//无符号右移，补0 } System.out.println(pos); for(int x = pos;x<ch.length;x++) System.out.print(ch[x]); System.out.println(); } }
6
1A
关于查表法
由上面的进制转换程序我们可以发现，十六进制中一共有十六个元素，而且没通过&15获取的数字都在15之内，都有对应的十六进制元素。而且元素对应的数字正好有规律的，而且符合了数组这种容器的特点——角标，那么可以讲十六进制的元素都存储到数组当中，将每次&15的结果作为角标去查询这个数组，就可以取到十六进制对应的元素。
那么什么时候使用查表法，当元素很多，而且这些元素与数字有对应的关系，而且这些数字都有角标的规律，这时优先考虑查表法。
package day07; public class try_10 { public static void main(String[] args) { transer(26,15,4); System.out.println(); transer(26,1,1); System.out.println(); transer(26,7,3); } public static void transer(int num,int offset,int move) { char[]array = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'} ; char[]ch = new char[32]; int pos = ch.length; while(num!=0) { pos--; int temp = num&offset; ch[pos] =array[temp]; num=num>>>move; } System.out.println(pos); for(int x = pos;x<ch.length;x++) System.out.print(ch[x]); System.out.println(); } }
30
1A
27
11010
30
32
实现了由十进制转换成其他进制的转换过程。
transer(26,15,4);将十进制的26转换成十六进制， 参数分别是转换数字，&，换算位数。四个二进制位是一个十六进制位，00001111是十进制中的15
transer(26,1,1); 将十进制的26转换成二进制 00000001是十进制中的1
transer(26,7,3); 将十进制的26转换成八进制 三个二进制位是一个八进制位，00000111是十进制中的7