写在前面：因为自己编程挺弱的，可能写的代码有瑕疵，并且有些没有优化（比如在快排时，选择基准值时就直接选择最前面的值），但是代码都能运行通过，欢迎交流与指出！
排序算法介绍
排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。
排序算法的稳定性：假设在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法的稳定的，否则称为不稳定的。
待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序算法分为：内部排序（计算机随机存储器中进行排序），外部排序（待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序过程）
本文只讨论内部排序。
内部排序介绍
按排序过程中依据的不同原则对内部排序进行分类，大致可分为插入排序（直接插入排序、希尔排序）、交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、归并排序和计数排序等五类。
下表给出了常见比较排序算法的性能：
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)~O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)~O(n) | 不稳定 |
冒泡排序
1 public static void bubbleSort(int[] num){ 2 if (num==null) 3 return; 4 5 for (int i=0; i<num.length-1; i++){ //遍历的趟数 n-1，每遍历一次就有一个数在规定的位置上 6 boolean flag = true; //判断是否已经排好序了，如果排好了，直接退出循环，优化部分 7 8 // 从后向前开始冒泡。因为前i个元素已经为排好序的，所以判断范围为i到n-1，即比较到i+1和i为止，j到i+1。 9 for (int j=num.length-1; j>i; j--){ 10 if (num[j] < num[j-1]){ 11 int temp = num[j]; 12 num[j] = num[j-1]; 13 num[j-1] = temp; 14 flag = false; //如果有交换，说明并没有拍好序，继续下一趟排序。 15 } 16 } 17 18 if (flag) 19 break; 20 } 21 }
简单选择排序
选择排序的基本思想：每一趟在n-i+1(i=1,2,...,n-1)个记录中选出关键字最小的记录作为有序序列中的第i个记录。
1 public static void selectionSort(int[] num){ 2 if (num==null) 3 return; 4 5 //每次选择一个未排序数组中最小的放在开始处，一共需要n-1次 6 for (int i=0; i<num.length-1; i++){ 7 int min = i; //将每次遍历开始的索引保存为min，之后min保存当前遍历中数值最小的索引。 8 for (int j=i+1; j<num.length; j++){ 9 if (num[j] < num[min]){ 10 min = j; 11 } 12 } 13 14 //如果min不等于i，将最小的数值调换到i位置上 15 if (i != min){ 16 int temp = num[i]; 17 num[i] = num[min]; 18 num[min] = temp; 19 } 20 } 21 }
直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
1 public static void insertSort(int[] num){ 2 if (num==null) 3 return; 4 5 //因为给定的数组一般都是从下标为0开始的，如果将其作为哨兵，需要将其先整体往后挪，排完序后再挪回来 6 //所以声明一个常数空间来存储元素,但是这样无法防止数组越界，需要自己判断 7 for (int i=1; i<num.length; i++){ 8 if (num[i] < num[i-1]){ //可以不用这行判断，见希尔排序的写法 9 int temp = num[i]; //复制为哨兵 10 int j = i-1; 11 //加入约束条件j>=0，并且要将其放在前面，不然数组越界 12 while (j>=0 && temp<num[j]){ 13 num[j+1] = num[j]; 14 j--; 15 } 16 num[j+1] = temp; 17 } 18 } 19 }
改进：折半插入排序、2-路插入排序
希尔排序
又称为“缩小增量排序”。基本思想：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
1 //希尔排序 2 //插入排序法可以高速处理顺序较整齐的数据，而希尔排序法就是充分发挥插入排序法这一特长的高速算法。 3 public static void shellSort(int[] num){ 4 if (num==null || num.length==0) 5 return; 6 7 //生成数组G，表示间隔。因为G的大小不能确定，所以使用list 8 List<Integer> G = new ArrayList<>(); 9 int h = 1; 10 while (h<num.length){ 11 G.add(h); 12 h = 3*h + 1; 13 } 14 15 for (int i=G.size()-1; i>=0; i--){ 16 insertionSortShell(num, G.get(i)); 17 } 18 } 19 20 public static void insertionSortShell(int[] num, int g){ 21 for (int i=g; i<num.length; i++){ 22 int temp = num[i]; 23 int j = i-g; 24 while (j>=0 && num[j]>temp){ 25 num[j+g] = num[j]; 26 j -= g; 27 } 28 num[j+g] = temp; 29 } 30 }
快速排序
基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序的递归代码：
1 // r代表的是数组的最后一个元素 2 public static int partition(int[] nums, int p, int r){ 3 int x = nums[r]; 4 int i = p-1; 5 for (int j=p; j<r; j++){ 6 if (nums[j] <= x){ 7 i++; 8 int temp = nums[i]; 9 nums[i] = nums[j]; 10 nums[j] = temp; 11 } 12 } 13 14 int temp = nums[i+1]; 15 nums[i+1] = nums[r]; 16 nums[r] = temp; 17 18 return i+1; 19 } 20 21 public static void quickSort(int[] nums, int p, int r){ 22 if (p < r){ 23 int q = partition(nums, p, r); 24 quickSort(nums, p, q-1); 25 quickSort(nums, q+1, r); 26 } 27 } 28 29 public static void quickSort2(int[] nums, int l, int r){ 30 if (l>=r){ 31 return; 32 } 33 34 int i = l; 35 int j = r; 36 int key = nums[l]; 37 38 while (i<j){ 39 while (i<j && nums[j]>=key){ 40 j--; 41 } 42 if (i<j){ 43 nums[i] = nums[j]; 44 i++; 45 } 46 47 while (i<j && nums[i]<key){ 48 i++; 49 } 50 if (i<j){ 51 nums[j] = nums[i]; 52 j--; 53 } 54 } 55 56 nums[i] = key; 57 quickSort2(nums, l, i-1); 58 quickSort2(nums, i+1, r); 59 }
快速排序的非递归代码
1 public static void quickSortUnRec(int[] num, int start, int end){ 2 Stack<Integer> stack = new Stack<>(); //用栈模拟 3 if (start < end){ 4 stack.push(end); 5 stack.push(start); 6 while (!stack.isEmpty()){ 7 int l = stack.pop(); 8 int r = stack.pop(); 9 int index = partition2(num, l, r); 10 if (l < index-1){ 11 stack.push(index-1); 12 stack.push(l); 13 } 14 if (r > index+1){ 15 stack.push(r); 16 stack.push(index+1); 17 } 18 } 19 } 20 } 21 22 private static int partition2(int[] num, int l, int r) { 23 int pivot = num[l]; 24 while(l<r){ 25 while(l<r && num[r]>=pivot){ 26 r--; 27 } 28 if (l<r){ 29 num[l] = num[r]; 30 l++; 31 } 32 while(l<r && num[l]<pivot){ 33 l++; 34 } 35 if (l<r){ 36 num[r] = num[l]; 37 r--; 38 } 39 } 40 num[l] = pivot; 41 return l; 42 }
递归算法使用的栈由程序自动产生，栈中包含：函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数，则栈会很大。每次递归调用都要操作很大的栈，效率自然会下降。
而对于非递归算法，每次循环使用自己预先创建的栈，因此不管程序复杂度如何，都不会影响程序效率。
对于上面的快速排序，由于局部变量只有一个mid，栈很小，所以效率并不比非递归实现的低。
若初始记录序列按关键字有序或者基本有序时，快速排序将蜕化为起泡排序，时间复杂度为O(n2)，为改进之，通常依“三者取中”的法则来选取枢纽记录。
堆排序
使用的是最小堆，每次最小的值和最后一个元素交换，因此最后的排序是从大到小排序的。
堆排序的非递归代码：
1 public static void minHeapSort(int[] nums, int n){ 2 if (nums == null){ 3 return; 4 } 5 6 buildMinHeap(nums, n); 7 8 for (int i=n-1; i>0; i--){ 9 int temp = nums[0]; 10 nums[0] = nums[i]; 11 nums[i] = temp; 12 13 minHeapFixDown(nums, 0, i); 14 } 15 16 } 17 18 private static void buildMinHeap(int[] nums, int n) { 19 for (int i=(n-1)/2; i>=0; i--){ 20 minHeapFixDown(nums, i, n); 21 } 22 } 23 24 private static void minHeapFixDown(int[] nums, int i, int n) { 25 int j = 2*i+1; 26 27 while (j < n){ 28 if (j+1<n && nums[j+1]<nums[j]){ 29 j++; 30 } 31 if (nums[i] <= nums[j]){ 32 break; 33 } 34 35 int temp = nums[i]; 36 nums[i] = nums[j]; 37 nums[j] = temp; 38 39 i = j; 40 j = 2*i+1; 41 } 42 }
堆排序的递归代码（只在调整堆的时候有变化）：
1 private static void minHeapFixDown2(int[] nums, int i, int n){ 2 int j = 2*i+1; 3 4 if (j >= n){ 5 return; 6 } 7 8 if (j+1<n && nums[j+1]<nums[j]){ 9 j++; 10 } 11 if (nums[i] <= nums[j]){ 12 return; 13 } 14 15 int temp = nums[i]; 16 nums[i] = nums[j]; 17 nums[j] = temp; 18 19 minHeapFixDown2(nums, j, n); 20 }
归并排序
假设初始序列有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2(向上取整)个长度为2或1的有序子序列；再两两归并，...，如此重复，直至得到一个长度为n的有序序列为止，这种方法称为2-路归并排序。
归并排序的递归代码：
1 // right代表的是最后一个元素的后一个元素 2 public static void mergeSort(int[] nums, int left, int right){ 3 if (left+1 < right){ 4 int mid = (left + right) / 2; 5 mergeSort(nums, left, mid); 6 mergeSort(nums, mid, right); 7 merge(nums, left, mid, right); 8 } 9 } 10 11 private static void merge(int[] nums, int left, int mid, int right) { 12 int n1 = mid - left; 13 int n2 = right - mid; 14 15 int[] L = new int[n1+1]; 16 int[] R = new int[n2+1]; 17 for (int i=0; i<n1; i++){ 18 L[i] = nums[left+i]; 19 } 20 for (int i=0; i<n2; i++){ 21 R[i] = nums[mid+i]; 22 } 23 L[n1] = Integer.MAX_VALUE; 24 R[n2] = Integer.MAX_VALUE; 25 26 int i = 0; 27 int j = 0; 28 for (int k=left; k<right; k++){ 29 if (L[i] <= R[j]){ 30 nums[k] = L[i++]; 31 }else { 32 nums[k] = R[j++]; 33 } 34 } 35 }
归并排序的非递归代码（merge方法和上面一致）：
1 public static void mergeSortUnRec(int[] num){ 2 int len = 1; 3 while (len <= num.length){ 4 5 for (int i=0; i+len<=num.length; i+=len*2){ 6 int low = i; 7 int mid = i+len; 8 int high = i+2*len; 9 10 if (high>num.length){ 11 high=num.length; 12 } 13 merge(num, low, mid, high); 14 } 15 len *= 2; 16 } 17 }
计数排序
先统计出每个数对应的个数（数组C），然后每个值都累加前面所有数的个数（数组C进行累加），最后从后向前面遍历所有数。
1 //假设输入的元素都是0到k之间的整数 2 public static void countingSort(int[] A, int[] B, int k){ 3 4 int[] C = new int[k+1]; 5 for (int i=0; i<A.length; i++){ 6 C[A[i]]++; 7 } 8 9 for (int i=1; i<=k; i++){ 10 C[i] += C[i-1]; 11 } 12 13 for (int i=A.length-1; i>=0; i--){ 14 B[C[A[i]]-1] = A[i]; 15 C[A[i]]--; 16 } 17 }
参考：
http://www.cnblogs.com/eniac12/p/5329396.html#s3