了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i1遍的处理，它们已正确地排好序。冒泡排序是稳定的。算法时间复杂度是O
2。22选择排序（Selectio
Sort）选择排序的基本思想是对待排序的记录序列进行
1遍的处理，i遍处理第是将Li
中最小者与Li交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。选择排序是不稳定的。算法复杂度是O
2。23插入排序（I
sertio
Sort）插入排序的基本思想是，经过i1遍处理后L1i1己排好序。第i遍处理仅将Li插入L1i1的适当位置，使得L1i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较Li和Li1，如果Li1≤Li，则L1i已排好序，第i遍处理就结束了；否则交换Li与Li1的位置，继续比较Li1和Li2，直到找到某一个位置j1≤j≤i1，使得Lj≤Lj1时为止。图1演示了对4个元素进行插入排序的过程，共需要abc三次插入。直接插入排序是稳定的。算法时间复杂度是O
24堆排序堆排序是一种树形选择排序，在排序过程中，将A
看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最2
f小的元素。堆排序是不稳定的。算法时间复杂度O
log
。25归并排序设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为Alm，Am1h，将它们归并为一个有序数列，并存储在Alh。其时间复杂度无论是在最好情况下还是在最坏情况下均是O
log2
。26快速排序快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。快速排序是不稳定的。最理想情况算法时间复杂度O
log2
，最坏O
2。27希尔排序在直接插入排序算法中，每次插入一个数，个节点，在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（增量）并且对插入下一个数没有r