快速排序

思路：（升序）

  • 快速排序使用递归的思想，先在原数组中找一个基准值（要用一个变量保存起来），一般是第一个或者最后一个元素。（可以减少交换次数）
  • 使用两个指针（普通变量i,j即可）分别指向第一个和最后一个元素。
  • 如果选择第一个元素作为基准值，那么就从右边开始扫描，比较右指针指向的数与基准值的大小，如果小于基准值，那么将右指针指向的值赋给左指针（A[i]=A[j]，不用担心A[i]原来的值被覆盖，因为最开始左指针指向基准值，且用变量保存了。那右指针A[j]不需要变吗？不需要！按理说是要把基准值赋给A[j]，但是没有必要）然后左指针就右移动一位，并开始比较左指针与基准值的大小关系，如果大于基准值，就将左指针的值赋给右指针（A[j]=A[i]），然后右指针左移一位。重复操作，直到i=j，而i，j的值就是最终基准值的位置
  • 在扫描的过程中也就是移动指针时，左指针右移要找比基准值大的数，没找到就一直右移。右指针左移要找比基准值小的数，没找到就一直左移。最终就是要让小于基准值的数在左边，大于基准值的数在右边。

代码

/**
 * 递归调用
 * @param A       待排序数组
 * @param left    起始位置
 * @param right   结束位置
 */
public static void quickSort(int[] A, int left, int right) {
    int position;       //记录基准值所在下标
    if (left < right) {
        position = partition(A, left, right);
        quickSort(A, left, position);
        quickSort(A, position + 1, right);
    }
}


/**
 * 对子数组进行排序 最终返回基准值所在下标
 * @param A
 * @param left
 * @param right
 * @return
 */
public static int partition(int[] A, int left, int right) {
    int i = left, j = right;
    int basic = A[i];     //数组的最左边元素为基准值  基准值不参与交换
    do {
        while (j > i && A[j] >= basic) {  //取最左边元素为基准值 那么就从最右边开始扫描 找出右边比基准值小的元素
            j--;
        }
        if (j > i) {
            A[i] = A[j];  //交换 但只需把找到的元素赋给左边  因为左边的值用basic变量记录了
            i++;
        }
        while (i < j && A[i] <= basic) {     //然后就要从左边找比基准值大的元素
            i++;
        }
        if (i < j) {
            A[j] = A[i];             //也是只需要将找的的元素赋值给右边
            j--;
        }
    } while (i < j);
    A[i] = basic;      //基准值最终的位置
    return i;
}

时间复杂度

平均时间复杂度$O(n)=nlbn$

最差时间复杂度$O(n)=n^2$

堆排序

堆：用完全二叉树解释如下

  • 大根堆：根节点大于孩子节点
  • 小根堆：根节点小于孩子节点

大根堆最顶部节点一定是最大的，小根堆最顶部节点一定是最小的。其他节点间的大小关系是不确定的。

思路：（大根堆）

  • 初建堆 首先有一个初建堆的过程，将无序数组化为大根堆。先从最后一个根节点开始（完全二叉树结构中最后一个根节点的序号是$n/2$,向下取整，比如5个节点的完全二叉树，最后一个根节点的序号是2），调整根节点形成的子树。主要过程就是先看该根节点是否有左孩子（这个判断是个循环条件，刚开始进入循环，由于根节点是整个完全二叉树的最后一个根节点，肯定是有做孩子的，但在循环中，根节点会更新），如果有，再判断是否有右孩子，如果也有，那就比较一下左右孩子的大小，选出最大的与根节点进行交换。然后，将进行交换的孩子节点序号作为新的根节点，继续往下交换。当一趟交换完成后，从倒数第二个根节点开始重相同操作。直到所有根节点都完成交换。一次初建堆操作包含对所有根节点的处理，并会把最大值交换到最顶部位置。
  • 重建堆 由于初建堆操作把最大值交换到最顶部，所以可以把最大值与最后面部分的节点交换位置，并进行堆的重建，重建时，将第1至第n-1个数作为新的完全二叉树，最后一个数相当于已经排好序了。第x次建立堆后，将最大值与倒数第x个数进行交换，并将1至n-x节点看成新的二叉树。每次重建堆不再是从最后一个根节点开始操作，而是从第一个根节点开始，初建堆操作已经将根节点与孩子节点的大小关系处理好了，现在只不过是第一个根节点的值发生了变化，从第一个根节点一直往下交换即可，交换完成新的最大值又被交换到了最顶部，然后与倒数节点进行交换，重复执行，最后完成排序。

