面试常考数据结构与算法

算法 数据结构

1. 堆排序

参考出处

1.1 二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树(只有最后一层是不完整的)。
二叉堆满足二个特性：

• 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

1.2 堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

1.3 堆的操作——插入删除

堆的插入
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中
堆的删除
按定义，堆中每次都只能删除第0个数据。为了便于重建堆，把子节点上升到根节点，然后再从根结点开始进行一次从上向下的调整。
个人总结：
所以堆排序就是在堆的基础上来排序。
堆化数组

1.4 堆排序

首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A1交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。

1.5 时间复杂度分析

时间复杂度 O(nlogn), 空间复杂度O(1). 从这一点就可以看出，堆排序在时间上类似归并，但是它又是一种原地排序，时间复杂度小于归并的O(n+logn)
排序时间与输入无关，最好，最差，平均都是O(nlogn). 不稳定

堆排序借助了堆这个数据结构，堆类似二叉树，又具有堆积的性质（子节点的关键值总小于（大于）父节点）
堆排序包括两个主要操作:

保持堆的性质heapify(A,i)
时间复杂度O(logn)
建堆 buildmaxheap(A)
时间复杂度O(n)线性时间建堆

对于大数据的处理： 如果对100亿条数据选择Topk数据，选择快速排序好还是堆排序好？ 答案是只能用堆排序。 堆排序只需要维护一个k大小的空间，即在内存开辟k大小的空间。而快速排序需要开辟能存储100亿条数据的空间，which is impossible.

2. 快速排序

2.1 算法步骤

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

static void quikSort(int s [], int l, int r) {
        if (l < r) {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j) {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if(i < j)
                    s[i++] = s[j];
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if(i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            quikSort(s, l, i - 1); // 递归调用
            quikSort(s, i + 1, r);
        }
    }

2.2 算法复杂度分析

我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如图9‐9‐7所示，它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

图9-9-7在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。

T（n）≤2T（n/2） +n，T（1）=0
T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
……
T（n）≤nT（1）+（log2n）×n= O(nlogn)
也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为 ，最终其时间复杂度为O(n2)。

平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：

由数学归纳法可证明，其数量级为O(nlogn)。

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

3. 冒泡排序

冒泡排序是非常容易理解和实现，，以从小到大排序举例：

3.1 冒泡排序概述

设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

3.2 冒泡排序代码实现

//冒泡排序3
void BubbleSort3(int a[], int n)
{
    int j, k;
    int flag;
    flag = n;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
            if (a[j - 1] > a[j])
            {
                Swap(a[j - 1], a[j]);
                flag = j;
            }
    }
}

3.3 冒泡排序时间复杂度

时间复杂度O(n^2), 空间复杂度O(1)， 稳定，因为存在两两比较，不存在跳跃。
排序时间与输入无关，最好，最差，平均都是O(n^2)。数据小时可以作为排序方式。