–本文参考书目《java常用算法手册》赵志云，衡友跃，中国铁道出版社。
1、冒泡排序算法
冒泡排序思路就是交换排序，通过相邻数据的交换来达到排序的目的。对N个数据排序时，无论原数据有无数据，都需要进行N-1步的中间排序。
缺点：执行效率不是很高。
改进：在每次中间排序之后，比较一下数据是否已经按照顺序排列完成。若排列完成则退出排序过程，否则继续进行冒泡排序，这样对于数据比较有规则的，可以加速算法的执行过程。
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+1]=temp;
}
}
System.out.print("第"+i+"步排序结果：");
for(int k=0; k<a.length; k++){
System.out.print(" "+a[k]);
}
System.out.println();
}
}
2、选择排序算法
在每一步中选取最小值来重新排列，来达到排序目的。
流程：（1）首先从原始数组中选择最小的1个数据，将其和位于第一个位置的数据交换； （2）接着从剩下的n-1个数据中选择次小的1个元素，将其和第二个位置的数据交换； （3）然后，不断重复，直到最后两个数交换完成。至此，完成对原始数据从小到大的排序。
N个数据需要N-1步的中间排序。
void insertSort(int[] a){
int j,t,h;
for(int i=1; i<a.length; i++){
t = a[i];
j = i-1;
while(j>=0&&t<a[j]){
a[j+1] = a[j];
j--;
}
a[j+1]=t;
//输出每步排序结果
System.out.print("第"+i+"步排序结果：");
for(int k=0; k<a.length; k++){
System.out.print(" "+a[k]);
}
System.out.println();
}
}
4、Shell排序法（希尔排序/缩小增量排序）
void shellSort(int[] a){
int j,i,h;
int r,temp;
int x=0;
for(r = a.length/2; r>=1; r/=2){
for(i=r; i<a.length; i++){
temp = a[i];
j=i-r;
while(j>=0&&temp<a[j]){
a[j+r] = a[j];
j-=r;
}
a[j+r] = temp;
}
x++;
//输出每步排序结果
System.out.print("第"+x+"步排序结果：");
for(int k=0; k<a.length; k++){
System.out.print(" "+a[k]);
}
System.out.println();
}
}
5、快速排序法
与冒泡排序类似，都是基于交换排序思想。对冒泡排序的改进，有更高的执行效率。
（1）首先选取一个分界值，将数组分成左右两部分；
（2）将大于等于分界值的数据集中到数组右边，小于的集中到数组左边。此时，左边的各元素都小于分界值，右边的各元素都大于等于分界值。
（3）然后左边和右边的数据可以独立排序。对于左侧的数据又可以取分界值分为左右两部分，左边放置较小值，右边放置较大值。右侧数组数据类似处理。
（4）重复上述过程，通过递归，将左右两侧数据排好序后，整个数组的排序就完成了。
void quickSort(int[] arr, int left, int right){
int f,t;
int ltemp,rtemp; ltemp = left;
rtemp = right;
f = arr[(left+right)/2];
while(ltemp<rtemp){
while(arr[ltemp]<f){
++ltemp;
}
while(arr[rtemp]>f){
--ltemp;
}
if(ltemp<=rtemp){
t=arr[ltemp];
arr[ltemp]=arr[rtemp];
arr[rtemp]=t;
--rtemp;
++ltemp;
}
}
if(ltemp==rtemp){
ltemp++;
}
if(left<rtemp){
quickSort(arr,left,ltemp-1);
}
if(ltemp<rifht){
quickSort(arr,rtemp+1,rifht);
}
}
6、堆排序法
堆排序法是基于选择排序思想的，利用堆结构和二叉树的一些性质来完成数据排序。
A 什么是堆结构？
堆结构是一种树结构，准确的说是一个完全二叉树。
树中每个结点对应原始数据的一个记录，每个结点满足如下条件：
*若按照从小到大顺序排序，要求非叶结点数据>=其左右子结点的数据；
*若按照从大到小顺序排序，要求非叶结点数据<=其左右子结点的数据；
(对结点的左子结点和右子结点大小无要求。)
B 堆排序过程
反复两个步骤：构造堆结构和堆排序输出。
void heapSort(int[] a, int n){
int i,j,h,k;
int t;
for(i=n/2-1; i>=0; i--){ //将a[0]--a[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];
a[0]=a[i];
a[i]=t;
k=0;
while(2*k+1<i){
j=2*k+1;
if((j+1)<i){
if(a[j]<a[j+1]){
j++;
}
}
if(a[k]<a[j]){
t=a[k];
a[k]=a[j];
a[j]=t;
k=j;
}
else{
break;
}
}
System.out.print("第"+(n-i)+"步排序结果：");
for(h=0;h<n;h++){
System.out.print(" "+a[h]);
}
System.out.println();
}
}
排序算法的效率：
