课本上经典的排序算法复习
参考http://blog.csdn.net/hkx1n/article/details/3922249
冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： 复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。直接插入排序：O(n*n)
选择排序：O(n*n)
快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
归并排序：log2(n)*n
堆排序：log2(n)*n
希尔排序：算法的复杂度为n的1.2次幂
下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。
B是真数(0-9)，
R是基数(个十百)
ShellO(n^(3/2))O(ns) 1<s<2不稳定O(1)s是所选分组快速O(nlogn)O(n2)不稳定O(nlogn)n大时较好归并O(nlogn)O(nlogn)稳定O(1)n大时较好堆O(nlogn)O(nlogn)不稳定O(1)n大时较好public class Px {
public static void main(String[] args) {
int[] a = new int[]{9,8,7,6,5,4,3,2,1};
Px p = new Px();
p.maopao(a);
}
//插入排序理念就是从数组前二个开始，如果第一个大于第二个，就将第二个插入第一个位置，第一个放入第二个位置
//然后是数组的第三个，在前三个中插入，如果第三个小鱼第二个，大于第一个，就插入在第二个位置，
//依次类推，第四个，第五个，一直到数组结束。
public void charupx(int[] args){
for(int i=1;i<args.length;i++){
int j = i-1;
int t = args[i];
while(j>=0&&args[j]>t){
args[j+1]=args[j];
j--;
}
//beacause j已经减了
args[j+1] = t;
System.out.println("=========="+i);
for(int k=0;k<args.length;k++){
System.out.print(args[k]+" ");
}
}
}
/**
* 冒泡算法的理念就是，每一次都将最大或最小的数放在最开始或最后
* 将最大的放在最后，次大的放在次后，第三大的放在倒数第三
* 这样在中间可以减少比较的次数，就是最后的都是最大，次大，倒数第三大...，不需要比较
* @param args
*/
public void maopao(int[] args){
for(int i=0;i<args.length;i++){
int j=0;
for(j=0;j<args.length-i-1;j++){
if(args[j]>args[j+1]){
int temp = args[j];
args[j] = args[j+1];
args[j+1] = temp;
}
}
System.out.println("=========="+i);
for(int k=0;k<args.length;k++){
System.out.print(args[k]+" ");
}
}
}
/**
* 理念就是选择最小的放在第一个位置，次小的第二个位置，第三小的放在第三位置
* @param a
*/
public void xuanzhe(int[] a){
for(int i=0;i<a.length;i++){
int temp;
int index = 0;
temp = a[i];
for(int j=i;j<a.length;j++){
if(temp>a[j]){
temp = a[j];
index = j;
}
}
a[index] = a[i];
a[i] = temp;
System.out.println("=========="+i);
for(int k=0;k<a.length;k++){
System.out.print(a[k]+" ");
}
}
}
}