ps:本文中所有的排序都是以升序的方式进行 1.选择排序 我们如果将数组分为两部分，前一部分是有序部分，后一部分是无序部分，那么选择排序就是每次从无序部分中挑选一个最小值，放到有序部分内。 刚开始在取第一个元素时，有序部分内此时没有元素，直接将该元素放进去，当放第二个元素时，有序部分已经有一个元素了，将该元素直接放在第一个元素的后面即可，以此类推。 我们可以看一下下面的动画图解，更直观的认识一下。 图中，有序部分为黄色部分，无序部分为蓝色部分。每趟中的最小值用红色标出，随着往后遍历，最小值也在变化。将最终的最小值放入有序部分，也就是数组的左端，与原来此位置上的元素交换位置。 代码实现如下：
public class Test { public static void main(String[] args) { int[] array = new int[]{1, 5, 6, 3, 2, 8, 0, 3}; selectSort(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "、"); } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void selectSort(int[] array) { // 每次选一个最小的数放在有序部分 for (int i = 0; i < array.length; i++) { // 有序 [0,i) // 无序[i,array.length] int minindex = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[minindex]) { minindex = j; } } swap(array, minindex, i); } } } 插入排序 插入排序就是每次从无序部分中取出一个数，在有序部分找到合适的位置，插入进去。 因此我们插入排序就需要两个步骤： step 1：给待插入元素在有序部分找到一个合适的位置 step 2：在该位置插入元素 有序部分为黄色，无序部分为蓝色，待插入元素为绿色。刚开始，有序部分没有数，在无序部分取出一个数，放入有序部分，再从无序部分中取出一个数，与有序部分中的数比较（从后往前比较），若待插入的数大于或等于有序部分中的数，则找到了合适的位置，将待插入元素插入到该位置。若待插入的数小于有序部分中的数，则有序部分往前走，直到走完有序部分或到了小于待插入元素的数。依此类推，直到所有的数都已有序。 代码实现如下： public class Test { public static void main(String[] args) { int[] array = new int[]{1, 4, 6, 3, 2, -2, 0, 3}; bubble1(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "、"); } } public static void insertSort1(int[] array) { for (int i = 0; i < array.length; i++) { int key = array[i]; int j = i - 1; for (; j >= 0 && key < array[j]; j--) { array[j + 1] = array[j]; } array[j + 1] = key; } } }上面的代码是遍历查找合适的位置，为了提高查找效率，我们也可以采用二分查找法来确定要插入的位置，代码如下：
// 二分插入排序 public static void insertSort2(int[] array) { for (int i = 0; i < array.length; i++) { int key = array[i]; // 在有序部分[0.i)做二分查找 int left = 0; int right = i; while (left < right) { //当left == right，就找到了 int mid = left + (right - left) / 2; if (key == array[mid]) { // 为了考虑稳定性，与mid后的再比较，mid后的数有可能都是相等的 left = mid + 1; } else if (key < array[mid]) { right = mid; } else { left = mid + 1; } } int pos = left; for (int k = i; k > pos; k--) { array[k] = array[k - 1]; } array[pos] = key; } }希尔排序也是插入排序的一种，希尔排序说简单点就是对数据分组做直接插入排序，是对数组先做了预排序，能很快的使数组基本有序，代码如下：
private static void insertWithGap(int[] array, int gap) { for (int i = 0; i < array.length; i++) { int key = array[i]; int j = i - gap; for (; j >= 0 && key < array[j]; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = key; } } public static void shellSort(int[] array) { int gap = array.length; while (true) { // gap = gap / 2; gap = (gap / 3) + 1; insertWithGap(array, gap); if (gap == 1) { break; } } } 冒泡排序 &emsp冒泡排序就是重复遍历所要排序的元素，依此比较相邻的两个元素大小，当不满足升序条件时，将两数交换位置。直到没有需要交换的时候。如图，我们从最后一个元素开始，与其相邻的元素比较，保证较小的元素在前面。第一次排序结束，我们把最小的元素冒泡到了最前面，依此类推，直到把所有的元素都排好序。代码实现如下：
public class Test { public static void main(String[] args) { int[] array = new int[]{1, 4, 6, 3, 2, -2, 0, 3}; bubble1(array); for (int i = 0; i < array.length; i++) { System.out.print(array[i] + "、"); } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void bubble1(int[] array){ // 排序的趟数 for(int i = 0; i < array.length-1; i++){ // 每趟比较的次数 for(int j = array.length -1; j > i; j--){ if(array[j] < array[j-1]){ swap(array,j-1,j); } } } } }上述代码可以优化一下，当数组本身有序时，我们第一趟在比较时就没有做任何交换，因此后续的比较就不用再做了。我们可以设置一个标记位，默认为true，当有交换时，将标志位改为false。每趟比较完后，对标志位检查，若为true，则直接返回。 代码如下：
public static void bubbleSort(int[] array) { boolean isSort = true; // 优化条件，判断是否发生过交换 for (int i = 0; i < array.length; i++) { // 最小的数冒泡到最前面(从后往前冒泡)、把最大的数冒泡到最后面 // 有序[0,i) // 无序[i,array.length] for (int j = array.length - 1; j > i; j--) { if (array[j] < array[j - 1]) { swap(array, j, j - 1); isSort = false; } } if (isSort) { break; } } }