[数据结构与算法]堆排序、归并排序、快速排序

堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序是基于堆这种数据结构实现的，什么是堆呢？首先，堆是一棵完全二叉树，其次根据性质不同可以分为以下两种：

• 大根（顶）堆：每个结点的值均大于等于它的两个孩子结点的值
• 小根（顶）堆：每个结点的值均小于等于它的两个孩子结点的值

显然，大根堆的堆顶具有整个堆中最大的结点值，小根堆的堆顶具有整个堆中最小的结点值。下面我将基于大根堆（小根堆也是可以的）实现堆排序。
大根堆排序的思想是：

1. 首先将整个待排序数组（假设长度为n）视为一个完全二叉树，然后将其调整为一个大根堆；
2. 交换堆顶与堆尾两个元素，然后把堆尾（严格来说此时它已不是堆了，为了方便还这么叫吧）从堆中断开，再把剩余的完全二叉树调整为一个新的大根堆；
3. 不断重复前面两部直到堆为空，此时排序完成。

很明显堆排序的核心就是如何把一个完全二叉树调整为堆，下面来分析以下：
一棵完全二叉树中，什么样的顶点需要被调整呢？当然是他的孩子节点大于它本身时，显然叶子节点不需要被调整，只有分支结点需要被调整，当我们发现一个需要调整的结点时，非常简单，只需要将它与它结点值较大的那个孩子交换位置即可,每完成一次调整，被换下去的那个结点有可能再次成为一个需要被调整的结点，所以我们需要不断向下检查直到被换下去的结点不满足调整的条件。根据完全二叉树的性质，编号从1~floor(n/2)(floor(a)表示对a向下取整)结点为分支结点。
下面是一个堆排序例子的过程：

实现代码

public static void heapSort(int[] A){
    //先将原数组调整为一个堆
    buildMaxHeap(A);
    for (int i = A.length;i>1;i--){
        //swap前i表示堆的节点个数，也即堆中最后一个节点的编号，所以其下标为i-1
        //此时堆顶也就是编号为1下标为0的元素为堆中最大的元素，将其交换到堆的末尾
        //此时堆中最大元素处在堆的末尾处，然后将此时编号为1到i-1的元素视为一个新的堆
        //此时从编号i到数组末尾都是已排序好的元素，不断重复此过程，每次都可以在未排序序
        //列(也就是我们的堆)中选出一个最大的元素，最终完成排序

        swap(A,i-1,0);
        新的堆大概率不符合堆的定义，所以需要对其重新调整
        heapAdjust(A,1,i-1);
    }
}
private static void swap(int[] A,int a,int b){
    //交换数组A中下标为a和b的两个元素
    A[a] = A[a]^A[b];
    A[b] = A[a]^A[b];
    A[a] = A[a]^A[b];
}
private static void buildMaxHeap(int[] A){
    for (int i = A.length/2; i > 0; i--){
        //从最后一个分支节点（根据完全二叉树的性质其编号为节点总数/2）逆向开始调整堆
        //i是节点编号不是下标，数组标为为编号-1
        heapAdjust(A,i,A.length);
    }
}
private static void heapAdjust(int[] A,int k,int len){
    /**堆调整算法
     * k：表示被调整的堆的根节点编号,其下标为k-1
     * len：表示待调整的堆的最后一个节点编号
     */
    int root = A[k-1];  //第k个元素的下标为k-1

    for (int i = 2*k; i<=len; i*=2){
        //第k个节点的左孩子编号为2k，其下标为2k-1
        //此时i为左孩子编号其下标为i-1
        if (i + 1 <= len && A[i] > A[i-1]){
            //i+1为有孩子编号，其下标为i
            i = i+1;    //如果有孩子大于左孩子则让i指向有孩子编号
        }
        //此时i一定是两个孩子中较大的那的的编号
        if (root > A[i-1]){
            //如果根节点大于两个孩子节点，则不用再继续调整
            break;
        } else{
            //否则讲较大的孩子节点移动到父节点上
            A[k-1] = A[i-1];
            //修改k值以便继续向下筛选
            //此时
            k = i;
        }
    }
    A[k-1] = root;
}

