用java对常用内部排序算法的实现。
对冒泡排序，简单选择排序，直接插入排序，希尔排序，归并排序的简单实现（缺少快速排序和堆排序，改天补充），只是对其排序原理的理解，并没有做算法的优化。
冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
// 冒泡排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
private static int[] BubbleSort(int[] is) {
for (int i = 0; i < is.length; i++) {
boolean isChanged = true;
for (int j = i + 1; j < is.length; j++) {
if (is[i] > is[j]) {
int tmp = is[i];
is[i] = is[j];
is[j] = tmp;
isChanged = false;
}
}
if (isChanged == true)
break;
}
return is;
}
简单选择排序
选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
//简单选择排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
private static int[] SelectSort(int[] is){
for(int i=0;i<is.length;i++){
boolean isChanged = true;
for(int j=i+1;j<is.length;j++){
if(is[j]<is[i]){
int tmp=is[i];
is[i]=is[j];
is[j]=tmp;
isChanged = false;
}
}
if(isChanged == true)
break;
}
return is;
}
直接插入排序
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
//直接插入排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
private static int[] InsertionSort(int[] is){
for(int i=1;i<is.length;i++){
boolean isChanged=true;
for(int j=i;j>0;j--){
if(is[j]<is[j-1]){
int tmp = is[j];
is[j] = is[j-1];
is[j-1] = tmp;
isChanged = false;
}
}
if (isChanged == true)
break;
}
return is;
}
希尔排序
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
//希尔排序。
private static int[] ShellSort(int[] is){
for(int step=is.length/2;step>0;step=step/2){//设置排序的步长，默认都是从n/2开始
//直接插入排序
for(int j=0;j<step;j++){
for(int k=j+step;k<is.length;k+=step){
if(is[k]<is[k-step]){
int tmp = is[k];
int t=k-step;
while(t>=0&&is[t]>tmp){
is[t+step]=is[t];
t-=step;
}
is[t+step] = tmp;
}
}
}
}
return is;
}
归并排序
归并排序，是创建在归并操作上的一种有效的排序算法。
//归并排序,采用递归方式
private static int[] MergeSort(int[] is){
if(is.length==1){
return is;
}
int half=is.length/2;
int[] ary1=new int[half];
int[] ary2=new int[is.length-half];
System.arraycopy(is, 0, ary1, 0, ary1.length);
System.arraycopy(is, half, ary2, 0, ary2.length);
ary1=MergeSort(ary1);
ary2=MergeSort(ary2);
return Merge(ary1, ary2);
}
//合并两个有序数组，并且合并后的数组也有顺序
private static int[] Merge(int[] A,int[] B){
int[] tmp=new int[A.length+B.length];
int i=0,j=0,k=0;
while(i<A.length&&j<B.length){
if(A[i]<B[j]){
tmp[k++]=A[i++];
}else{
tmp[k++]=B[j++];
}
}
while(i<A.length){
tmp[k++]=A[i++];
}
while(j<B.length){
tmp[k++]=B[j++];
}
return tmp;
}
