1、直接插入排序与希尔排序
- 直接插入排序
直接插入排序算法步骤分为两步：
首先，将第一个元素当成一个有序的序列，然后将第二个元素到最后一个元素当成是一个未排序的序列。
其次，扫描未排序的序列，将扫描到的每个元素插入到有序序列的适当位置。也就是说它会和有序序列的元素从末尾到头部依次比较，并找到自己的位置。
Java实现：
public static void insertSort(int[] array) {
int size = array.length;
for(int i=1; i<size; i++) { //i从1开始表明我们假设a[0]已经放好了位置
int temp = array[i];
int j;
//比较当前元素和该元素之前所有元素的大小，将比该元素大的后移
for(j=i-1; j>=0 && a[j]>temp; j--) {
a[j+1] = a[j];
}
a[j+1] = temp; //插入到正确的位置
}
}
总结分析：
当最好的情况，也就是排序的表本身是有序的，那么我们比较的次数就是n-1次，没有移动记录，此时时间复杂度是O(n)。当最坏的情况，即待排序的表是逆序的情况下，此时的时间复杂度是O(n^2)。 平均情况下，时间复杂度是O(n^2)。
从空间上来看，它只需要一个辅助的空间来进行临时数据的存储，空间复杂度是O(1)。
直接插入排序的稳定性分析：由于直接插入排序比较的是相邻的元素，而且也不存在跳跃性比较和交换，所以它是一种稳定的排序方法。
- 希尔排序
希尔排序是对直接插入排序的改进。我们可以将待排序序列分割为若干个子序列，此时子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。
对于上面的解释中的若干个子序列的定义我们需要转换一下思想：
我们将相距某个“增量”的记录组成一个子序列。如下表所示，当增量为4时，9和3，1和7，5和4，8和6，2组成子序列，在子序列中将小的排在前面，大的排在后面。排完一轮后，增量变化为2时，然后下标0和2，下标1和3，...组成子序列，又排完一轮后，增量变化为1，这个时候希尔排序变成了直接插入排序，这个时候序列经过前面几轮的排序已经变得基本有序了，所以使用直接插入排序变得很高效。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| *** | 9 | 1 | 5 | 8 | 3 | 7 | 4 | 6 | 2 |
Java实现：(将直接插入排序的1使用increment代替，因为当increment为1时就是直接插入排序)
public static void shellSort(int[] array) {
int size = array.length;
int increment = size;
while(increment > 1) {
increment = increment / 3 + 1; //增量序列的一种获取算法，也可以用其他的算法
for(int i=increment; i<size; i++) {
int temp = array[i];
int j;
for(j=i-increment; j>=0 && a[j]>temp; j-=increment) {
a[j+increment] = a[j];
}
a[j+increment] = temp;
}
}
}
总结分析：
大量的数据表明，在最好的情况下，希尔排序的时间复杂度是O(n^1.3)。 最坏的情况是O(n^2)。 平均情况是O(nlog2n)~O(n^2)。
空间复杂度也是O(1)。
稳定性方面由于是跳跃性的移动，所以希尔排序是一种不稳定的排序方法。
2、冒泡排序与快速排序
- 冒泡排序
冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
Java实现：
public static void bubbleSort(int[] array) {
boolean swapped = true; //swapped作为标记
int length = array.length;
for (int i = 0; swapped && i < length - 1; i++) { //若swapped为false则退出循环，注意i的值是小于length-1的
swapped = false; //初始化为false
for (int j = length - 1; j > i; j--) { //从后往前循环
if (array[j] < array[j - 1]) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
swapped = true; //如果数据有效，swapped为true
}
}
}
}
总结分析
最好的情况下，也就是排序的表本身是有序的，那么我们只是比较而没有数据交换，可以判断出就是n-1次比较，没有数据交换，时间复杂度为O(n)。当最坏的情况下，即待排序的表是逆序的情况下，此时需要比较n-1+n-2+......+2+1=n(n-1)/2次，并作等数量级的记录移动，因此，总的时间复杂度是O(n^2)。
整个排序过程中只用到了一个临时变量来存储待要交换的数据，故空间复杂度为O(1)。
冒泡排序是因为是相邻的元素两两比较和交换，故冒泡排序是一种稳定的排序方法。
- 快速排序
快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分继续进行排序，以达到整个序列有序的目的。
Java实现：
public static void quickSort(int[] array) {
int low = 0, high = array.length - 1;
int pivot; //枢纽，中心点
while(low < high) {
pivot = partition(array, low, high); //将array分为low到pivot - 1，pivot+1到high两部分
quickSort(array, low, pivot -1); //对低字表递归排序
low = pivot + 1; //尾递归
}
}
public static int partition(int[] array, int low, int high) {
int m = (low + high) / 2; //数组中间元素的下标
if(array[low] > array[high]) {
swap(array, low, high); //交换左端与右端的元素，保证左端较小
}
if(array[m] > array[high]) {
swap(array, m, high); //交换中间和右端的元素，保证中间较小
}
if(array[m] > a[low]) {
swap(array, m, low); //交换中间与左端数据，保证左端较大
}
//此时array[low]已经是整个序列左中右三个关键字的中间值
int pivot = a[low];
while(low < high) {
while(low < high && array[high] >= pivot) {
high--;
}
swap(array, low, high);
while(low < high && array[low] <= pivot) {
low++;
}
swap(array, low, high);
}
return low; //此时low=high，返回其之一就行
}
总结分析：
快速排序的调用，时间性能取决于快速排序递归的深度。在最优的情况下，partition每次都划分得很均匀，此时时间复杂度为O(nlogn)。在最坏的情况下，待排序序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它是一颗斜树，此时的时间复杂度为O(n^2)。 平均情况下，时间复杂度为O(nlogn)。
空间复杂度主要是递归造成的栈的使用，最好情况下，递归树的深度为logn，其空间复杂度为O(logn)。最坏情况下，需要进行n-1次递归调用，其空间复杂度为O(n)。平均情况下，空间复杂度也为O(logn)。
由于快速排序关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
3、简单选择排序与堆排序
- 简单选择排序
简单选择排序的基本思想是：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换。
Java实现
public static void simpleSelectSort(int[] array) {
int length = array.length;
int min;
for (int i = 0; i < length; i++) {
min = i;
for (int j = i+1; j < length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
if (min != i) {
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}
}
- 堆排序
堆排序是对简单选择排序的一种改进。堆是具有下列性质的完全二叉树：每个节点的值都大于或者等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于等于其左右孩子节点的值，称为小顶堆。
堆排序的基本思想是：将待排序的序列构造成一个大顶推。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是讲起与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩下的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便得到一个有序的序列。
Java实现：
public static void heapSort(int[] array, int n) {
//这里的数组从第一位开始才有值，主要是为了对应完全二叉树的性质。n表示有值的元素的长度
for(int i = n / 2; i > 0;i--) {
heapAdjust(array, i, n);
}
for (int i = n; i > 1; i--) {
swap(array, 1, i); //交换数组两个下标的数
heapAdjust(array, 1, i - 1);
}
}
public static void heapAdjust(int[] a, int s, int m) {
int i;
int temp = a[s]; //将第一个非终端结点保存
for (i = 2 * s; i <= m; i*=2) {
if (i < m && a[i] < a[i + 1]) { //i<m表明存在左、右孩子
i++; //右孩子比较大，则i+1，否则i不变
}
if (temp >= a[i]) { //比较结点和较大的记录，若结点较大，则退出for循环，不用交换数据
break;
}
//否则将a[i]插入到结点的位置
a[s] = a[i];
s = i; //由于有数据交换，破坏了以位置s为根节点的堆的性质，于是将i赋值给s
}
a[s] = temp; //最后将temp插入到a[s]的位置
}
