原地排序算法，不使用额外空间

  1. 冒泡排序

每次循环将最大通过相邻交换换到最后，做N-1次循环，第i次循环的要交换的数下标范围是[0,N-1-i]，j的范围是[0,N-2-i]。O（n2）

  1. void bubbleSort(int[] arr){
  2.     // 循环次数N-1
  3.     for(int i=0;i<arr.length-1;i++){
  4.         // 交换的靠前元素下标 j
  5.         for(int j=0;j<arr.length-1-i;j++){
  6.             if(arr[j]>arr[j+1]) swap(arr,j,j+1);
  7.         }
  8.     }
  9. }
  10. void swap(int[] nums, int i, int j) {
  11.     // 交换 nums[i] 和 nums[j]
  12.     int tmp = nums[i];
  13.     nums[i] = nums[j];
  14.     nums[j] = tmp;
  15. }
  1. 插入排序

类似于扑克牌整牌，分为有序部分和无序部分，每次循环的目的是使无序部分的第一个排到有序部分的合适位置，方式是不断向左交换。循环次数为N-1次。O（n2）

  1. void insertSort(int[] arr){
  2.     // i为无序部分的第一个数的下标
  3.     for(int i=1;i<arr.length;i++){
  4.         // 从i开始往前两两比较，j为交换的靠前元素的下标，初值是有序部分的最后一个数的下标i-1
  5.         for(int j=i-1;j>=0;j--){
  6.             if(arr[j]>arr[j+1]) swap(arr,j,j+1);
  7.         }
  8.     }
  9. }
  10. void swap(int[] nums, int i, int j) {
  11.     // 交换 nums[i] 和 nums[j]
  12.     int tmp = nums[i];
  13.     nums[i] = nums[j];
  14.     nums[j] = tmp;
  15. }
  1. 选择排序

分为有序部分和无序部分，每次循环的目的是使第i次循环找到第i个小的数放在下标i位置，循环N-1次。找第i小的手段是，循环找到无序部分，比原本下标 i 位置的数小的数中最小的位置，然后交换；如果没找到，则说明原本 i 下标就放着第 i 小的数，无需操作。O（n2）

  1. void selectSort(int[] arr){
  2.     // i为找到数后应该放的下标
  3.     for(int i=0;i<arr.length-1;i++){
  4.         int flag=arr[i];
  5.         int pos=i;
  6.         // j为无序部分的下标
  7.         for(int j=i+1;j<arr.length;j++){
  8.             if(arr[j]<flag) {
  9.                 //更新最小值与位置记录
  10.                 pos=j;
  11.                 flag=arr[j];
  12.             }
  13.         }
  14.         // 判断pos是否已更新
  15.         if(pos!=i) swap(arr,i,pos);
  16.     }
  17. }
  18. void swap(int[] nums, int i, int j) {
  19.     // 交换 nums[i] 和 nums[j]
  20.     int tmp = nums[i];
  21.     nums[i] = nums[j];
  22.     nums[j] = tmp;
  23. }
  1. 堆排序

