把n个待排序的元素看成一个有序表和一个无序表。开始时有序表中只包含一个元素，即第一个元素，无序表中有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它插入到有序表中适当位置。
for(int i=1;i<arr.length;i++){ int insertVal=arr[i];//待插入的数 int insertIndex=i-1;//记录互换数下标（初始为待插入数前面一个数的下标） while(insertIndex>=0 && insertVal<arr[insertIndex]){ arr[insertIndex+1]=arr[insertIndex]; insertIndex--; } arr[insertIndex+1]=insertVal;//注意退出while循环多减了一次，这里加回来 }多次分组，对每个分组进行插入排序
for(int gap=arr.length/2;gap>0;gap/=2){ for(int i=gap;i<arr.length;i++){ for(int j=i-gap;j>=0;j-=gap){ if(arr[j]>arr[j+gap]{ temp=arr[j]; arr[j]=arr[j+gap]; arr[j+gap]=temp; } } } }第一次从arr[0]-arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换…
for(int i=0;i<arr.length-1;i++){ int minIndex=i;//记录该轮最小值坐标（最小值先假设为第一个数） int min=arr[i];//记录该轮最小值（最小值先假设为第一个数） for(int j=i+1;j<arr.length;j++){ if(arr[j]<min){ min=arr[j]; minIndex=j; } } if(minIndex!=i){//该轮循环结束，进行交换 arr[minIndex]=arr[i]; arr[i]=min; } }图解堆排序
堆： 基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
public static int[] PileSort(int[] arr){ //构建大顶堆，从下到上，从右到左 for(int i=arr.length/2-1;i>=0;i--){ bigTip(arr,i,arr.length); } for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//交换堆顶和最后一个元素 bigTip(arr,0,j);//继续调整为大顶堆 } return arr; } //从index开始到length构造大顶堆 public static void bigTip(int[] arr,int index,int length){ int temp=arr[index]; for(int i=2*index+1;i<length;i=i*2+1){ if(i+1<length&&arr[i]<arr[i+1]){ i++; } if(arr[i]>temp){ swap(arr,i,index); } } } //交换 public static void swap(int[] arr,int i,int index){ int temp=arr[i]; arr[i]=arr[index]; arr[index]=temp; }从前向后，依次比较相邻元素的值，若发现逆序则交换。
//从小到大排序 for(int i=0;i<arr.length-1;i++){ for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } }优化：如果在某趟排序中，没有发生一次交换，则已经有序，可以提前结束排序
//从小到大排序 boolean flag=true; for(int i=0;i<arr.length-1;i++){ for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; flag=false; } } if(flag){ break; }else{ flag=true; } }选择一个基准数，把比他大的放在右边，比他小的放在左边。再对左边和右边的数继续这个过程。
public static void quickSort(int[] arr,int low,int high){ if(low<high){ int index=getIndex(arr,low,high); quickSort(arr,low,index-1); quickSort(arr,index+1,high); } } public static int getIndex(int[] arr,int low,int high){ int temp=arr[low]; while(low<high){ while(low<high&&arr[high]>temp){ high--; } arr[low]=arr[high]; while(low<high&&arr[low]<=temp){ low++; } arr[high]=arr[low]; } arr[low]=temp; return low; }分治思想
public static void main(String[] args) { int[] a={6,5,3,1,8,7,2,4}; a=guiBing(a); System.out.println(Arrays.toString(a)); } public static int[] guiBing (int[] a) { int len=a.length; int[] result=new int[len]; for(int block=1;block<len;block*=2){ for(int start=0;start<len;start+=2*block){ //每组的起始、中间、结束下标 int low=start; int mid=(start+block)<len?(start+block):len; int high=(start+2*block)<len?(start+2*block):len; //两个块的起始和结束下标 int start1=low,end1=mid; int start2=mid,end2=high; //对两个block进行归并排序 while (start1<end1&&start2<end2){ result[low++]=a[start1]<a[start2]?a[start1++]:a[start2++]; } while (start1<end1){ result[low++]=a[start1++]; } while (start2<end2) { result[low++] = a[start2++]; } } a=result.clone(); } return a; }基数排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。
public class RadixSort { public static void main(String[] args) { int[] data = {51, 944, 1, 9, 57, 366, 79, 6, 1, 345};// 待排序数组 sort(data, 3); } /** * 从小到大排序 * @param data 待排序数组 * @param d 表示最大的数有多少位 */ public static void sort(int[] data, int d) { int n = 1; // 数组的第一维表示可能的余数0-9 int[][] bask = new int[10][data.length]; // 数组index[i]用来表示该位（个、十、百.......）是i的数的个数 int[] index = new int[10]; // i：控制键值排序依据在哪一位（个、十、百.......） for (int i = 0; i < d; i++) { for (int j = 0; j < data.length; j++) { int lsd = ((data[j] / n) % 10); bask[lsd][index[lsd]++] = data[j]; } int pos = 0; for (int j = 0; j < 10; j++) { for (int k = 0; k < index[j]; k++) { data[pos++] = bask[j][k]; } index[j] = 0; } n *= 10; } } }当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。
