排序算法总结
总结：口诀1：心情不稳定，快些选一堆好朋友来聊天吧! 【不稳定：快速排序、希尔排序、选择排序、堆排序】
口诀2：快些以O(nlogn)的速度归队！【快速，希尔，归并，堆 ## 除了桶排序其他的时间复杂度为n*n】
1.冒泡排序【 点击可以查看专题博客 】
将相邻的两个数做比较，如果不满足排序要求，则交换位置。具体有两种，一种就是从前往后相邻的比较，假设按照增序排，第一个跟第二个比，如果第一个大，则交换。然后将第二个和第三个位置的比。以此类推，一直比下去，这样一个轮回，可以将最大的那个数字送到最后一个位置。然后比较余下的。因此也称这种为“沉底法”。还有一种类似，就是从后往前比较，就是所谓的“冒泡法”，每一个轮回，将最小的那个数字送到了第一个元素的位置。
冒泡核心代码：
for(i=0;i<len-1;i++)
for(j=len-1;j>i;--j){
if(a[j]<a[j-1]){
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
冒泡算法的改进：
记录每次交换的位置，当一次冒泡中无两个元素交换，则后面的部分已经有序，以后每轮比较不需要再次比较已经有序的部分。
2.选择排序
思想：每一趟找到一个最小元素，放入第一个位置，第二趟找到次小元素放入第二的位置，每一次将最小元素放入temp,与其他元素比较。而不是相邻的两两比较。时间复杂度O(n^2),空间复杂度O（1）。
关键代码：
for(int i=0;i<n;i++){
int temp=a[i];//假定未排序中的第一个时最小的
int flag=i;//最小元素的位置
for(int j=i+1;j<n;j++){
if(a[j]<temp){
temp=a[j];
flag=j;
}
}
if(flag!=i){
a[flag]=a[i];
a[i]=temp;
}
}
3.插入排序
思想：从前往后遍历元素，每次将未排序的元素插入一个到已经排序的队列中。时间复杂度O（n^2）。
核心代码：
for(int i=0;i<a.length;i++){
int temp=a[i];//待插入的一个元素
int j=i;
if(a[j-1]>temp){//找到该插入的位置j
while(j>=1 && a[j-1]>temp){
a[j]=a[j-1];
j--;
}
}
a[j]=tenp;//将temp插入j位置；
}
二路归并：递归+合并。两个元素为一组排序后归并。【递归+分治思想】
时间复杂度O（n log n）
5.希尔排序
思想：选一个基准，从右往左扫，小的跟他交换，从从往右，比他大的再与他交换。最坏退化为冒泡，时间空间平均 O（n log n）;
8.基数排序（桶排序）
附稳定性和复杂度查询表：
