排序：根据元素关键字的大小或其他规则来对序列中的元素进行调整，以确保它们的相对顺序符合所需的排序顺序（升序或降序）。
排序的稳定性：如果关键字key1=key2,在排序后记录1和记录2的位置没有发生变化，那么这种排序方法就是稳定的，相反，如果排序后记录1和2的顺序和排序前发生了变化，则此排序方法不稳定。
内排序：在排序的过程中，待排序的所有记录放置在内存中。
外排序：当数据无法一次性全部加载到内存中时，将大文件分割成适当大小的块，然后在内存中对这些块进行排序，最后将排好序的块合并成一个有序的文件。这个过程通常需要从外部存储（磁盘）读取和写入大量数据。
内排序又分为：插入排序、交换排序、选择排序、递归排序
此篇文章的所有排序操作均是对以下顺序表进行排序操作。
结构如下：
交换函数：
如果不知道冒泡排序的同学，详细介绍请看下面文章：
看了以上文章你应该知道，这种排序方法不管在什么情况下都会进行n-1趟排列。但是当一个序列只有前几个是无序的，后几个都是满足你规定的顺序，那这样做就显得很不聪，根本没有必要做那么多趟排序。
具体优化见下面代码：
进行优化后，只有序列为逆序的情况下才会进行n-1次，其他情况均小于n-1次。
（以下对优化后的算法进行分析）
当序列有序时，进行n-1次比较，只进行一趟排序；
当序列逆序时，每一趟进行（n-i）次比较，总共进行次比较，进行n-1趟排序；
时间复杂度：O()
简单选择排序：在未排序的部分中选择最小的元素，然后将其与未排序部分的第一个元素交换位置。这个过程不断重复，每次选择未排序部分的最小元素，直到整个序列有序。
代码如下：
优点：交换的次数少。
不论什么情况，每一趟进行（n-i）次比较，总共进行次比较。
最少交换0次，最多交换n-1次。
时间复杂度：O()
将数组分为已排序和未排序两部分，初始时已排序部分只有一个元素。算法从未排序部分逐个取出元素，插入到已排序部分的正确位置，通过逐步构建有序序列实现整体排序。在每一步，当前元素与已排序部分的元素逐个比较，找到其正确插入位置，确保已排序部分仍然有序。这一过程重复进行直到整个数组有序。
代码如下：
序列是有序是需要比较（n-1）次，移动零次
序列为逆序时，
对于每个元素，都需要移动到已排序部分的最前面。因此，第二个元素需要移动一次，第三个元素需要移动两次，第四个元素需要移动三次，以此类推。
总的移动次数是前 n 个整数的累加和：
需要移动：
时间复杂度：O()
希尔排序：希尔排序是一种基于插入排序的排序算法，它的特点在于通过预处理使得原数组中某些较远的元素先有序，然后逐步缩小间隔，最终实现整体有序。
思想：希尔排序的核心思想是通过每一轮的插入排序，减小数组中元素的距离，使得原本较远的元素有机会在前几轮中先有序。
算法步骤：
- 选择一个增量序列（间隔序列）：通常使用长度/2。
- 对每个增量序列进行排序：对于每个增量，将数组分成若干个子序列，每个子序列包含相邻间隔为增量的元素。对每个子序列应用插入排序。
- 减小增量：每一次减小增量/2。重复上述过程，缩小增量，直到增量为1。最终一次使用增量为1的插入排序，完成整个排序过程。
大顶堆：完全二叉树每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：完全二叉树每个结点的值都小于或等于其左右孩子结点的值。
在堆排序算法中，第一步是构建一个初始的大顶堆，然后将堆顶元素（最大值）与堆中最后一个元素交换，接着对剩余的堆进行调整，确保仍然保持大顶堆的性质。这样的交换和调整步骤会重复进行，直到整个序列有序。
归并排序的初始阶段将原始序列中的每个元素看作一个有序队列（长度为1的队列）。随后，逐步将相邻的有序队列两两合并，并对合并后的队列进行排序。然后，将这些排好序的队列再次两两合并，不断重复这一步骤，直到合并后的队列长度达到原始序列的长度，此时排序完成。这个过程保证了每次合并都是在有序的基础上进行，最终得到整个序列的有序结果。
- 选择基准值：从待排序的序列中选择一个元素作为基准值。（为了方便选择第一个元素作为基准值）
- 划分序列:将比基准值小的放在基准值的左边，将大于基准值的放在基准值的右边。一趟排序下来基准值左边的值均小于右边的值。再次递归对基准值左边和右边的序列进行以上操作，直到当低指针low大于等于高指针high时，表示当前子序列的长度为1或0，即已经有序，此时递归结束。
代码如下：
优化基准值
三数取中
选择中间位置的元素作为基准值，通过比较三个位置的元素，确保基准值在三者中间，有助于提高基准值的选择的准确性，减小最坏情况的概率，从而提高整体排序性能。
代码如下：
结合插入排序优化性能
当子序列的规模较小时，切换到插入排序，因为对于小规模数据，插入排序更为高效。插入排序在小规模数据上有较好的性能，而快速排序在大规模数据上表现更好，因此这种切换可以提高整体性能。
代码如下:
优化递归
代码如下：
减少交换
将交换操作改变为替换操作(简单的赋值语句：L->a [low]=L->a [high];)，减少交换次数优化性能。
代码如下：
优化后的完整代码如下：