1、排序算法概述

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

• 所需辅助空间最多：归并排序
• 所需辅助空间最少：堆排序
• 平均速度最快：快速排序
• 不稳定：快速排序，希尔排序，堆排序。

选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有：

• 1.数据的规模 ：当数据规模较小时，选择直接插入排序或冒泡排序。
• 2.数据的类型 ：如全部是正整数，那么考虑使用桶排序为最优。
• 3.数据已有的顺序 ：快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。

数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

2、直接插入排序时空复杂度

最好时间复杂度O(n)，最差时间复杂度O(n^{2)，平均时间复杂度O(n}2)，空间复杂度O(1)，是一种稳定的排序算法。元素集合越接近有序，直接插入排序算法的时间效率越高。从空间上看只需要一个哨兵的辅助空间。

• 当最好的情况下，也就是表本身就是有序的，那么我们比较次数共计n-1次，因为每次都是elem[i]>elem[i -1]，所以没有移动记录，时间复杂度为O(n)。当最坏的情况下，即逆序情况下，此时需要比较1+2+3+…+n-1=n(n-1)/2次，而记录的移动次数也达到最大值n(n-1)/2​次。

同样的复杂度，直接插入排序比冒泡和简单选择排序性能要好。

• 1.当n <= 50时，适合适用直接插入排序和简单选择排序，如果元素包含的内容过大，就不适合直接插入排序，因为直接插入排序需要移动元素的次数比较多。
• 2.当数组基本有序的情况下适合使用直接插入排序和冒泡排序，它们在基本有序的情况下排序的时间复杂度接近O(n)。

3、直接插入排序原理

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。简单理解就是将n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素，排序过程中每次从无序表中取出第一个元素，将其插入到有序表中的指定位置，使之成为一个新的有序表，重复n-1次可完成排序过程。

• 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较， 直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

4、直接插入排序思路

1. 首先比较数组的前两个数据，并排序；
2. 比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
3. 比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；

…直至把最后一个元素放入适当的位置。

5、直接插入排序举例说明

要排序数组：int[] arr={21,25,49,25,16, 08};

1.i=4时，设置temp=a[4];

2.将temp与前一个数a[3]比较,a[3]大,后移到a[4]位置，即a[4]=a[3];

3.将temp与前一个数a[2]比较,a[2]大,后移到a[3]位置，即a[3]=a[2];

4.将temp与前一个数a[1]比较,a[1]大,后移到a[2]位置，即a[2]=a[1];

5.将temp与前一个数a[0]比较,a[0]大,后移到a[1]位置，即a[1]=a[0];

6.将temp移到a[0]位置，即a[0]=temp;

6、直接插入排序代码

public class InsertSort {
	public static void main(String[] args) {
		int arr[] = { 1, 4, 6, 8, 2, 5, 3, 7, 9 };
		System.out.println("数组排序前顺序：");
		for (int n : arr) {
			System.out.print(n + " ");
		}
		// 直接插入排序
		insertSort(arr);
		System.out.println("\n数组排序后顺序：");
		for (int n : arr) {
			System.out.print(n + " ");
		}
	}

	// 直接插入排序
	private static void insertSort(int[] arr) {
		// 外层循环确定待比较数值
		for (int i = 1; i < arr.length; i++) { // 必须i=1，因为开始从第二个数与第一个数进行比较
			int temp = arr[i]; // 待比较数值
			int j = i - 1;
			// 内层循环为待比较数值确定其最终位置
			for (; j >= 0 && arr[j] > temp; j--) { // 待比较数值比前一位置小，应插往前插一位
				// 将大于temp的值整体后移一个单位
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp; // 待比较数值比前一位置大，最终位置无误
		}
	}
}

// 数组排序前顺序：
// 1 4 6 8 2 5 3 7 9 
// 数组排序后顺序：
// 1 2 3 4 5 6 7 8 9