归并排序

**归并排序（Merge Sort）**是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

"归并"的含义是将两个或两个以上的有序表合成一个新的有序表。假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到floor(n/2)个长度为2或1的有序表；继续两两归并······，如此重复，直到合并成一个长度为n的有序表为止。下面是动画演示：

实现代码

public static void mergeSort(int[] A){
    //归并排序，给mSort外面套个壳子，调用起来方便
    //先初始化辅助数组
    Sort.B = new  int[A.length];
    mSort(A,0,A.length-1);

}
private static void mSort(int[] A,int low,int high){
    //归并排序
    if (low < high){
        int mid = (low + high) / 2;
        mSort(A,low,mid);
        mSort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}
private static void merge(int[] A,int low,int mid,int high){
    //首先将A数组中从low到high的元素复制到B数组对应位置
    for (int i = low; i <= high; i++) {
        B[i] = A[i];
    }
    //接下来对两个已经有序子数组进行归并，依次挑选较小的元素放入原数组
    int i,j,k;
    for (i = low,j = mid+1,k = i;i<=mid&&j<=high;k++){
        if (B[i] <= B[j]){
            A[k] = B[i++];
        }else {
            A[k] = B[j++];
        }
    }
    //然后将剩余那个子数组全部放回
    while (i<=mid){
        A[k++] = B[i++];
    }
    while (j<=high){
        A[k++] = B[j++];
    }
}

快速排序

快速排序（Quick Sort） 是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换直接消除多个逆序，则会大大加快排序的虚度。快速排序方法中的一次交换可以消除多个逆序。

算法步骤

在待排序的n个记录中任取一个记录（通常选取第一个记录）作为枢轴，设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换的前面，把所有大于pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢轴放置在分界处的位置。然后对左右两个子表重复上述过程，直到每一个子表只有一个记录时，排序完成。换句话说，就是每一趟排序都将一条记录放在了正确的位置上。（正确位置就是完成排序时它所处的位置）

具体步骤

1. 选择待排序表中第一个记录作为枢轴，保存在变量pivotkey中。附设两个指针low和high,初始时分别指向表的上界和下界（第一趟时，low = 0;high = nums.length）。
2. 从表的最右侧位置依次向左侧搜索，当找到第一个值小于pivotkey的记录时，将其移动到low处。具体操作是：当low < high时，若high所指记录大于等于pivotkey，则向左移动指针high；否则移动该记录。
3. 然后从表的最左侧位置依次向右侧搜索，找到第一个关键字大于pivotkey的记录，将其移动到high处。具体操作是：若low所指记录的值小于pivotkey，则向右移动指针low；否则移动该记录。
4. 重复步骤2和3，直至low和high。此时low和high的位置即为枢轴在此躺排序的最终位置，原表被分为两个子表。

下面是快速排序的动画演示：

代码实现

public class Sort {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 321, 34, 54, 56, 745, 7546,3,423,463,64,234,143421};
        quickSort(nums);
        for (int n : nums) {
            System.out.println(n);
        }
//        1
//        3
//        34
//        54
//        56
//        64
//        234
//        321
//        423
//        463
//        745
//        7546
//        143421
    }
    public static void quickSort(int[] nums) {
        qSort(nums,0,nums.length - 1);
    }
    public static void qSort(int[] nums,int low,int high) {
        if(low < high) {
            int pivotloc = partition(nums,low,high);
            qSort(nums,low,pivotloc - 1);
            qSort(nums,pivotloc+1,high);
        }

    }
    public static int partition(int[] nums,int low,int high) {
        int pivotkey = nums[low];  //用于比较的枢轴
        while (low < high) {
            while (low < high && nums[high] >= pivotkey) { high --; }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivotkey) { low ++;}
            nums[high] = nums[low];
        }
        nums[low] = pivotkey;
        return low;
    }
}

如有错误恳请指正