一、排序：
1、常用的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序等。
2、根据时间复杂度的分类：
冒泡排序、插入排序、选择排序 O(n^2)。基于比较。
快速排序、归并排序 O(nlogn)。基于比较。
计数排序、基数排序、桶排序 O(n)。不基于比较。
二、分析一个排序算法的方法：
1、排序算法的执行效率：
a、最好情况、最坏情况、平均情况时间复杂度。
b、时间复杂度的系数、常数 、低阶。
c、比较次数和交换（或移动）次数。
2、排序算法的内存消耗。（原地排序算法，就是特指空间复杂度是O(1)的排序算法。）
3、排序算法的稳定性。
三、有序度、逆序度、满有序度：
1、有序度：有序度是数组中具有有序关系（默认从小到大为有序）的元素对的个数。有序元素对用数学表达式表示：有序元素对： a[i] <= a[j], 如果i < j。
2、逆序度：逆序度是数组中具有逆序关系（默认从小到大为有序）的元素对的个数。逆序元素对用数学表达式表示：逆序元素对： a[i] > a[j], 如果i < j。
3、满有序度：数组是完全有序的，此时的有序度就是满有序度。
4、三者之间关系：逆序度 = 满有序度 - 有序度
四、冒泡排序（Bubble Sort）：
1、原理：只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
2、冒泡排序原理示意图：
3、实现代码（以从小到大排序为例）：
// 冒泡排序， a表示数组， n表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {//n个数，所以要比较n次
//提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {//每一次比较都要将目前最大的移到在后面
if (a[j] > a[j+1]) { //交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; //表示有数据交换
}
}
if (!flag) break; //没有数据交换，提前退出
}
}
4、相关问题：
a.冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
b.冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
c.冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n^2)。平均情况下的时间复杂度是O(n^2)。
五、插入排序（Insertion Sort）：
1、原理：首先，我们将数组中的数据分为两个区间， 已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
2、插入排序原理示意图：（排序的数据是4， 5， 6， 1， 3， 2，其中左侧为已排序区间，右侧是未排序区间）
3、实现代码（以从小到大为例）：
// 插入排序， a表示数组， n表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
//查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; //数据移动
} else {
break;
}
}
a[j+1] = value; //插入数据
}
}
4、相关问题：
a、插入排序是原地排序算法吗？
插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。
b、插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
c、插入排序的时间复杂度是多少？
如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。最好时间复杂度为O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n^2)。在数组中插入一个数据的平均时间复杂度是O(n)。对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n^2)。
六、选择排序（Selection Sort）：
1、原理：分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
2、选择排序原理示意图：
3、实现代码：
public static void SelectionSort(int[] arr){
int n = arr.length;
for (int i = 1; i < n; ++i) {
int value = arr[i];
int j = 0;//插入的位置
for (j = i-1; j >= 0; j--) {
if (arr[j] > value) {
arr[j+1] = arr[j];//移动数据
} else {
break;
}
}
arr[j+1] = value; //插入数据
}
}
4、相关问题：
a、插入排序是原地排序算法吗？
选择排序空间复杂度为O(1)，是一种原地排序算法。
b、插入排序是稳定的排序算法吗？
不是，选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。比如5， 8， 5， 2， 9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。
c、插入排序的时间复杂度是多少？
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n^2)。
七、三种排序算法的对比：
八、相对于冒泡排序，插入排序的优点：
冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个。
