排序

算法稳定性：

假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变。即在原序列中，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];
}