java实现：插入排序、选者排序、希尔排序

选择排序

public class 选择排序 { public static void main(String[] args) { int[] arr=new int[]{3,2,7,1,9,5,4,8,3}; for (int i=0;i<arr.length;i++){ int min=arr[i];//重新给min赋值，这一步必不可少 int k=0; for (int n=i;n<arr.length;n++){ if (arr[n]<=min){ min=arr[n];//记录最小的值 k=n;//交换最小值的下标索引 } } //交换最小的值和第i个元素位置 arr[k]=arr[i]; arr[i]=min; } for(int i:arr) System.out.println(i+" "); } }

插入排序

可将插入排序对比希尔排序

public class 插入排序 { public static void main(String[] args) { int[] arr = new int[]{1, 2, 5, 8, 6, 4, 7}; for (int i = 0; i < arr.length-1; i++) { int value=arr[i+1];//待插入元素存到value int k = i; //当k<0时退出循环，说明k时最小元素的索引值 //并且当arr[k]<=value时退出循环，证明k是比value小的元素的索引值 for (;k>=0&&arr[k]>value;k--){ //元素往后挪 arr[k+1]=arr[k]; } //将待插入元素放入正确位置 arr[k+1]=value; } for (int i:arr){ System.out.print(i+" "); } } }

希尔排序（插入排序的改进）

对比插入排序进行学习 arr.length个小的插入排序，效率比插入排序快

public class 希尔排序 { public static void main(String[] args) { int[] arr = new int[]{1, 2, 5, 8, 6, 4, 7}; shellSort(arr); for (int i:arr){ System.out.print(i+" "); } } public static void shellSort(int[] arr){ //不断地缩小增量 for (int interval=arr.length/2;interval>0;interval=interval/2){ //增量为interval的插入排序 //每一次i增量为interval for (int i = interval; i < arr.length; i+=interval) { int value=arr[i];//待插入元素存到value int k = i-interval; //当k<0时退出循环，说明k时最小元素的索引值 //并且当arr[k]<=value时退出循环，证明k是比value小的元素的索引值 for (;k>=0&&arr[k]>value;k-=interval){ //元素往后挪 arr[k+interval]=arr[k]; } //将待插入元素放入正确位置 arr[k+interval]=value; } } } }