分为有序部分和无序部分， i 次循环时，末尾的 i 位是有序部分，前面n-i 位通过维护组成一个大顶堆（以升序为例），然后将堆顶与 无序部分的最后一位交换，交换后，末尾的 i+1位形成有序部分，前面位由于交换而失衡，在下一次循环中重新维护大顶堆。O（nlogn）

  1. package sortdemo;
  3. import java.util.Arrays;
  5. /**
  6.  * Created by chengxiao on 2016/12/17.
  7.  * 堆排序demo
  8.  */
  9. public class HeapSort {
  10.     public static void main(String []args){
  11.         int []arr = {9,8,7,6,5,4,3,2,1};
  12.         sort(arr);
  13.         System.out.println(Arrays.toString(arr));
  14.     }
  15.     public static void sort(int []arr){
  16.         //1.构建大顶堆
  17.         for(int i=arr.length/2-1;i>=0;i--){
  18.             //从第一个非叶子结点从下至上，从右至左调整结构
  19.             adjustHeap(arr,i,arr.length);
  20.         }
  21.         //2.交换堆顶元素与末尾元素，之后调整堆结构
  22.         for(int j=arr.length-1;j>0;j--){
  23.             swap(arr,0,j);//将堆顶元素与末尾元素进行交换
  24.             adjustHeap(arr,0,j);//重新对堆进行调整
  25.         }
  27.     }
  29.     /**
  30.      * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
  31.      * @param arr
  32.      * @param i
  33.      * @param length
  34.      */
  35.     public static void adjustHeap(int []arr,int i,int length){
  36.         int temp = arr[i];//先取出当前元素i
  37.         for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
  38.             // 使k指向左子节点与右子节点中的较大值
  39.             if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
  40.                 k++;
  41.             }
  43.             if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
  44.                 arr[i] = arr[k];
  45.                 i = k;
  46.             }else{
  47.                 break;
  48.             }
  49.         }
  50.         arr[i] = temp;//将temp值放到最终的位置
  51.     }
  53.     /**
  54.      * 交换元素
  55.      * @param arr
  56.      * @param a
  57.      * @param b
  58.      */
  59.     public static void swap(int []arr,int a ,int b){
  60.         int temp=arr[a];
  61.         arr[a] = arr[b];
  62.         arr[b] = temp;
  63.     }
  64. }

非原地算法

  1. 快速排序

递归。每次递归按照标志位划分为大于标志位和小于标志位的，具体是将两边的大小元素交换实现，最后把标志位与中间i=j的位置交换。O(logN), O(logN)。
注意，标准快排的具体执行与该代码执行顺序有所不同，每次找到比标志位小的 a[j] 或 比标志位大的 a[i]，就会将标志位与其交换。

  1. void quickSort(int[] nums, int l, int r) {
  2.     // 子数组长度为 1 时终止递归
  3.     if (l >= r) return;
  4.     // 哨兵划分操作
  5.     // 以 nums[l] 作为基准数
  6.     int i = l, j = r;
  7.     while (i < j) {
  8.         // 先从右向左找到arr[j]<flag为止
  9.         while (i < j && nums[j] >= nums[l]) j--;
  10.         // 再从左向右找到arr[i]>flag为止
  11.         while (i < j && nums[i] <= nums[l]) i++;
  12.         swap(nums, i, j);
  13.     }
  14.     swap(nums, i, l);
  15.     // 递归左（右）子数组执行哨兵划分
  16.     quickSort(nums, l, i - 1);
  17.     quickSort(nums, i + 1, r);
  18. }
  20. void swap(int[] nums, int i, int j) {
  21.     // 交换 nums[i] 和 nums[j]
  22.     int tmp = nums[i];
  23.     nums[i] = nums[j];
  24.     nums[j] = tmp;
  25. }
  27. // 调用
  28. int[] nums = { 4, 1, 3, 2, 5 };
  29. quickSort(nums, 0, nums.length - 1);
  1. 归并排序

递归，分治。注意合并时需要复制原数据作为判定依据。O（logN），O（N）

  1. void mergeSort(int[] nums, int start, int stop) {
  2.     // 终止递归
  3.     if (start >= stop) return;
  4.     // 对半分
  5.     int mid=(start+stop)/2;
  6.     mergeSort(nums, start, mid);
  7.     mergeSort(nums, mid+1, stop);
  8.     // 合并
  9.     // 由于原数组在合并时会改变，因此复制每次递归中的数组，作为合并的判据
  10.     int[] temp=new int[stop-start+1];
  11.     for(int i=0;i<temp.length;i++){
  12.         temp[i]=nums[start+i];
  13.     }
  14.     // 合并[start,mid] 与[mid+1,stop]
  15.     // i,j 为 待合并数组在temp中的下标
  16.     int i=start-start, j=mid+1-start;
  17.     // k为合并所在位置在原数组的下标
  18.     for(int k=start;k<=stop;k++){
  19.         // 考虑 i 越界
  20.         if(i==mid-start+1){
  21.             nums[k]=temp[j++];
  22.         // j 越界 或 i位置数更小
  23.         }else if(j==stop-start+1 || temp[i]<temp[j]){
  24.             nums[k]=temp[i++];
  25.         // j位置数更小
  26.         }else{
  27.             nums[k]=temp[j++];
  28.         }
  29.     }
  30. }