1.分类

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
?

2.算法复杂度

3.相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

4.各类排序

一、冒泡排序

简单，不总结

二、选择排序（Selection Sort）

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

for (int i = 0 ; i < arr.length - 1; i ++){
 ? ?int min = arr[i];
 ? ?int index = i;
 ? ?for (int j = i + 1 ; j < arr.length ; j ++ ){
?
 ? ? ? ?if ( arr[j] < min){
 ? ? ? ? ? ?min = arr[j];
 ? ? ? ? ? ?index = j;
 ? ? ?  }
 ?  }
?
 ? ?if (index != i){
 ? ? ? ?arr[index] = arr[i];
 ? ? ? ?arr[i] = min;
 ?  }
}

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

三、插入排序（Insertion Sort）

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；

for (int i = 1 ; i < array.length ; i ++) {
?
 ? ?int insertVal = array[i];
 ? ?int insertIndex = i - 1;
?
 ? ?while (insertIndex >= 0 && insertVal < array[insertIndex]) {
 ? ? ? ?array[insertIndex + 1] = array[insertIndex];
 ? ? ? ?insertIndex--;
 ?  }
?
 ? ?if (insertIndex + 1 != i)
 ? ? ? ?array[insertIndex + 1] = insertVal;
}

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

四、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

 for (int gap = array.length/2; gap > 0; gap /= 2){
 ? ? for (int i = gap; i < array.length ; i ++){
 ? ? ? ? int j = i;
 ? ? ? ? int temp = array[j];
 ? ? ? ? while (j - gap>= 0 && array[j] < array[j - gap] ){
 ? ? ? ? ? ? array[j] = array[j - gap];
 ? ? ? ? ? ? j -= gap;
 ? ? ? ? }
 ? ? ? ? array[j] = temp;
 ? ? }
 }

五、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

public static void merge(int[] array,int left,int mid,int right,int[] temp){
 ? ?int l = left;
 ? ?int r = mid + 1;
 ? ?int t = 0;
?
?
 ? ?while (l <= mid && r <= right){
 ? ? ? ?if (array[l] <= array[r] ){
 ? ? ? ? ? ?temp[t] = array[l];
 ? ? ? ? ? ?t ++;
 ? ? ? ? ? ?l ++;
 ? ? ?  }else {
 ? ? ? ? ? ?temp[t] = array[r];
 ? ? ? ? ? ?t ++;
 ? ? ? ? ? ?r ++;
 ? ? ?  }
 ?  }
?
 ? ?// 剩余的数
 ? ?while (l <= mid){
 ? ? ? ?temp[t] = array[l];
 ? ? ? ?l ++;
 ? ? ? ?t ++;
 ?  }
?
 ? ?while (r <= right){
 ? ? ? ?temp[t] = array[r];
 ? ? ? ?r ++;
 ? ? ? ?t ++;
 ?  }
?
 ? ?t = 0;
 ? ?int templeft = left;
 ? ?while (templeft <= right){
 ? ? ? ?array[templeft] = temp[t];
 ? ? ? ?t ++;
 ? ? ? ?templeft ++;
 ?  }
}
?
?
public static void sort(int[] array,int left,int right,int[] temp){
 ? ?if (left < right){
 ? ? ? ?int mid = (left + right) /2;
 ? ? ? ?// 左边
 ? ? ? ?sort(array,left,mid,temp);
?
 ? ? ? ?// 右边
 ? ? ? ?sort(array,mid+1,right,temp);
?
 ? ? ? ?merge(array,left,mid,right,temp );
 ?  }
}

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

六、快速排序（Quick Sort）

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

private static int partition(int[] array, int left, int right) {
?
 ? ?int low = left;
 ? ?int high = right;
 ? ?int pivot = array[low];
 ? ?while (low < high) {
 ? ? ? ?while (array[high] >= pivot && low < high) {
 ? ? ? ? ? ?high--;
 ? ? ?  }
?
 ? ? ? ?if (low < high) {
 ? ? ? ? ? ?array[low] = array[high];
 ? ? ? ? ? ?low++;
 ? ? ?  }
?
 ? ? ? ?while (array[low] <= pivot && low < high) {
 ? ? ? ? ? ?low++;
 ? ? ?  }
?
 ? ? ? ?if (low < high) {
 ? ? ? ? ? ?array[high] = array[low];
 ? ? ? ? ? ?high--;
 ? ? ?  }
?
 ?  }
?
 ? ?array[low] = pivot;
?
 ? ?return low;
}
?
private static void sort(int[] array, int left, int right) {
 ? ?if (left < right) {
 ? ? ? ?int index = partition(array, left, right);
?
 ? ? ? ?sort(array, left, index - 1);
?
 ? ? ? ?sort(array, index + 1, right);
?
 ?  }
}
?
 // 重载
private static void sort(int array[]) {
 ? ?int left = 0;
 ? ?int right = array.length - 1;
 ? ?sort(array,left,right);
}

七、基数排序（Radix Sort）

基数排序的排序思路是这样的：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……
排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。
由于某位数（个位/十位….，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了

public static void sort(int[] arr) {
?
 ? ?int max = arr[0];
 ? ?for (int i = 0; i < arr.length; i++) {
 ? ? ? ?if (arr[i] > max) {
 ? ? ? ? ? ?max = arr[i];
 ? ? ?  }
 ?  }
 ? ?int maxlength = (max+"").length();
 ? ?int[][] bucket = new int[10][arr.length];
?
 ? ?int[] bucketindex = new int[10];
?
 ? ?for (int i = 0 ,n = 1; i < maxlength ; i ++,n*=10) {
?
 ? ? ? ?for (int j = 0; j < arr.length; j++) {
 ? ? ? ? ? ?int digit = arr[j] /n % 10;
 ? ? ? ? ? ?bucket[digit][bucketindex[digit]] = arr[j];
 ? ? ? ? ? ?bucketindex[digit]++;
 ? ? ?  }
?
 ? ? ? ?int index = 0;
 ? ? ? ?for (int k = 0; k < bucketindex.length; k++) {
 ? ? ? ? ? ?if (bucketindex[k] != 0) {
 ? ? ? ? ? ? ? ?for (int l = 0; l < bucketindex[k]; l++) {
 ? ? ? ? ? ? ? ? ? ?arr[index] = bucket[k][l];
 ? ? ? ? ? ? ? ? ? ?index++;
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
?
 ? ? ? ? ? ?bucketindex[k] = 0;
 ? ? ?  }
 ?  }
?
}