本文共 7141 字，大约阅读时间需要 23 分钟。
从第一个开始比较，找到最大的值，让其交换到数组的最后面，然后就第二大，第三大·····，不断比较，当前一个的值都比后一个的值小的时候，数组排序结束。
时间复杂度是O(n^2)
稳定性较强，因为总是相邻的两个元素在交换
public class TenAlgorithm { public static void main(String[] args) { int[] a={ 4,5,8,9,6,2,3,5,4,58,15,9}; for (int i:bubbleSort(a)) { System.out.print(i+","); } } public static int[] bubbleSort(int[] arr){ int len=arr.length; if(arr==null||len<2){ return arr; } int temp=0; for (int i = 0; i < len; i++) { for (int j=0;j arr[j+1]){ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } return arr; }} 从无序的区间不断找出最小值，挑选n-1次（最后一个元素不用挑）。与冒泡排序的不同在于，冒泡排序每次比对都要交换元素的位置，而选择排序只有经过一轮的比较后，找到这一轮最小值的下标才会去交换元素，相比之下节省了不少的资源。
时间复杂度：O（n^2）
稳定性较差，因为有可能第一个和最后一个元素交换
public static int[] selectSort(int[] arr){ int len=arr.length; if(arr==null||len<2){ return arr; } for (int i = 0; i arr[j]){ minIndex=j; } } swap(arr,minIndex,i); } return arr; } public static void swap(int[] arr,int minIndex,int i){ int temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } 插入排序就是把未排序的元素插入到已排序的数组中。
把左边的第一位看做已经排好序的数组，右边的为没有拍好序的数组，通过向左边一个个的插入右边的元素从而实现数组的排序。
从数组的第二个元素开始遍历，在进入第一个循环后，需要保存当前位置元素。然后进行比较，如果前一个元素大于保存的元素，则前一个元素向后移动一位，一直如此，直到前一个元素小于保存的元素时，停止。
然后跳出内循环，因为当前j位置的元素是小于保存的元素，并且其后一个的元素已经向后移动了一位，所以保存的元素要插入的位置是j+1。
时间复杂度：O（n^2）
稳定性较强，因为在相邻的元素中移动
public static int[] insertionSort(int[] arr){ int len=arr.length; if(arr==null||len<2){ return arr; } for (int i = 1; i < len; i++) { int insert=arr[i]; int j=i-1; for (; j>=0&&arr[j] >insert ; j--) { //如果前一个大于后一个，则移动前一个到后面 arr[j+1]=arr[j]; } arr[j+1]=insert; } return arr; } 小规模数据或者基本有序时高效（数据有序程度越高，越高效（移动少））
首先把一个较大的数据集合分割成若干个小组（逻辑上的分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。
{9，8，7，6，5，4，3，2}这种，一开始以4为间隔，就是{9，5}，{8，4}，{7，3}，{6，2}，对里面的进行插入排序得到{5，4，3，2，9，8，7，6}，然后再长度对半为2分组，就是{5，3，9，7}，{4，2，8，6}得到{3，2，5，4，7，6，9，8}，再重复上面的操作，最后得到{2，3，4，5，6，7，8，9}。public static int[] shellSort(int[] arr){ int len=arr.length; if(arr==null||len<2){ return arr; } //进行分组，最开始时的增量为数组长度的一半 for (int gap =len/2 ; gap>0; gap/=2) { //比较完一组后，再移动下一组（按一组组这样进行插入排序） for (int i = gap; i < len; i++) { int insertValue=arr[i]; //j已经移到第前grap个了 int j=i-gap; //插入的时候按组进行插入（组内元素两两相隔gap） for (; j >=0 &&insertValue 希尔排序的复杂度和增量序列是相关的
{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)
Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n ^ 1.5)
Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}
归并排序是建立在归并操作的一种高效的排序方法，该方法采用了分治的思想，比较适用于处理较大规模的数据，但比较耗内存。
public static int[] mergeSortArr(int[] arr){ int len=arr.length; if(arr==null||len<2){ return arr; } int[] temp=new int[len]; //right的长度为len-1，因为从0开始 mergeSort(arr,temp,0,len-1); return arr; } private static void mergeSort(int[] arr, int[] temp, int left, int right) { //当left==right是停止 if(left center mergeSort(arr,temp,left,center); //右边center+1->right mergeSort(arr,temp,center+1,right); //合并数组 merge(arr,temp,left,center,right); } } private static void merge(int[] arr, int[] temp, int left, int center, int right) { int i=left,j=center+1; for (int k = left; k <=right; k++) { //如果i大于center，表示i的数组已经赋值完，不需要再比较，直接copy数组j //如果j大于right，表示j的数组已经赋值完，不需要再比较，直接copy数组i if(i>center){ temp[k]=arr[j++]; }else if(j>right){ temp[k]=arr[i++]; }else if(arr[i]<=arr[j]){ temp[k]=arr[i++]; }else { temp[k]=arr[j++]; } } //从临时数组传回原来数组 for (int k = left; k <=right; k++) { arr[k]=temp[k]; } } 时间复杂度：O（N log N）
时间复杂度：O（nlogn），最坏的情况为O(n^2)
稳定性较差
它不像归并排序那样，需要额外的辅助空间，而且在分割调整的时候，不像归并排序那样，元素还要在辅助数组与源数组之间来回复制。
/** * 快速排序 * * @param arr * @return int[] */ public static int[] partitionSort(int[] arr) { int len = arr.length; if (arr == null || len < 2) { return arr; } partition(arr, 0, len - 1); return arr; } private static void partition(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[left]; int i = left + 1, j = right; while (i < j) { while (i <= j && arr[i] <= pivot) { i++; } while (i <= j && arr[j] >= pivot) { j--; } if (i >= j) { break; } int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } if (pivot > arr[j]) { arr[left] = arr[j]; arr[j] = pivot; } partition(arr, left, j - 1); partition(arr, j + 1, right); } 基本思想：把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如temp[i]=m，表示元素i一共出现了m次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来的数据是有序的。
时间复杂度：O（n）
private static int[] countSort(int[] arr){ int len = arr.length; if (arr == null || len < 2) { return arr; } int min=arr[0]; int max=arr[0]; //寻找数组的最大值与最小值 for (int i = 0; i < len; i++) { if(max arr[i]){ min=arr[i]; } } int d=max-min+1; //创建大小为max的临时数组 int[] temp=new int[d]; //统计元素i出现的次数 for (int i = 0; i < len; i++) { temp[arr[i]-min]++; } int k=0; //把临时数组统计好的数据汇总到原数组 for (int i = 0; i < d; i++) { for (int j = temp[i]; j >0 ; j--) { arr[k++]=i+min; } } return arr; } 参考：https://www.iamshuaidi.com/608.html
转载地址：http://nlvgn.baihongyu.com/