简单排序算法(二)
ects[in-1];
--in;
}
objects[in]=temp;
}
return objects;
}
public static void main(String[] args) {
int[] a={1,3,2,4,0};
InsertionSort insertionSort =new InsertionSort();
a=insertionSort.getResult(a);
System.out.println(Arrays.toString(a));
}
}
希尔排序：
[java]
import java.util.Arrays;
public class Shell_Sort {
/*
* @them 希尔排序
* 是对插入排序的改进，先将整个分成若干个，再在若干个里分别进行插入排序，然后再整体进行一次插入排序。
* 时间复杂度：O（NlogN）~O（N*N）
*/
public int[] shellSort(int[] theArray)
{
int inner=0,outer=0;
int nElems=theArray.length;
long temp=0;
int h=1; //find initial value of h
while(h<=nElems/3) //1,4,13,40,121,...
h=h*3+1;
while(h>0)
{
//当间隔h>1时，进行小部分插入排序；当间隔h=1时，进行整体插入排序
for(outer=h;outer
{
temp=theArray[outer];
inner=outer;
while(inner>h-1&&theArray[inner-h]>=temp)
{
theArray[inner]=theArray[inner-h];
inner-=h;
}
theArray[inner]=(int) temp;
}
h=(h-1)/3; // 间隔从大减小，一直减小到1，此时因为间隔为1，就相当于是做整体的插入排序
}
return theArray;
}
public static void main(String[] args) {
int[] a={1,4,2,7,3,12,44,21,55,32,11};
Shell_Sort g=new Shell_Sort();
a=g.shellSort(a);
System.out.println(Arrays.toString(a));
}
}
选择排序：
[java]
import java.util.Arrays;
public class SelectSort {
/**
* @param args
* @author mayi
* @them 选择排序
* 假设有 N 条数据，则暂且标记第 0 个数据为 MIN（最小），使用 OUT 标记最左
边未排序的数据，然后使用 IN 标记第 1 个数据，依次与 MIN 进行比较，如果比
MIN 小，则将该数据标记为 MIN，当第一轮比较完后，最终的 MIN 与 OUT 标记
数据交换，依次类推；
选择排序的效率：O（N*N），比较 N*N/2，交换
较，比较次数没有明显改变，但交换次数明显减少了很多；
*/
public int[] getResult(int[] objects){
int in,out,min,temp;
//如果数组为null，直接返回
if(objects==null||objects.length==0){
return objects;
}
for(out=0;out
min =out;
//寻找最小值
for(in=out+1;in
if(objects[min]>objects[in]){
min = in;
}
}
//与out交换位置
temp =objects[out];
objects[out]=objects[min];
objects[min]=temp;
}
return objects;
}
public static void main(String[] args) {
SelectSort ss = new SelectSort();
int[] a ={2,5,4,1};
a=ss.getResult(a);
System.out.println(Arrays.toString(a));
}
}