数据结构的内部排序也就是内存排序，分为插入排序(直接插入排序和希尔排序)，交换排序(冒泡排序和快速排序)，选择排序(直接选择排序和堆排序)，归并排序。

插入排序

插入排序的思想是:将一个带排序的记录按照大小插入到一个有序的序列的适当位置，使得插入后的序列仍然有序。插入排序包括直接插入排序和希尔排序。

直接插入排序

直接插入排序思想:待排序的n个记录放在数组R中，把数组分为两个表，一个有序表和一个无序表。开始有序表只有一个记录R[0]，无序表有n-1，每一次都从无序表中取出第一个元素，把它插入到有序表中的适当位置，这样经过n-1次插入后，无序表成为了空表，有序表包含了所有的记录。

直接插入排序

直接插入排序 时间复杂度O(n2)，空间复杂度为O(1)，稳定的。

希尔排序

希尔排序又称为缩小增量排序，基本思想是把待排记录分成几个组，在每一个组内的分别进行直接插入排序，使得整个记录序列部分有序，重复此过程，直到所有记录都在一个组中，最后对所有的记录进行一次直接插入排序。

希尔排序

希尔排序时间复杂度为O(nlog2n )到O(n2)之间，大约为O(n1.5)之间，空间复杂度为O(1)，不稳定。

交换排序

交换排序的基本思想是，两两比较待排序的记录，不符合排列顺序的交换记录。

冒泡排序

冒泡排序是依次比较两个相邻的两个记录的排序码，不符合顺序的直接交换。

时间复杂度为OO(n2)之间，空间复杂度为O(1)，比较稳定。

冒泡排序

快速排序

快速排序称为划分排序或分区排序，它是目前所有内部排序中速度最快的一种，快速排序是对冒泡排序的一种改进。在快速排序中，比较和交换是从数组的两端向中间进行，使得排序码较小的或者较大的记录一次就能够交换到数组的前面或者后面，记录的每一次移动距离较远，因为使得总的比较和移动次数较小。快速排序是一个递归的过程。

快速排序时间复杂度为O(nlog2n )，空间复杂度为O(nlog2n)。快速排序是个不稳定的排序方法。

快速排序

选择排序

选择排序的基本思想，每一次从待排序记录序列中选取一个排序码最小或者最大的记录和放在待排序记录的的最前面或者最后面，重复此过程，直到所有的记录按照排序码排好序。

直接选择排序

直接选择排序(Straight Select Sort) 也是一种简单的排序方法。直接选择排序的基本思想是：假定待排序的n个记录存储在数组R[1]~R[n]中，经过比较选出排序码最小的记录，将其同R[1]交换，也就是将排序码最小的记录放到待排序区间的最前面，完成第一趟直接选择排序(即i=1) 。第i(1<i<n一1) 趟直接选择排序的结果是将R[i] ~RCn] 中排序码最小的记录放到待排序子区间的最前面，即与R[i]交换位置。经过n一1趟直接选择排序，R[1] ~REn] 成为有序表， 整个排序过程结束。

时间复杂度是O(n2)，空间复杂度O(1)，是不稳定的排序算法。

直接选择排序

堆排序

堆排序正是利用大(或小)根堆的性质不断地选择排序码最大(或小)的记录来实现排序的，下面利用大根堆来实现升序排列。设有n个待排序记录存储在R[1]~R[n]中，首先将这n个记录按排序码建成大根堆，此时排序码最大的记录是堆顶R[1]，然后R[1]与R[n]交换位置， 即把排序码最大的记录放到待排序区间的最后； 接着， 再把R[1] ~REn一1] 中的n一1个记录建成大根堆， 仍然将堆顶R[1] 与REn一1] 交换位置。如此反复n一1次，每次选一个排序码最大的记录与本次排序区间的最后一个记录交换位置，最终得到一个有序序列，我们称这个过程为堆排序。

堆排序的时间复杂度是O(nlog2n)，空间复杂度O(nlog2n)，是不稳定的排序算法

堆排序

归并排序

归并排序(MergeSort) 是利用“归并”技术实现的排序方法。所谓归并就是将两个或多个有序表合并成一个有序表的过程。如果是将两个有序表合并成一个有序表称为二路归并；同理，将三个有序表合并成一个有序表称为三路归并，以此类推可以有n路归并等。但云路归并是最简单和最常用的。本节主要讲二路归并技术实现的归并排序。

归并排序的时间复杂度是O(nlog2n)，空间复杂度O(n)，是稳定的排序算法。

归并排序