堆排序与选择排序

其实堆排序可以看成是选择排序的改进，每次找出最大值放入已排好序的部分。

  • 选择排序：每次选出最大值放入已排好序部分后，再对剩余部分全部进行比较，而剩余部分仍然是一个无序的数组 需要比较n-x-1次

  • 堆排序：在初建堆时，根节点与孩子节点的大小关系已经确定。每次重建时，比较一下左右孩子的大小，然后将根节点与较大的孩子进行交换，每比较一次，就减少了一半的比较操操作，平均比较次数是二叉树的高度-1，是lbn级别。

代码

/**
 * 初建堆  需要对所有根节点进行调整
 * @param A
 * @param n
 */
static void createHeap(int[] A, int n) {
    int k;    //指向需要调整的根节点
    for (k = n / 2; k >= 1; k--) {
        swift(A, k, n);
    }
}

/**
 * 进行堆的调整
 * @param A 待排序数组
 * @param k 调节范围起点   始终指向根节点
 * @param n 调整范围终点
 */
static void swift(int[] A, int k, int n) {
    int t;
    int temp;
    int p = 2 * k;
    while (p <= n) {     //只有当k有左孩子时才需要调整
        t = p;           //t先指向左孩子   
        if (p < n) {     //如果k有右孩子  需要比较左右孩子的大小
            if (A[p] < A[p + 1]) {    //如果右孩子大 则需要将t指向右孩子
                t = p + 1;
            }
        }
        if (A[k] < A[t]) {     //比较根节点与孩子的大小   如果根节点小于孩子节点   则需要交换
            temp = A[k];
            A[k] = A[t];
            A[t] = temp;
            k = t;            //k指向新的根节点
            p = 2 * k;        //p指向新的根节点的左孩子
        } else {              //根节点大于孩子  则已经是大根堆 不必调整  结束
            break;
        }
    }
}

/**
 * @param A
 * @param n
 */
static void heapSort(int[] A, int n) {
    int temp;
    createHeap(A, n);
    for (int i = n; i > 0; i--) {    //调整堆
        A[0] = A[n - 1];            //无序数组要求第一个位置A[0]不存数，便于代码书写与理解
        A[n - 1] = A[1];
        A[1] = A[0];
        swift(A, 1, i - 1);    //只需要
    }
}

时间复杂度

平均时间复杂度$O(n)=nlbn$

最差时间复杂度$O(n)=nlbn$

简单分析一下：

初建堆要对$n/2$ 个根节点进行调整，每个根节点调整次数（孩子节点的比较次数）平均也就是高度的一半 $\frac{1}{2}lbn$（如果加上根节点与孩子节点的比较差不多就是$lbn$）, 所以初建堆差不多也就是$\frac{1}{4}lbn$ ,调整堆也是类似，相加还是 $nlbn$ 级别 （这些数据只是个大概，影响的是系数大小，不会对n哟影响）

合并排序

思路：

  • 合并数组 循环合并，先按照两个子数组的长度为1、2、4、8…进行第合并,每一轮合并都包含多次合并操作。就比如进行长度为8的合并时，就要对{0-7}和{8-15}进行合并 ，对{16-23}和{24-31}进行合并……。
  • 合并其实就是依次比较两个子数组中的元素大小，将它们另一个临时数组保存，最后把临时数组的内容复制到原数组对应下标。

