算法稳定性：
假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变。即在原序列中，ri=rj,且ri在rj之前，而在排序后，ri仍在rj之前，则称这种排序算法是稳定的。
- 算法稳定性的重要性
在实际的应用中，我们交换的不一定只是一个数，而可能是一个很大的对象，交换元素存在一定的开销。
排序分类：
排序分类
排序算法
插入排序
插入排序由N-1趟排序组成。对于i=1到N-1趟，插入排序保证从位置0到位置i上的元素已经处于排过序的状态。
如下图：
插入排序.png
具体实现：
public class InsertSort {
public static void main(String[] args){
int[] arr = {34,8,64,51,32,21};
System.out.println("Before sort:");
printArray(arr);
System.out.println("After insert sort:");
insertionSort(arr);
printArray(arr);
}
public static void printArray(int[] a){
for (int i = 0; i < a.length; i ++){
System.out.print(a[i] + " ");
}
System.out.println();
}
/**
* 实现思路：从第二个位置开始遍历，保证目标数左边是排序好的，目标数不断
* 往右边找，直到找到合适的位置放入。
* @param a
*/
public static void insertionSort(int[] a){
int j;
//从第二个位置开始
for (int i = 1; i < a.length; i ++){
//设置临时变量
int tmp = a[i];
//将该位置不断往左移，直到当前的数不大于该数
for (j = i; j > 0 && tmp < a[j-1] ; j--){
//将数往右移，为目标数腾一个位置
a[j] = a[j - 1];
}
//找到位置，将目标数放入
a[j] = tmp;
}
}
}
输出结果：
Before sort:
34 8 64 51 32 21
After insert sort:
8 21 32 34 51 64
评价：
插入排序的复杂度为O(N2)，但算法是稳定的。
希尔排序：
先将序列按Gap划分为元素个数相同的若干数组，使用直接插入排序法进行排序，然后不断缩小Gap直至1，最后使用插入排序完成排序。希尔排序实际上是插入排序的增强版。
如下图：
希尔排序.png
实现过程：
public static void shellSort(int[] a){
int j;
//设置gap，定义gap/2变化
for (int gap = a.length / 2; gap > 0; gap /= 2){
System.out.println("第" + gap + "趟排序：");
//每gap间进行插入排序
for (int i = gap; i < a.length; i ++){
int tmp = a[i];
for (j = i; j >= gap && tmp < a[j-gap]; j -= gap){
a[j] = a[j-gap];
}
a[j] = tmp;
}
printArray(a);
}
}
输出结果：以第一个位置进行比较
希尔排序.png
评价：
- 希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(N²)，而Hibbard增量的希尔排序的时间复杂度为O(N3/2)。
- 希尔排序是不稳定的算法。
冒泡排序
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作就是重复地进行直到没有再需要交换，也就是说数列已经排序完成。
如下图：
冒泡排序.png
具体实现：
public static void bubbleSort(int[] a){
int temp;
//遍历N-1趟
for (int i = 0; i < a.length - 1; i ++){
//每一躺保证该趟的最后一个元素为最大
for (int j = 0; j < a.length - i - 1; j ++){
if (a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
评价：
- 冒泡排序与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最好的情况，冒泡排序需要
O(n^{2})次交换，而插入排序只要最多O(n)。 - 冒泡排序是稳定的。
快速排序
使用分治法策略来把一个序列分为两个子序列。
- 从数列中挑出一个元素，称为“基准”。
- 重新排序数列，所有比基准小的元素放在基准的左边，所有比基准大的元素放在基准的右边。
- 对基准的左边和右边两个子集，不断重复前面两个步骤，直到所有子集只剩下一个元素。
如下图：
快速排序.png
具体实现：
public class QuickSort {
private int[] arr;
public QuickSort(int[] arr){
this.arr = arr;
}
//打印数组
public void printArray(){
for (int i = 0; i < arr.length; i ++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
public void quick_sort(){
quick_sort_recursive(0, arr.length - 1);
}
private void quick_sort_recursive(int start, int end){
//只有一个元素的情况，直接返回
if (start >= end) return;
//取最后一个元素作为基准
int mid = arr[end];
//设置左右边
int left = start;
int right = end - 1;
//进行比较交换
while (left < right){
//左边的数往右找，直到找到大于基准的数
while (arr[left] <= mid && left < right)
left ++;
//右边的数往左找，直到找到小于基准的数
while (arr[right] >= mid && left < right)
right --;
//交换两个数
Swap(left,right);
}
//若中间元素大于基准，则进行交换
if (arr[left] > arr[end])
Swap(left,end);
//否则left++，目的是排除掉中间元素
else
left ++;
//递归左右两边
quick_sort_recursive(start,left-1);
quick_sort_recursive(left+1, end);
}
//交换元素
private void Swap(int x, int y){
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
评价：
快速排序的时间复杂度为O(nlgn)，最坏情况为O(n2)，其空间复杂度为O(lgn)。
快速排序的算法是不稳定的。
选择排序
首先在未排序序列中找到最大(小)元素，存放到排序序列中的起始位置，然后，再从剩余未排序元素中继续寻找最大(小)元素，然后放到已排序序列的末尾。以此类推，直到所有元素排序完毕。
实现如下：
private static void selection_sort(int[] arr){
int i,j,min,temp,len = arr.length;
for (i = 0; i < len - 1; i ++){
//记录当前元素
min = i;
//获取到未排序的序列中找到最小元素的位置
for (j = i + 1; j < len; j ++)
if (arr[min] > arr[j])
min = j;
//将最小的元素放在起始位置
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
评价：
- 选择排序的时间复杂度为O(n2)
- 选择排序是稳定的。
堆排序
利用堆这种数据结构设计的一种排序算法。堆积是一个近似的完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或大于)它的父节点。
堆节点的访问：
a. 父亲节点i 的左子节点的位置(2i+1)
b. 父节点i的右子节点的位置(2i+2)
c. 子节点的父节点位置floor((i-1)/2)堆的操作：
a. 创建最大堆：将堆所有数据重新排序
b. 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
c. 堆排序：移除位于第一个数据的根节点，并做出最大堆调整的递归运算具体实现过程：
http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
- 具体实现方法：
public class HeapSort {
private int[] arr;
public HeapSort(int[] arr){
this.arr = arr;
}
//进行排序
public void sort(){
//建立最大堆
buildMaxHeap();
//移除顶点，并调整堆顺序
for (int i = arr.length - 1; i > 0; i --){
//将顶点与最后的元素（最小值）交换
swap(i,0);
//然后调整堆顺序
maxHeapify(0,i);
}
}
private void swap(int i , int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//建立最大堆，递归实现
private void maxHeapify(int index, int len){
//默认父节点为最大值
int max = index;
//获取左右孩子节点位置
int left = (index * 2) + 1;
int right = left + 1;
//若左孩子大于父亲，则赋值左孩子
if (left < len && arr[max] < arr[left])
max = left;
//若右孩子大于父亲，则赋值右孩子
if (right < len && arr[max] < arr[right])
max = right;
//若需要更新父节点，则交换，并调整
if (max != index){
swap(index, max);
maxHeapify(max,len);
}
}
//建立最大堆
private void buildMaxHeap(){
//设置根节点位置
int parent = arr.length/2 - 1;
//从根开始创建堆
for (int i = parent; i >= 0; i --){
maxHeapify(i,arr.length);
}
}
private void printArray(int[] a){
for (int i = 0; i < a.length; i ++){
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args){
int[] arr = {81,94,11,96,12,35,17,95,28,58,41,75,15};
System.out.println("Before sort:");
HeapSort hs = new HeapSort(arr);
hs.printArray(arr);
hs.sort();
System.out.println("After heapSort sort:");
hs.printArray(arr);
}
}
输出结果：
Before sort:
81 94 11 96 12 35 17 95 28 58 41 75 15
After heapSort sort:
11 12 15 17 28 35 41 58 75 81 94 95 96
归并排序
将数组划分为若干个部分进行排序，再将这些排序好的部分合并
实现过程：
归并排序
实现方法：
/**
* 实现归并排序
* @param arr 原始数组
* @param rs 结果数组
* @param start 开始位置
* @param end 结束位置
*/
private static void merge_sort_recursive(int[] arr, int[] rs, int start, int end){
if (start >= end) return;
//划分为两段，并分别设置这两段的始末位置
int len = end - start;
int mid = len / 2 + start;
int s1 = start, e1 = mid;
int s2 = mid + 1, e2 = end;
//对这两段分别进行递归操作，划分数组
merge_sort_recursive(arr,rs,s1,e1);
merge_sort_recursive(arr,rs,s2,e2);
//进行合并数组
int k = start;
//从两个划分的数组中选取较小的数放入结果数组中
while (s1 <= e1 && s2 <= e2)
rs[k++] = arr[s1] < arr[s2] ? arr[s1++] : arr[s2++];
//对于未排完的，直接放入结果数组中
while (s1 <= e1)
rs[k++] = arr[s1++];
while (s2 <= e2)
rs[k++] = arr[s2++];
//赋值给原始数组
for (k= start; k <=end; k++)
arr[k] = rs[k];
}
