选择排序：每次在未排序部分选择一个最小的放到前面，并把最小值的标记向后移动一位 特点： 1. 运行时间和输入无关（但是并没有用，因为即使输入时是有序的，仍然会进行遍历与比较，复杂度不变 2. 数据移动量是最少的，因为每次只移动一个元素，移动N次
时间复杂度：最坏n^2,最优n^2平均n^2 缺点：未排序部分若有序，仍会继续遍历
public static void select(int[]arr){ for(int i=0;i<arr.length;i++){ int min = i;//每次假设未排序部分首位为最小值 for(int j=i;j<arr.length;j++){ if(arr[j] < arr[min]){//然后在剩余部分中找出最小值 min = j; } } //将剩余部分的最小值放到i上（即排序部分的末尾） int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } }插入排序：即把未排序部分的第一个元素拿出来，插入到已排序的部分。将插入位置后面的元素后移。类似于从左往右整理扑克牌 特点： 1. 与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。 2. 数组已经相对有序时，时间会减少很多（整理扑克牌时如果接近有序，也不用花太多时间） 3. 由于插入排序插入时会影响到后续元素的位置，因此用数组来实现会有大量的时间用于元素位置移动。(可以尝试用链表改进)
最坏：n^2 最优 n 平均n^2
public static void insertSort(int arr[]){ for(int i=1;i<arr.length;i++){//插入第i个数 for(int j=i;j>0;j--){ //从第i-1开始往前比较，不停的往前移动 if(arr[j]<arr[j-1]){ int temp = arr[j]; arr[j]=arr[j-1]; arr[j-1] = temp; } } } }归并排序:采用分治思想，将一个数组的排序转化为若干小数组的排序，然后将结果归并起来 采用分治思想算法复杂度始终是nlogn
public static void merge(int arr[]){ mergeSort(0,arr.length-1,arr); } public static void mergeSort(int lo,int hi,int arr[]){ if(lo>=hi) return; int mid = lo + (hi-lo)/2; mergeSort(lo,mid,arr); mergeSort(mid+1,hi,arr); merge(lo,mid,hi,arr); } public static void merge(int lo,int mid,int hi,int[] arr){ int[] temp = new int[arr.length]; for(int i=lo;i<=hi;i++){ temp[i] = arr[i]; } int j = mid+1; int k = lo; int f = lo; while(f <= hi){ if(k > mid) arr[f++] = temp[j++]; else if(j > hi) arr[f++] = temp[k++]; else if(temp[k] < temp[j]) arr[f++] = temp[k++]; else arr[f++] = temp[j++]; } }快速排序：快速排序也是采用分治思想的排序，快速排序的思路是选取一个随机元素一般是a[lo]（待排部分首位），
然后在分别从lo->hi,hi->lo进行扫描，从左边元素找到一个比a[lo]大的，在右侧找到一个比a[lo]小的，进行位置交换，直到左右扫描的标记相遇
如果i>=j ，说明 i 左侧元素一定比a[lo]小了，并且j右侧元素一定比a[lo]大了此时把a[lo]放到a[i]与a[j]之间即可
顺序或逆序的数组进行快排的性能十分之低，所以在进行操作之前应该先对其进行一个打乱操作（此处未打乱）
public static void quick(int []arr){ quickSort(0,arr.length-1,arr); } public static void quickSort(int lo,int hi,int[] arr){ if(lo>=hi) return; int a = partion(lo,hi,arr); quickSort(lo,a-1,arr); quickSort(a+1,hi,arr); } public static int partion(int lo,int hi,int[]arr){ int i=lo+1; int j=hi; int part=arr[lo]; while(i<=j){ while(arr[i]<part){ if(i==hi) break; i++; } while(arr[j]>part){ if(i==lo) break; j--; } if(i>=j) break; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } arr[lo] = arr[j]; arr[j] = part; return j; }