一 前言
本来要写树和图，这两块内容比较复杂，所以先梳理一下常用的排序算法。
二 排序算法的几个概念
2.1 排序算法的稳定性
对于排序算法的稳定性，之前看过《大话数据结构》这本书的解释，后来发现是有问题的，下面是维基百科给的定义，
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录 R和S，且在原本的列表中 R出现在 S之前，在排序过的列表中R也将会是在S之前。
——维基百科排序算法
举个例子，一个班的学生成绩表（原数据），现在按成绩排序，如果成绩相同时（小钱和小李），保持原来的顺序（小钱在前，小李在后），就是稳定的，否则是不稳定的。
- 原数据
| 学号 | 姓名 | 成绩 |
|---|---|---|
| 2 | 小赵 | 90 |
| 9 | 小钱 | 68 |
| 7 | 小孙 | 78 |
| 6 | 小李 | 68 |
- 不稳定排序
| 学号 | 姓名 | 成绩 |
|---|---|---|
| 2 | 小赵 | 90 |
| 7 | 小孙 | 78 |
| 6 | 小李 | 68 |
| 9 | 小钱 | 68 |
- 稳定排序
| 学号 | 姓名 | 成绩 |
|---|---|---|
| 2 | 小赵 | 90 |
| 7 | 小孙 | 78 |
| 9 | 小钱 | 68 |
| 6 | 小李 | 68 |
2.2 内部排序和外部排序
- 内部排序：排序过程中，数据存储在内存中，如基础排序算法——插入排序（直接插入和希尔排序）、选择排序（简单选择和堆排序）、交换排序（冒泡和快排）、归并排序。
- 外部排序：利用内存和外部存储处理超大数据集，Java8中引入了parallelSort，可以充分利用多CPU处理大数据集。
三 排序算法
3.1 冒泡排序
public void bubbleSort(int[] arrs){
if(arrs==null||arrs.length==0||arrs.length==1)return;
//总共n-1趟
for(int i=0;i<arrs.length-1;i++){
boolean isFlag=true;
//每一趟的右边会排好一个数字，所以无序区的总长度为length-1-i
for(int j=0;j<arrs.length-1-i;j++){
//交换位置
if(arrs[j]>arrs[j+1]){
int temp=arrs[j];
arrs[j+1]=arrs[j];
arrs[j]=temp;
isFlag=false;
}
}
if(isFlag) break;
}
}
3.2 直接插入排序
public void insertSort(int[] arrs){
if(arrs==null||arrs.length==0||arrs.length==1)return;
//1.一共n-1趟
for(int i=0;i<arrs.length-1;i++){
//每一趟对左边的有序区，从后往前比较，所以最大数为i+1;
for(int j=i+1;j>0;j--){
if(arrs[j-1]<=arrs[j}){
break;
}
int temp=arrs[j-1];
arrs[j-1]=arrs[j];
arrs[j]=temp;
}
}
}
3.3 快速排序
public qSort(int left,int rigth){
//定义左侧移动索引
int i=left;
//定义右侧移动索引
int j=right;
//取基准值；
int p=arrs[(i+j)/2];
while(i<=j){
while(arrs[i]<p)i++;
while(arrs[j]>p)j--;
if(i<j){
int temp=arrs[i];
arrs[i]=arrs[j];
arrs[j]=temp;
i++;
j--;
}else if(i==j){
i++;
}
}
qSort(left,j);
qSort(i,right);
}
代码地址：https://github.com/ywqyunshan/LearnCode/tree/master/src/com/iigeo/sort
参考文献
[1] 排序算法.维基百科
