排序
内部排序和外部排序：排序过程中，所有数据在内存中处理，不涉及数据的内、外存交换则称之为“内部排序”，反之，称为外部排序。
排序稳定性：若记录序列中有两个或两个以上关键字相等的记录，Ki == Kj(i != j)，且在排序前 Ri 先于 Rj(i < j),排序后的记录序列仍然是 Ri 先于 Rj, 则称排序算法是稳定的，否则是不稳定的。
在排序过程中通常需要进行两种基本操作：
- 对记录中的关键字大小进行比较
- 将记录从一个位置移动到另一个位置
比较次数和移动次数成为排序方法时间复杂度的评估标准。
插入排序
基本思想将线性表看成两部分，有序和无序，排序过程是每次从无序子表中取出一个元素将其插入到有序子表的正确位置。
算法设计
/**
* 插入排序
* @param a
*/
public static void insertSort(int a[]){
int temp, n = a.length;
for (int i = 0; i < n - 1; i++){
for (int j = i + 1; j > 0 ; j--){
if (a[j] < a[j-1]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
} else {
break;
}
}
}
}
时间复杂度分析为 O(n^2).
选择排序
基本思想：将线性表看成有序和无序两部分，排序过程是每次从无序表中选出最小的一个元素，将其添加到有序表的末尾。
算法设计
/**
* 选择排序
* @param a
*/
public static void selectSort(int a[]){
for (int i = 0; i < a.length; i++){
int minIndex = i;
for (int j = i + 1; j < a.length; j++){
if (a[j] < a[minIndex]){
minIndex = j;
}
}
if (i != minIndex){
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
时间复杂度分析O(n^2).
冒泡排序
冒泡排序是一种交换类排序方法。交换排序是根据序列中两个关键字的比较结果来交换在序列中的位置。冒泡排序的特点是关键字较大的记录向序列尾部移动，较小的向序列前部移动。
算法设计
/**
* 冒泡排序
* @param a
*/
public static void bubbleSort(int a[]){
int i, j, temp, n = a.length;
for (i = n - 1; i > 0; i--)
for (j = 0; j < i; j++){
if (a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
时间复杂度分析O(n^2).
快速排序
快速排序又称为分区交换排序，是目前已知的实测平均速度最快的一种排序方法，它是对冒泡排序方法的一种改进。
算法设计
时间复杂度分析
#归并排序