内部排序算法中的插入与快排及其优化算法（个人理解不含代码）

内部排序算法中的插入与快排及其优化算法（个人理解不含代码）

内部排序算法

1. 插入排序
	基础插入排序指的是对于一个有序表，依次将待插入的值插入在有序表的合适位置，从而使得有序。在程序实现中可以先将表第一个值单独当成一个有序表，然后从第二个值开始往后循环，从后往前对比，直到找到合适位置插入，然后将目标位置原值及之后的值全部往后移动。这种排序方式的主要开销用于对比与后移 *** 作。
	
1.1 插入排序优化
	折半插入排序：由于直接插入排序的开销用于对比与后移 *** 作，针对于查找 *** 作，可以采用折半对比的方法，减少对比次数。这种方式被称为折半插入排序。
	2-路插入排序：2路插入排序是对折半插入排序的再改进。这个优化主要针对于简化插入排序的移动 *** 作。具体实现通俗来说就是初始将前两个值按大小分别当成最大的与最小的，然后放在表两端，如果比最大的还大就直接放在最大的后面，如果比最小的还小就直接放在最小的前面，这样就可以减少移动的次数。其他的 *** 作跟普通插入排序一样，可以一定程度优化算法。
	希尔排序：希尔排序，又称缩小增量排序，也是一种插入排序，不同的是希尔排序是按照一定增量对比交换，然后缩小增量直到增量为1（这时进行普通插入排序 *** 作）。我感觉希尔排序更像是插入排序和交换排序的结合。通过采用希尔排序可以不存在大量数据后移或者前移 *** 作，而是通过一定区间数据的移动使得表逐渐有序。例如：
	对于 10 个元素的数据，使其有序，可以先设增量为 5 ，使 1 6， 2 7 ， 3 8， 4 9， 5 10进行插入排序，然后设增量为 3， 使 1 4 7 10， 2 5 8， 3 6 9进行插入排序。最后设增量为 1 直接排序（实际交换 *** 作很少）。
    之所以希尔排序能优化算法，是因为较小（较大）值的移动是进行跳跃交换移动的，而不需要一点点挪动，经实验可以很好优化算法，而这个优点主要体现在程序中是：希尔排序不是简单地分段，而是通过增量分成子序列。

2. 快速排序
	最简单地是起泡排序（我一般叫它冒泡排序），就是先从第二个数开始循环一遍无序表，然后将目标数与前面的数对比，如果不满足排序规则，就交换，继续往前起泡，直到到达表头或者符合排序规则。
	
	快速排序是对起泡排序的优化，我的理解是类似于二分思想，首先定义一个初始中点数（一般选无序表的第一个元素），用这个中点数将无序表一分为二，表前半部分都小于这个数（但仍是无序的），表后半部分都大于这个数（但仍是无序的），然后分别将前后两个表作为目标表进行快排，直到表不能再分。也体现一种递归的思想。
	在程序实现时需要写出两个方法，一个目的是将用选定中位数将表一分为二，一个目的是调用递归。