各种排序算法
1、归并排序
归并排序是一种经典的排序算法，采用分治的思想。其基本思路是将待排序序列分成若干个子序列，然后对每个子序列进行排序，最后将已经排好序的子序列合并成为最终的有序序列。
具体实现步骤如下：
- 将待排序序列分成若干个子序列，每个子序列中只包含一个元素。
- 两两合并相邻的子序列，得到一些长度为2的有序子序列。
- 再将相邻的有序子序列两两合并，得到一些长度为4的有序子序列。
- 重复上述步骤，直到得到一个有序序列。
归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。
2、直接插入排序
直接插入排序是一种简单的排序算法，其基本思想是将待排序序列中的元素一个一个地插入到已经排好序的子序列中，直到整个序列都有序为止。
具体实现步骤如下：
- 将第一个元素视为已经排好序的子序列，从第二个元素开始将其插入到已经排好序的子序列中。
- 对于第i个元素，将它与前面的元素依次比较，找到它应该插入的位置。
- 将第i个元素插入到它应该插入的位置上。
- 重复步骤2和3，直到将所有元素插入到已经排好序的子序列中。
直接插入排序的时间复杂度为O(n^2)，是一种稳定的排序算法。如果待排序序列已经有一部分有序，那么直接插入排序的效率会比较高，因为插入的操作次数会减少。
3、折半插入排序 （直接插入排序+二分法）
折半插入排序是一种插入排序算法，其基本思想是将待排序序列中的元素一个一个地插入到已经排好序的子序列中，但是在寻找插入位置时采用折半查找的方式，从而减少了比较次数。
具体实现步骤如下：
- 将第一个元素视为已经排好序的子序列，从第二个元素开始将其插入到已经排好序的子序列中。
- 对于第i个元素，采用折半查找的方式找到它应该插入的位置。
- 将第i个元素插入到它应该插入的位置上。
- 重复步骤2和3，直到将所有元素插入到已经排好序的子序列中。
折半插入排序的时间复杂度为O(n^2)，与直接插入排序相同，但是比较次数会减少，因此效率会稍微高一些。同时，折半插入排序也是一种稳定的排序算法。
4、选择排序
选择排序是一种简单直观的排序算法，其基本思想是每次从待排序序列中选择最小（或最大）的元素，将其放到已经排好序的序列的末尾（或开头），直到整个序列都有序为止。
具体实现步骤如下：
- 将待排序序列分成已排序和未排序两部分，初始时已排序部分为空，未排序部分包含所有元素。
- 从未排序部分中选择最小（或最大）的元素，将其与已排序部分的末尾（或开头）元素交换位置。
- 将已排序部分的长度增加1，将刚刚选择的元素放入已排序部分的末尾（或开头）。
- 重复步骤2和3，直到整个序列都有序为止。
选择排序的时间复杂度为O(n^2)，不论待排序序列的初始状态如何，比较次数和交换次数都是相同的，因此选择排序是一种不稳定的排序算法。
5、冒泡排序
冒泡排序是一种简单直观的排序算法，其基本思想是多次遍历待排序序列，每次遍历都比较相邻的两个元素，如果它们的顺序不对就交换位置，这样就可以将最大（或最小）的元素逐步“冒泡”到序列的末尾，直到整个序列都有序为止。
具体实现步骤如下：
- 将待排序序列分成已排序和未排序两部分，初始时已排序部分为空，未排序部分包含所有元素。
- 对于未排序部分，从前往后依次比较相邻的两个元素，如果它们的顺序不对就交换位置，将最大（或最小）的元素“冒泡”到未排序部分的末尾。
- 将未排序部分的长度减少1，将刚刚“冒泡”到末尾的元素放入已排序部分的末尾。
- 重复步骤2和3，直到整个序列都有序为止。
冒泡排序的时间复杂度为O(n^2)，不论待排序序列的初始状态如何，比较次数和交换次数都是相同的，因此冒泡排序是一种稳定的排序算法。