代码

/**
 * 划分长度进行合并
 * @param A   原数组
 * @param n   数组长度
 */
static void mergeSort(int[] A, int n) {     //进行归并
    for (int i = 1; i < n; i = i * 2) {     //依次归并长度为1,2,4,8...的数组
        mergePass(A, i, n);
    }
}

/**
 * 合并
 * @param A        原数组
 * @param length   子数组长度
 * @param n        原数组长度
 */
static void mergePass(int[] A, int length, int n) {   //合并长度为length的数组
    int i;
    for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length) {
        merge(A, i, i + length - 1, i + 2 * length - 1);   //下界是i  长度是length 所以mid=i+length-1 上界是mid+length-1
    }
    if (i + length - 1 < n - 1) {  //分界点未超过数组最大下标 也就是但大于一个 小于两个，还是要合并一次
        merge(A, i, i + length - 1, n - 1);
    }
}

/**
 * 合并
 * @param A
 * @param left    上界  left-mid确定第一个子数组
 * @param mid     第一个子数组末尾
 * @param high    下界  mid+1-high确定第二个子数组
 */
static void merge(int[] A, int left, int mid, int high) {
    int[] temp = new int[high - left + 1];
    int i = left, j = mid + 1, p = 0;
    while (i <= mid && j <= high) {
        if (A[i] > A[j]) {
            temp[p++] = A[j++];
        } else {
            temp[p++] = A[i++];
        }
    }
    while (i <= mid) {
        temp[p++] = A[i++];
    }
    while (j <= high) {
        temp[p++] = A[j++];
    }
    for (i = left, p = 0; i <= high; i++, p++) {
        A[i] = temp[p];
    }
}

对于代码中的几个细节此处记录以下，老是容易忘记

下界 ：$i$ 最初是0

分界 ：$i+length-1$

上界 ：$i+2*length-1$

循环条件 ：上界不超过数组最大下标 $i+2*length-1<n-1$

循环变量变化 ：上一组被合并的数组的上界加1 $i+2*length-1+1$

剩余数组大于1个小于两个 ：分界小于最大下标 $i+length-1<n-1$

第一个函数，是先划分合并的两两子数组长度length，每次都是都整个数组进行合并。

第二个函数，拿到了子数组长度后，就从0开始，计算相邻两个数组的上下边界（两个数组合在一起的上下界，不是各自的上下界），并传入第三个函数进行合并。第三个函数需要知道被合并的相邻的两个数组的上下界以及二者间的分界。因此第二个函数的循环，以 $i=0$ 为下界，i加上两个length长度再减去1 即 $i+2*length-1$ 计算出上界，而分界就是i加上一个length再减去1即$i+length-1$。循环变量的变化显然就是变为下一组需要被合并的两个数组的下界，也就是上一组被合并的数组的下界加1，即 $i+2*length$。循环条件的判断就是判断被合并的数组的上界是否没有超出原数组的大小。最后要进行一次合并，因为上界如果不满足循环条件，有多种情况，可能就剩一个length长度的数组，或者不足一个，也或者大于一个小于两个，对于最后者这种情况也就是分界点没超过数组长度$i+length-1<n-1$，就需要再次进行合并，那么最后这一次合并的上下界就是 i，n-1。

时间复杂度

平均时间复杂度$O(n)=nlbn$

最差时间复杂度$O(n)=nlbn$

简单分析一下

合并过程中，因为是对整个数组进行合并，不管是合并子数组的长度为多少，比较次数的规模基本就是n，因为比较的时候本来就是两个数组中的元素取出来依次比较大小，就算运气最好情况也是将另一个数组直接拼接到另一个后面，整体下来还是 $\frac{n}{2}$ 。如果数组元素的个数 $n=2^k$ 长度划分就有k种 所以 最终时间复杂度就是 $k*n,k=lbn$ 所以最终是 $nlbn$