冒泡排序：
public static int[] bubbleSort(int[] arr){ // i用来控制需要排序多少趟，j用来控制当前元素需要比较的次数 int i, j, temp, len = arr.length; // 共计多少趟排序,最后一个元素不用,前面的排好了，最后一个自动有序 for(i = 0; i < len - 1; i++){ // 比较次数，对剩下的无序元素进行排序 for(j = 0; j < len - i - 1; j++){ // 如果arr[j] > arr[j + 1]，就交换它们的位置 if(arr[j] > arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } return arr; } 改进之后：加了一个changed变量，如果一次比较中没有发生交换，则是有序的 public static int[] bubbleSort(int[] arr) { int i, j, temp, len = arr.length, changed = 1, count = 0; for (i = 0; i < len - 1 && changed != 0; i++) { count++; // 记录冒泡的次数 changed = 0; for (j = 0; j < len - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; changed = 1; // 发生位置交换，说明当前数组在本次位置交换前还是无序的 } } } System.out.println(count); // 4，如果是未改进的冒泡排序则需要6次冒泡(7-1) return arr; }插入排序：
public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 ; j--) { if(arr[j]>arr[j+1]) { swap(arr,j,j+1); } } } }快速排序：
通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组递归排序也就将整个数组排序了
切分过程：取 a[left] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[left] 和 a[j] 交换位置
public class QuickSort { public static int[] Asort (int [] nums){ Bsort(nums,0,nums.length-1); return nums; } public static void Bsort(int []nums,int left,int right){ if(right<=left){ return ; } int j=partition(nums,left,right); Bsort(nums,left,j-1); Bsort(nums,j+1,right); } public static int partition(int nums[],int left,int right){ int i=left,j=right+1; int v=nums[left]; while(true){ while(nums[++i]<=v&&i<right){ } while(nums[--j]>v&& j>0){ } if(i>=j){ break; } swap(nums,i,j); } swap(nums,left,j); return j; } public static void swap(int[] arr,int i,int j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }选择排序：
思想：
从0-n-1中选择最小的数放在数组第一个位置
从1-n-1中选择最小的数放在第二个位置
.............
public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; //从后面的元素选最小的数和第一个数交换，继续此过程 for (int j = i + 1; j < arr.length; j++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr, i, minIndex); } }归并排序：
思想，将数组分层二半，先将左边得部分排好序，右边的排好序，最后再整体排序,
仔细分析以下merge过程，要先准备一个辅助数组help,它跟原数组有同样大的长度，用一个指针p1指向数组的第一个位置，p2指向数组的mid+1位置，比较p1和p2所指的值谁小，就放入help数组里面，同时,p1,p2要往下走，help的长度也要加一，最后还要将help数组中的元素的元素替换原来数组中的元素arr[L+i]=help[i]。
public class MergeSort { public static void process(int[] arr) { if (arr == null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int L, int R) { if (L == R) { return; } int mid = L + ((R - L) >> 1); mergeSort(arr, L, mid); mergeSort(arr, mid + 1, R); merge(arr, L, mid, R); } public static void merge(int[] arr, int L, int mid, int R) { int[] help = new int[R - L + 1]; int i = 0; int p1 = L; int p2 = mid + 1; while (p1 <= mid && p2 <= R) { //help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; if(arr[p1]<arr[p2]){ help[i++]=arr[p1++]; }else{ help[i++]=arr[p2++]; } } while (p1 <= mid) { help[i++] = arr[p1++]; } while (p2 <= R) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[L + i] = help[i]; } }堆排序： 堆排序的步骤主要包括建立大根堆，以及调整堆的结构
1.建立大根堆(即建立0~i的大根堆)
也就是将数组变成一个大根堆的形式，大根堆的结构是任何一颗子树的根节点的值大于左右子节点的值，建立大根堆的过程其实是将数组中的数往上移动的过程。时间复杂度是O(n),为什么是O(n)呢？对于一个i位置上的数将其添加到堆中的所需时间复杂度为O(log i-1),i+1位置上数所需时间复杂度为O(log i),总的时间复杂度为O(log 1)+O(log2)+O(log3)+....+O(log n)=O(n)
private static void heapInsert(int[] arr, int index) { while(arr[index]<arr[(index-1)/2]) { swap(arr,index,(index-1)/2); index=(index-1)/2; } }2.调整堆结构
经过1过程，已经将数组变成一个大根堆，但是有些时候堆的某些值改变，导致整棵树不是大根堆的结构，这个时候就需要进行调整，具体调整过程如下：
先在左右子节点中选择最大的节点，再和根节点进行比较选择最大的，建立堆的过程是往上调整，而调整堆的过程是将数往下移。时间复杂度为调整整个堆的代价即O(logn)
public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { //选取左右子节点的最大值 int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; //选取根节点和左右子节点的最大值中的最大值 largest = arr[largest] > arr[index] ? largest : index; //如果根节点就是最大的，跳出循环 if (largest == index) { break; } //否则交换根节点和左右子节点中的最大值 swap(arr, largest, index); //更新根节点索引 index = largest; //保证循环能进行下去 left = index * 2 + 1; } }堆排序的总过程：
先建立大根堆，交换堆中的根节点(即数组第一个位置的数)与最后一个节点(数组最后一个数)
然后堆的长度减1，调整堆的结构，这样每一步得到的数是数组中的最大的，循环此步骤，也就完成了排序。
public class Code_03_HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; //交换堆顶元素和堆中最后一个元素，长度减1 swap(arr, 0, --size); //循环 while (size > 0) { //调整上一此堆中少一个元素之后的结构，是使其恢复大根堆 heapify(arr, 0, size); swap(arr, 0, --size); } } public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }int i=4;
System.out.println(i--);//输出4，所以为什么是--size了
