最近经常调用api中的排序算法，很少自己写了，有时候也只写写快速排序这些比较快的排序，然而刚开始学排序时用的一些基本的排序算法却有点忘了
正好今天Java老师让我们每个人写个选择排序热热手，趁这个机会再来复习下一些基本的排序好了。
一、冒泡排序（稳定排序）
学编程接触到的第一个排序算法，基本思路就是，给定一个无序数组a0、a1、a2、a3....an;
通过从左到右相邻的元素两两比较，把最大或者最下的数依次放到数组的右边，最后得到有序的序列
public static void maoPao(int[] arr){ //遍历数组长度（要冒多少个泡）,i从1开始（从0开始也没错） for(int i=1;i<arr.length;i++){ //每冒一次泡，需要比较的元素就少一个，所以是arr.length-i for(int j=0;j<arr.length-i;j++){ //如果满足条件（前面的大于后面的或者后面的大于前面的都行） //交换两者 if(arr[j+1]<arr[j]){ //这里交换没有用中间变量 arr[j] = arr[j] + arr[j+1]; arr[j+1] = arr[j] - arr[j+1]; arr[j] = arr[j] - arr[j+1]; } } } }
二、选择排序（不稳定排序）
给定一个无序的序列a0、a1、a2、a3、a4。。。
下标从小到大遍历数组，每次遍历找到最小的元素并记录下标，如果遍历完之后发现记录的下标不是初始下标则交换
public static void xuanZe(int[] arr){ for(int i=0;i<arr.length-1;i++){ int min = i; for(int j=i+1;j<arr.length;j++){//找到最小的元素，记录下标 if(arr[j]<arr[min]) min = j; } if(min!=i){//如果不等于初始状态下标，就交换 arr[i] = arr[i] + arr[min]; arr[min] = arr[i] - arr[min]; arr[i] = arr[i] - arr[min]; } } }
三、插入排序（稳定排序）
插入排序的基本思路是将序列中的元素插入有序的序列中，所以可以假定数组中第一个元素为有序，依次遍历，与前面有序的元素依次比较，
找到比自己小（升序）的就在相应的位置插入
public static void chaRu(int[] arr){ //假定第一个元素是有序的，然后依次插入前面有序的序列 for(int i=1;i<arr.length;i++){ //标记待插入元素下标 int j = i; //记录标记元素的值 int target = arr[i]; while(j>0&&target<arr[j-1]){ //如果满足条件，向右移动 arr[j] = arr[j-1]; j--; } //插入数列中 arr[j] = target; } }
之前写的插入排序没有用target标记，结果出了很多问题，想了好久才想通，哎，还是太年轻了。。
这是之前写的插入排序
public static void chaRu(int[] arr){ //假定第一个元素是有序的，然后依次插入前面有序的序列 for(int i=1;i<arr.length;i++){ //标记待插入元素下标 int j = i; while(j>0&&arr[i]<arr[j-1]){ //如果满足条件，向右移动 arr[j] = arr[j-1]; j--; } //插入数列中 arr[j] = arr[i]; } }
在移动的过程中会改变arr[i]的值，所以会出错。
上面的这些排序时间复杂度相比其他排序都比较高，还有很多改进的地方，这里我就没优化了。。