c语言经典算法—二分查找，冒泡，选择，插入，归并，快排，堆排

一、二分查找

         1、前提条件：数据有序，随机访问；

         2、实现：递归实现，非递归实现

         3、注意事项：

                循环退出条件:low <=high,low = high.说明还有一个元素，该元素还要与key进行比较

                mid的取值：mid=（low + high）/2；mid = low + （（high - low）>>1)

                low 和high 的更新：low = mid +1；high = mid - 1；不能写成low = mid +1，high = mid-1；又可能出现死循环；

        代码实现：

1、查找第一个与key相等的元素：

2、查找最后一个与key相等的元素

3、查找最后一个小于等于key值的元素

4、查找第一个大于等于key值的元素

二、冒泡排序

        如何评价一个算法：

        1、时间复杂度：最好情况；最坏情况；平均情况；系数和低阶项

        2、空间复杂度：原地排序（特指空间复杂度为O（1））的排序；

        3、稳定性：数据集中“相等”的元素，如果排序前和排序后的相对次序不变，那么这个排序就是稳定的；

        稳定性就是排序算法的很重要的指标；

冒泡排序：

        比较相邻的元素，如果前一个比后一个大，就交换次序，

        对每一对相邻元素做同样的工作，从第一对到最后一对。最大的元素就会位于最后位置；

        除最后一个元素外，对其他元素重复上面的步骤，直到元素的个数为1；

时间复杂度：

        最好情况原数组有序（O（n））；

        最坏情况原数组逆序（比较次数（n-1）+(n-2)+...+1 = （n（n-1））/2）

                                           交换次数：（（n-1）+（n-2）+...+1  = （n（n-1））/2）

        平均情况（每一种情况出现的情况是相等的）：总情况（N！）

                                （比较次数：大于交换的次数，小于（n（n-1））/2）

                                 （交换次数（n（n-1）/4））

分析：有序元素对，逆序元素对，逆序度，有序度；

有序对：34，24，14

逆序对：12，13，23

排序的过程：增加有序度，减少逆序度，最终达到满有序度；

冒泡排序交换导致有序度+1，逆序度-1；

空间复杂度：O（1）；//原地排序

稳定性：稳定，arr[j]>arr[j+1]   才发生交换；

三、选择排序(无论什么数据进去都是（O（n2））的时间复杂度，所以用它的时候数据规模越小越好，唯一好处是不占用额外内存)

        工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕；（选择排序不能像冒泡排序一样去优化）

        时间复杂度：O(n2)

                比较次数：（n-1）+ ...+1 =(n(n-1))/2

                交换次数：n-1;

        空间复杂度：O（1）原地排序

        稳定性：不稳定，发生了长距离的交换；

四、插入排序：

        工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在从后向前扫描过程中，需要反复把已排序的元素逐步向后挪位，为最新元素提供插入空间；

        时间复杂度：

                最好情况：（O（n））

                                原数组有序(比较次数，（n-1）)交换次数：原数组有序（0）

                最坏情况：（O（n2））

                                原数组逆序（比较次数，（n-1）+（n-2）+...+1 = (n(n-1))/2）;

交换次数（（n-1）+(n-2)+...+1 =(n(n-1))/2：

                平均情况：

                                比较次数：大于交换次数，小于（n（n-1））/2

                                交换次数：（n（n-1））/4（逆序个数）

插入排序好处，当元素基本有序时，其性能非常好；

空间复杂度，O（1），原地排序

稳定性：稳定；

冒泡排序，选择排序，插入排序小结：

        

五、希尔排序（缩小增量排序，插入排序的改进版本）：

        第一批打破O（n2）这个时间复杂度的方法；

        gap（希尔）：n/2、n/4、...1;

gap = n/2=5

        

先按gap分组，组内使用简单的插入排序（十个元素分为5组）；

第一次组间排序完成后，就缩小增量，gap=5/2=2；gap =1；

时间复杂度比O（n2）小，和具体的gap序列相关；

空间复杂度O（1）原地排序；

稳定性：不稳定，会发生长距离交换；

六、归并排序：

        先把大数组分成两个小数组，直到有序再合并；单个数组已经算是有序的；

用递归解决；

        

注意释放堆区数组

        

七、快速排序

        从数列中挑出一个元素，称为“基准”（pivot）；（一般情况下可以选几个值取中位数，也可以选第一位，或者随机位）

        重新排序数列，所有元素比基准值小的拜访在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任意边。）在这个分区退出后，改基准就处于数列的中间位置（也就是最终位置）这个操作我们称之为分区（partition）；

        递归地把小于基准值元素地子数列和大于基准值元素地子数列排序（左右两边都使用快排）；

i 是放下一个比基准值小的位置，j放比基准值大的值；先移动 j 再移动 i ；

先找比基准值小的，再找比基准值大的，交替找直到  i  j 相遇，基准值的位置就确定了；

因为基准值已经保存就可以移动 j 把第一个值覆盖掉（以第一个值为基准）

时间复杂度：

        最好情况：（每次分区都分成大小相等的两份）

        最坏情况：每次基准值都位于最左边或者最右边；

        平均情况(假设每次分成三比一的情况)：

空间复杂度：

快速排序的改进策略（基准值的选取（随机选，选择多个元素的中位数）；分区操作的优化；选择多个基准值）；

八、堆排序

        二叉堆（大顶堆（根节点的键大于左右子树所有结点的键，并且左右子树都是大顶堆）；小顶堆（根节点的键小于左右子树所有结点的键，并且左右子树都是小顶堆））

        

把数组看作一个完全二叉树；

堆排算法：

把完全二叉树构建成大顶堆，找到第一个非叶子结点，从后往前构建大顶堆

把堆顶元素和无序区的最后一个元素交换，交换之后无序区的长度减一，

把无序区重新调整成大顶堆，重复上一步操作，直到无序区的长度为1；

归并（缺点：占用内存空间复杂度O（n）），快排，堆排

九、基于比较的排序算法

        证明：基于比较 的排序算法，时间复杂度的下限就是O（nlogn）；