常用排序

一、插入排序

每次将一个待排序的数据元素，按照其关键字大小插入到前面已排好序的有序序列的适当位置，使插入以后的数据序列仍然为一个有序序列，直到整个序列成为有序序列为止。

1.直接插入排序

插入排序过程需要将待插入的元素和所有的元素进行比较

2.折半插入排序

将待插入数据与当前有序序列中的平分位置的关键字数据进行比较，从而确定下一步要确定的子序列，直到找到插入的合适位置。

3.希尔排序

先将整个待排序序列分割成若干子序列，每个子序列由相关一定长度的数据元素组成(这个相差的长度称为增量)，然后我们分别对这些子序列进行直接插入排序，一轮排序后再取第二个增量，以此类推，需要注意的是，对于希尔排序中增量的确定没有统一的规定，通常的做法是：第一个增量为待排序序列长度的二分之一(取整),然后逐渐减半(取整)，直到等于1为止。

二、交换排序：利用交换数据元素的位置进行排序的方法称为交换排序

1.冒泡排序

2.选择排序