排序算法的优劣指标：
时间复杂度：比较次数和移动次数 空间复杂度：需要多少辅助内存 稳定性：若A和B关键字相等，排序后先后次序没变则称之为稳定的，否则是不稳定的。 内部排序和外部排序： 需不需要辅助内存。 内部排序分类：选择排序（直接选择排序、堆排序） 交换排序（冒泡排序、快速排序） 插入排序（直接插入排序、折半插入排序、shell排序） 归并排序 桶式排序 基数排序。
选择排序：
直接选择排序：简单直观但性能略差。 （改进的选择排序先交换下标）
>public static void arraySelect(int[] a) { for (int out = 0; out < a.length - 1; out++) { int min = out; for (int in = out + 1; in < a.length; in++) { if (a[in] < a[min]) min = in; } if(min!=out){ int s0 = a[out]; a[out] = a[min]; a[min] = s0; } } }思路：第一个数，从后面的数中依次比较得出最小者，与第一位交换。依次过去。 特点：排一次可以确定最左边的最小者。 从而out++。 时间复杂度为O(n2) 空间复杂度为O(1)。 直接选择排序不稳定。
堆排序：
从上至下、从左至右：小根堆（顶子树最小，左比右小）大根堆（顶子树最大，左比右大） 完全二叉树。 时间浮复杂度O（nlogn） 空间复杂度 O(1) 堆排序不稳定
交换排序：主体操作是对数据组中的数据不断进行交换操作。
冒泡排序：
public static void arrayBub(int[] a) { for(int out=a.length-1;out>1;out--){ for(int in=0;in<out;in++){ if(a[in]>a[in+1]){ int s=a[in+1]; a[in+1]=a[in]; a[in]=s; } } } }思路：从左边开始，相邻两个比较，选出较小者放左边，依次过去。 特点：排一次可以确定最右边是最大者。 从而out-1. 时间效率不确定， 空间效率为O(1)。 冒泡排序稳定。
快速排序：选取一个数作为分界值，比它小的放左边，大的放右边。 然后对左右两个子序列进行递归。
public void quickSort() { recQuickSort(0, nElems - 1); } private void recQuickSort(int left, int right) { if (right - left <= 0) { return; } else { long pivot = theArray[right]; int partition = partitionIt(left, right, pivot); recQuickSort(left, partition - 1); recQuickSort(partition + 1, right); } }时间效率高 O(nlogn)， 因为使用了递归，递归使用了栈，空间效率为O(nlog2n) 包含跳跃式交换，所以快速排序不稳定。
插入排序：
直接插入排序：
public static void arrayInsert(int[] a) { for (int out = 1; out < a.length; out++) { int temp = a[out]; int in = out; while (in > 0 && a[in - 1] >= temp) { a[in] = a[in - 1]; in--; } a[in] = temp; } }思路：从第二个元素开始，保持前面的元素局部有序。out++角标右移，与前面局部有序的部分比较，然后插入。 特点：对于开始就比较有序的数组，插入排序算法很快； 但对于随机数组，插入排序很慢。 时间复杂度O(n2)
折半插入排序：
public void halfInsert(){ for(int i=0;i<theArray.length;i++){ int tmp=(int) theArray[i]; int low=0; int high=i-1; while(low<=high){ int mid=(low+high)/2; if(tmp>=theArray[mid]){ low=mid+1; }else{ high=mid-1; } } for(int j=i;j>low;j--){ theArray[j]=theArray[j-1]; } theArray[low]=tmp; } }折半插入排序可以更快的确定第i个元素的插入位置。 效果与简单插入排序的效果基本相同，只是更快一些。
shell排序：可以认为直接插入排序是shell排序的一种特例—直接使用增量为1的shell排序就是直接插入排序。
public void shellSort() { int inner, outer; long tmp; int h = 1; while (h <= nElems / 3) h = h * 3 + 1; while (h > 0) { for (outer = h; outer < nElems; outer++) { tmp = theArray[outer]; inner = outer; while (inner > h - 1 && theArray[inner - h] >= tmp) { theArray[inner] = theArray[inner - h]; inner -= h; } theArray[inner]=tmp; } h=(h-1)/3; } }shell排序是直接插入排序的改进版，所以是稳定的，时间开销在 O(n3/2)~O(n7/6)之间。 空间开销是O(1)。
归并排序：
基本思想是将多个有序的序列合并成一个新的有序序列。
public void MergeSort() { sort(theArray, 0, nElems - 1); } private void sort(long[] theArray, int left, int rght) { int center = (left + rght) / 2; sort(theArray, left, center); sort(theArray, center + 1, rght); merge(theArray, left, center, rght); } private void merge(long[] theArray2, int left, int center, int rght) { long[] tmpArr = new long[theArray2.length]; int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= rght) { if (theArray[left] <= theArray[mid]) { tmpArr[third++] = theArray[left++]; } else { tmpArr[third++] = theArray[mid++]; } } while (mid <= rght) { tmpArr[third++] = theArray[mid++]; } while (left <= center) { tmpArr[third++] = theArray[left++]; } while (tmp <= rght) { theArray[tmp] = tmpArr[tmp++]; } } }归并算法需要递归地分解、合并，每进行一趟两路归并排序需要调用merge方法一次，每次执行merge方法需要比较n次，所以时间复杂度为O(nlog2n) ；空间效率较差，它需要一个与原始序列同样大小的辅助序列。 归并算法是稳定的。
桶式排序：
不是基于比较的算法。要求待排序满足：所有值处于一个可枚举范围内；枚举范围不应太大，否则开销太大。
基数排序：
必须依赖于另外的排序算法。总体思路将待排序的数据拆分成多个排序关键字。
