一、插入类算法
排序算法的稳定性：两个大小相等的元素排序前后的相对位置不变。{31，32，2} 排序后{2，31，32}，则称排序算法稳定
通用类：
public class Common {
public static int[] a = {48,62,35,77,55,14,35,98};
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void print(int[] a) {
for(int num : a) {
System.out.print(num + " ");
}
System.out.println();
}
}
1、插入排序
算法思想：将第i个元素插入到前i-1个已排好序的序列中。即要从i=2开始插入元素，默认第一个元素在已排好序的子集之中。
public static void insertSort(int[] a) {
for(int i = 1; i < a.length; i++) {
for(int j = i - 1; j>=0 ; j--) {
if(a[j+1]<a[j]) Common.swap(a, j+1, j);
else break;
}
}
}
对插入排序就是这么简单，想这么简单的代码面试时是不可能考的，主要理解算法的思想，例如考一个对链表进行插入排序。
时间复杂度：最好的情况待排序序列已经有序O(n)，最差的情况O(n2)。
空间复杂度：O(1)
稳定性：稳定
2、希尔排序
算法思想：希尔排序是对插入排序的改进，插入排序在待排序序列基本有序的情况下效率最高，希尔排序会进行组内插入排序，使得待排序数组基本有序，在进行插入排序。先以间隔为d元素划分一组，将集合划分成d组子集，例如{1，2，3，4，5，6}，d=2，则第一组{1，3，5}，第二组{2，4，6}；即下标i+k*d的都是一组。d的值一般取d = n/3 + 1，每次排序d缩小为原来的1/3。
public static void shellSort(int[] a) {
int d = a.length/3 + 1;
while(d >= 1) {
for(int i = d; i < a.length; i++) {
for(int j = i - d; j >=0 ; j = j-d) {
if(a[j+d]<a[j]) Common.swap(a, j+d, j);
else break;
}
}
d = d/3;
}
}
时间复杂度：O(n1.5)
空间复杂度：O(1)
稳定性：不稳定
二、交换类排序
1、冒泡排序
算法思想：每一轮和相邻元素比较，以第一个元素为开始，当前元素大于后一个元素则交换位置，当前元素小于后面元素则不动，这样没一轮都可以上浮一个最大的元素，最多进行n-1轮。
public static void bubbleSort(int[] a) {
boolean flag = true;
for(int i = 1; i <= a.length-1&&flag; i++) {
flag = false;
for(int j = 0; j < a.length - i; j++) {
if(a[j]>a[j+1]) {
Common.swap(a, j, j+1);
flag = true;
}
}
}
}
时间复杂度：最好的情况下，待排序列有序O(n)；最坏的情况下，倒序O(n2)
空间复杂度：O(1)
稳定性：稳定
2、快速排序
这个有点重要哦，Java类库里对基本类型的排序基本上都是使用快速排序，对象类型的元素都使用归并排序。
算法思想：基于分治法的思想
首先，进行一趟快排，选择第一个元素作为枢轴元素x，目的将小于x的移到x的左边，大于等于x的移到x的右边。
①low从左向右扫描，直到a[low] >= x，交换a[low]与a[high]
②high从右向左扫描，直到a[high] > x，交换a[low]与a[high]
③将x与a[high]交换
记住low永远指向大于等于x的元素，high永远指向小于x的元素
然后使用分治法，对x左边和右边元素分别进行快排。
public static void sort(int[] a, int low, int high) {
if(low>=high) return;
int l = low+1;
int h = high;
while(l<=h) {
if(a[l]>=a[low]) Common.swap(a, l, h--);
else l++;
}
Common.swap(a, low, h);
sort(a, low, h-1);
sort(a, h+1, high);
}
时间复杂度：一般情况O(nlogn)，最坏的情况待排序列有序O(n2)
空间复杂度：使用了递归栈O(logn)
稳定性：不稳定
3、三向切分排序
这是快速排序的演变版本，多了一个指针维护与枢轴相等的元素
public static void sort1(int[] a, int low, int high) {
if(low>=high) return;
int l = low;
int i = low+1;
int h = high;
while(i<=h) {
if(a[i]>a[low]) Common.swap(a, i, h--);
else if(a[i]<a[low]) Common.swap(a, i++, l++);
else i++;
}
sort1(a,low,l-1);
sort1(a,h+1,high);
}
时间复杂度：O(nlogn)
空间复杂度：O(logn)
稳定性：不稳定
4、利用一趟快排寻找第K大或第K小元素
private static int partition(int[] a, int low, int high) {
int l = low+1;
int h = high;
while(l<=h) {
if(a[l]>=a[low]) Common.swap(a, l, h--);
else l++;
}
Common.swap(a, low, h);
return h;
}
public static int select(int[] a, int k) {
int l = 0;
int h = a.length-1;
while(l<h) {
int min = partition(a,l,h);
if(min >= k-1) h = min;
else l = min+1;
}
return a[h];
}
时间复杂度：O(n)排序算法中能够在线性时间复杂度内解决问题的只有切分快速选择和桶排序了。
空间复杂度：O(1)
三、归并排序
这个也重要哦，因为有点难所以就很重要，面试的时候总不是拿几个大家都会的简单题考吧，考的一定是难题。
算法思想：基于分治法的算法思想
合并两个排好序的子集，然后递归调用，看程序啪
public static void sort(int[] a, int low, int high) {
if(low>=high) return;
int mid = (low + high) >>> 1;
int l1 = low;
int l2 = mid + 1;
int i = low;
sort(a,low,mid);
sort(a,mid+1,high);
int[] temp = Arrays.copyOf(a, a.length);
while(l1<=mid&&l2<=high) {
if(temp[l1]<=temp[l2]) a[i++] = temp[l1++];
else a[i++] = temp[l2++];
}
while(l1<=mid) {
a[i++] = temp[l1++];
}
while(l2<=high) {
a[i++] = temp[l2++];
}
}
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
四、堆排序
堆排序真的是很少用，排序重点应该在排序上面，而堆排序重点在建堆上。
堆排序最主要的操作是重建堆
//重建堆
private static void sift(int[] a, int start, int end) {
int i = start;//始终指向当前根
int j = 2*i;//指向当前根的左孩子
int x = a[start];
while(j<=end) {
//有右孩子，且右孩子值大，搜索右子树
if(j+1<=end&&a[j+1]>a[j]) j++;
if(x>=a[j]) break;
else {
Common.swap(a, i, j);
i = j;
j = 2*i;
}
}
}
创建堆自下而上，从第一个非叶子节点开始创建堆
//创建堆
public static void create(int[] a) {
int i = (a.length-1)/2;
for(; i >= 1; i--) {
sift(a,i,a.length-1);
}
}
堆排序
public static void sort(int[] a) {
create(a);
for(int i = a.length-1; i > 1; i--) {
Common.swap(a, 1, i);
sift(a,1,i-1);
}
}
时间复杂度：O(nlogn)
空间复杂度：O(1)
考察形式：215. 数组中的第K个最大元素
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num : nums) {
pq.add(num);
if(pq.size() > k) pq.poll();
}
return pq.peek();
}
使用优先级队列PriorityQueue创建一个小顶堆，确保队列中只有K各元素，每次poll都是去掉小的元素，剩下k就是k个最大的元素，队头就是我们要找的答案。
当然我们也可以使用切分选择算法，但是都没有Java类库中自带的排序算法高效。
五、选择排序
算法思想：从剩下的元素集合A中选取一个最小的和A中的第一个元素交换，直至有序
public static void sort(int[] a) {
for(int i = 0; i < a.length; i++) {
int k = i;
for(int j = i; j < a.length; j++) {
if(a[j]<a[k]) k = j;
}
if(k!=i) Common.swap(a, i, k);
}
}
时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：不稳定
六、桶排序
算法思想：用空间换时间，使用了哈希表。
看个题就明白了
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> hash = new HashMap<>();
LinkedList<Integer> ans = new LinkedList<>();
for(int num : nums) {
int v = hash.containsKey(num) == true ? hash.get(num) + 1 : 1;
hash.put(num,v);
}
LinkedList<Integer>[] buckets = new LinkedList[nums.length+1];
for(Map.Entry e : hash.entrySet()) {
int f = (Integer)e.getValue();
if(buckets[f] == null) buckets[f] = new LinkedList<Integer>();
buckets[f].add((Integer)e.getKey());
}
for(int i = nums.length; i >= 1 ; i--) {
if(buckets[i]==null) continue;
while(k > 0 && buckets[i].size() > 0) {
ans.add(buckets[i].poll());
k--;
}
}
return ans;
}
使用hash表统计频率，以频率为数组下标放入桶中，这样就利用数组按照频率自然的由低到高排序
时间复杂度：只有O(n)哦，要是排序题中出现线性时间复杂度，就妥妥的桶排序。
空间复杂度：O(n)
七、总结
| 类别 | 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|---|---|
| 插入类 | 插入排序 | √ | O(n)~O(n2) | O(1) | |
| 希尔排序 | × | O(n1.5) | O(1) | 对直接插入排序的改进 | |
| 交换类 | 冒泡排序 | √ | O(n)~O(n2) | O(1) | |
| 快速排序 | × | O(nlogn)~O(n2) | O(logn) | 对冒泡的改进 | |
| 三向快排 | × | O(nlogn) | O(logn) | 适用于有重复元素的 | |
| 选择类 | 选择排序 | × | O(n2) | O(1) | |
| 堆排序 | × | O(nlogn) | O(1) | 对选择排序的改进 | |
| 其他类 | 归并排序 | √ | O(nlogn) | O(n) | |
| 桶排序 | × | O(n) | O(n) | 唯一线性时间 |
1、稳定的算法，只有插入排序、冒泡排序、归并排序
2、时间复杂度稳定在O(nlog)常用的就是快排和归并
3、桶排序，唯一的线性时间