八大排序算法及其比较排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序、基数排序等。前面三种是简单排序，后续算法是在前面基础上进行优化。本文将基于C语言，依次介绍上述八大排序算法。1 八大排序算法1.1 冒泡排序主要思想：依次对两个数比较大小，较大的数冒起来，较小的数压下来。形象理解：一队新兵N个人整齐站成一列，教官想让他们按照身高排好队，看起来更协调，于是从前走到后走一趟，每次遇到相邻的两个人身高不协调时，就让两人互换位置。当走完一趟时，个子最高的人就被排到了最后。教官回到前排后发现队伍仍然不协调，于是又按照原样走了一趟。这样循环走了N-1趟之后，教官终于满意了。（注意：每次走一趟时，之前排到后面的高个子就不参与这次排序了；有时候可能还没走完N-1趟，教官就发现队伍已经协调了，于是排序结束。）特点：简单易懂，排序稳定，但速度慢。1.2 选择排序主要思想：针对冒泡排序，有一个地方可以优化，即在跑一趟的过程中，没必要两两交换，可以先记下最小值，跑完一趟后直接将最小值换到前面。特点：比冒泡更快一些，但代价是跳跃性交换，排序不稳定。1.3 插入排序主要思想：过程跟拿牌一样，依次拿N张牌，每次拿到到牌后，从后往前看，遇到合适位置就插进去。最终手上的牌从小到大。特点：当数据规模较小或者数据基本有序时，效率较高。1.4 希尔排序主要思想：设增量序列个数为k，则进行k轮排序。每一轮中，按照某个增量将数据分割成较小的若干组，每一组内部进行插入排序；各组排序完毕后，减小增量，进行下一轮的内部排序。特点：针对插入排序的改进，当数据规模较大或无序时也比较高效。精妙之处在于，可以同时构造出两个特殊的有利条件（数据量小，基本有序），一个有利条件弱时，另外一个有利条件就强。（刚开始时虽然每组有序度低，但其数据量小；随着每轮的增量逐渐压缩，虽然各组数据量逐渐变大，但其有序度逐渐增加。）1.5 堆排序主要思想：将待排数组构建成一个最大堆，将堆顶最大元素换到后面，然后堆容量减1；类似进行N-1次操作即可。1.6 快速排序主要思想：分治思想。选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成。注意：对于小规模数据（n<100），快排由于用了递归，其效率可能还不如插排。因此通常可以定义一个阈值，当递归的数据量很小时停止递归，直接调用插排。1.7 归并排序主要思想：类似两个有序链表的合并，每次两两合并相邻的两个有序序列，直至整个序列有序。1.8 基排序主要思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。2 八大排序算法比较复杂度与稳定性的比较算法类别平均时间复杂度最好情况复杂度最坏情况复杂度空间复杂度稳定性冒泡排序\(O(n^2)\)\(O(n)\)\(O(n^2)\)\(O(1)\)稳定选择排序\(O(n^2)\)\(O(n^2)\)\(O(n^2)\)\(O(1)\)不稳定插入排序\(O(n^2)\)\(O(n)\)\(O(n^2)\)\(O(1)\)稳定希尔排序\(O(n^{1.5})\)--\(O(1)\)不稳定堆排序\(O(n log(n))\)\(O(n log(n))\)\(O(n log(n))\)\(O(1)\)不稳定快速排序\(O(n log(n))\)\(O(n log(n))\)\(O(n^2)\)\(O(1)\)不稳定归并排序\(O(n log(n))\)\(O(n log(n))\)\(O(n log(n))\)\(O(n)\)稳定基排序\(O(d*n)\)\(O(d*n)\)\(O(d*n)\)\(O(n)\)稳定以下是基于浙大数据结构课练习题测试（09-排序1 排序 (25 分)）。参考：https://blog.csdn.net/qq_39207948/article/details/80006224https://www.cnblogs.com/onepixel/articles/7674659.htmlhttps://www.runoob.com/w3cnote/sort-algorithm-summary.htmlhttps://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/%E9%9D%A2%E8%AF%95%E4%B8%AD%E7%9A%84%2010%20%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.md
