冒泡、选择就不写了。很常见
一：插入排序：
/**
* 插入排序
*/
public class P4_3 {
static void insertSort(int[] a){
int j,t;
/**
*
*/
for (int i = 0; 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;
} }
public static void main(String[] args){
int[] a=new int[]{3,4,2,6,2,5,1,9,28};
insertSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
} }
}
二：shell排序
/**
* shell sort
*/
public class P4_4 {
static void shellsort(int[] a){
for (int r = a.length/2; r >=1 ; r/=2) {
for (int i = r; i < a.length; i++) {
int t=a[i];
int j=i-r;
while (j>=0&&t<a[j]){
a[j+r]=a[j];
j=j-r;
}
a[j+r]=t;
}
}
}
public static void main(String[] args){
int[] a=new int[]{3,4,2,6,25,1,9,28};
shellsort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
三：快排
/**
* qicksort
*/
public class P4_5 {
static void qicksort(int[] a,int left,int right){
int f,t;
int rtemp,ltemp;
rtemp=right;
ltemp=left;
f=a[(right+left)/2];
while (ltemp<rtemp){
while (a[ltemp]<f){
ltemp++;
}
while (a[rtemp]>f){
rtemp--;
}
if (ltemp<rtemp){
//将左边大于分界值得数交换到邮编小于分界值得位置
t=a[rtemp];
a[rtemp]=a[ltemp];
a[ltemp]=t;
ltemp++;
rtemp--;
}
}
if (ltemp==rtemp){
ltemp++;
}
if (right>ltemp){
qicksort(a,rtemp+1,right);
}
if (rtemp>left){
qicksort(a,left,ltemp-1);
}
}
public static void main(String[] args){
int[] a=new int[]{3,4,2,6,25,1,9,73};
qicksort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
} }
}
四：堆排序
/**
* heapsort
*/
public class P4_6 {
static void heapsort(int[] a,int n){
int i,j,h,k;
int t;
//构建堆
for (i = n/2-1; i >=0 ; i--) {//找到当前最后一个节点的父节点
//存在右子树
while (2*i+1<n){
j=2*i+1;
if (j+1<n){
if (a[j]<a[j+1]){
j++;
}
}
//将最大的放在节点位置
if (a[i]<a[j]){
t=a[i];
a[i]=a[j];
a[j]=t;
i=j;
}else {
break;
}
}
}
//输出堆：
System.out.println("输出的堆：");
for (int l = 0; l < a.length; l++) {
System.out.print(a[l]);
System.out.print(" ");
System.out.println();
} //找出最大
for (i = n-1; i >=0 ; i--) {
//将找到的数据放在最右边
t=a[0];
a[0]=a[i];
a[i]=t;
k=0;
//k存在有子树
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;
}
} } }
public static void main(String[] args){
int[] a=new int[]{1,3,5,7,9,2,4,6,8,0};
heapsort(a,a.length);
for (int l = 0; l < a.length; l++) {
System.out.print(a[l]);
System.out.print(" ");
}
}
}
五：归并排序
/**
* mergesort
*/
public class P4_7 {
static void mergeone(int[] a,int[] b,int n,int len){
int i,j,k,s,e;
s=0;//开始位置
while ((s+len)<n){
//结束位置
e=s+2*len-1;
if (e>n){
e=n-1;
}
//合并
k=s;
i=s;
j=s+len;
while (i<(s+len)&&j<=e){
if (a[i]<a[j]){
b[k++]=a[i++];
}else {
b[k++]=a[j++];
}
}
//将未合并的数组复制
while (i<(s+len)){
b[k++]=a[i++];
}
while (j<=e){
b[k++]=a[j++];
}
s=e+1;//下一次开始的位置 }
//没有比较的合并过来
if (s<n){
for (;s<n;s++){
b[s]=a[s];
}
}
}
static void mergesort(int[] a,int n){
int[] p=new int[n];
int f,len;
len=1;
f=0;
while (len<n){
if (f==1){
mergeone(p,a,n,len);
}else {
mergeone(a,p,n,len);
}
len=2*len;
f=1-f;
}
if (f==1){
for (int h = 0; h < n; h++) {
a[h]=p[h];
}
}
}
public static void main(String[] args){
int[] a=new int[]{3,4,2,6,25,1,9,92,19};
mergesort(a,a.length);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}