最近笔试了几家，发现都有排序题，所以就整合发下

本文由互联网资料整理而来（续写经典）

分类：

1）插入排序（直接插入排序、希尔排序）

2）交换排序（冒泡排序、快速排序）

3）选择排序（直接选择排序、堆排序）

4）归并排序

5）分配排序（基数排序）

所需辅助空间最多：归并排序

所需辅助空间最少：堆排序

平均速度最快：快速排序

不稳定：快速排序，希尔排序，堆排序。

/*1、直接插入排序

* 基本思想：假设前面已有n-1个已排好序的

* 现将第n个插入前面已排好序的，使得这n个

* 数也是已经排好序的

* */

直接插入排序

最好情况：是排序前对象已按照要求排好，需要比较次数n-1 时间复杂度O(n)

最差情况：比如逆序 需要比较：n*n/2,移动次数n*n/2 时间复杂度O(n^2)

平均时间复杂度O(n^2)

由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。

如何改进，或有和意见，请留言反馈

下一篇希尔排序

代码

public void testDirectInsert() { int[] a = new int[] {57,68,59,52,58}; int len = a.length; for(int i = 1;i < len;i++) { //准备插入的数 int temp = a[i]; int j = i - 1; for( ;j >= 0&&temp < a[j];j--) { //将大于temp的数整体后移一位 a[j+1] = a[j]; } a[j+1] = temp; } //遍历输出 for (int i : a) { System.out.println(i); } }