引言
为什么想起来最近写这一些列的文章，因为最近一个朋友吐槽面试的有6，7年工作经验的员工，连基本的排序都不能实现，所以想了下，如果让自己来做，能不能讲的清楚这一些列的排序。所以就动手写了这一系列的文章，也算是自己了解巩固下。
常用的排序算法
冒泡排序（Bubble Sort）
冒泡排序也称为：沉降排序(SinkingSort)，之所以有这两个名字和他的实现方法有关，因为冒泡排序的实现方式是将数据列表中的最小的数据往前移动，想水里面的气泡一样向上浮。这样也就对应着最大的数据，逐渐往后移动，对应着上浮的就是下沉。
冒泡排序每次只比较相邻的两个数字的大小，再将一个数字和后面数字继续比较大小，一轮比较完成后在比较下一轮数据。知道最终没有数据可以比较位置，排序结束。
Java:
public static void main(String[] args) {
int[] a =new int[]{9, 2, 7, 8, 5, 6, 3, 4, 1};
for (int i =a.length -1; i >=1; i--) {
for (int j =0; j < i; j++) {
int temp1 =a[j];
int temp2 =a[j +1];
a[j] =temp1 >temp2 ?temp2 :temp1;
a[j +1] =temp1 >temp2 ?temp1 :temp2;
printArrays(a);
}
}
}
private static void printArrays(int[] a) {
for (int i =0; i
System.out.print(a[i] +"、");
}
System.out.println();
}
Out:
2、9、7、8、5、6、3、4、1、
2、7、9、8、5、6、3、4、1、
2、7、8、9、5、6、3、4、1、
2、7、8、5、9、6、3、4、1、
2、7、8、5、6、9、3、4、1、
2、7、8、5、6、3、9、4、1、
2、7、8、5、6、3、4、9、1、
2、7、8、5、6、3、4、1、9、
2、7、8、5、6、3、4、1、9、
2、7、8、5、6、3、4、1、9、
2、7、5、8、6、3、4、1、9、
2、7、5、6、8、3、4、1、9、
2、7、5、6、3、8、4、1、9、
2、7、5、6、3、4、8、1、9、
2、7、5、6、3、4、1、8、9、
2、7、5、6、3、4、1、8、9、
2、5、7、6、3、4、1、8、9、
2、5、6、7、3、4、1、8、9、
2、5、6、3、7、4、1、8、9、
2、5、6、3、4、7、1、8、9、
2、5、6、3、4、1、7、8、9、
2、5、6、3、4、1、7、8、9、
2、5、6、3、4、1、7、8、9、
2、5、3、6、4、1、7、8、9、
2、5、3、4、6、1、7、8、9、
2、5、3、4、1、6、7、8、9、
2、5、3、4、1、6、7、8、9、
2、3、5、4、1、6、7、8、9、
2、3、4、5、1、6、7、8、9、
2、3、4、1、5、6、7、8、9、
2、3、4、1、5、6、7、8、9、
2、3、4、1、5、6、7、8、9、
2、3、1、4、5、6、7、8、9、
2、3、1、4、5、6、7、8、9、
2、1、3、4、5、6、7、8、9、
1、2、3、4、5、6、7、8、9、
程序的实现逻辑很简单，变及数组，依次将两个数字做比较，如果小的在大的前面，那么换一个位置，否则位置不换，继续拿大的和后面的比较。重复实现逻辑，为什么外面循环用i--,呢，因为每次我们实现一次排序，总能得到一个最大值，这个值，一定是排在了这个数组的最后一个，所以，最后面的一个我们是不需要比较的，这样无形中也就减少了运算。
从代码实现上来看，冒泡排序的时间复杂度为：O(n2);简单的说执行速度，取决于for循环的次数，链表的大小。
选择排序（Selection sort）
选择排序是一种很直观简单暴力的排序算法，简单的说，就是，先遍历一遍数据，把最小的数据找出来，交换位置，放在第一位，然后在从把后面的链表继续遍历，找出最小数据，然后在，交换位置，继续遍历后续链表。直到全部遍历完成
private static void selectionSortOne(int a[]) {
long first =System.currentTimeMillis();
for (int i =0; i
int min = i;
for (int j = i; j
if (a[min] >a[j]) {
min = j;
}
}
int temp =a[i];
a[i] =a[min];
a[min] =temp;
}
long second =System.currentTimeMillis();
System.out.println(second -first);
printArrays(a);
}
从代码实现上来看，选择排序的时间复杂度为：O(n2);简单的说执行速度，取决于for循环的次数，链表的大小。
上面的排序，我们不难看出，每次排序，其实我们不仅可以找到最小值，还可以找到最大值，这种情况，我们可以将排序算法变化下
private static void selectionSortTwo(int a[]) {
long first =System.currentTimeMillis();
for (int i =0; i
int min = i;
int max = i;
for (int j = i; j
if (a[min] >a[j]) {
min = j;
}
if (a[max]
max = j;
}
}
if (min != max) {
int maxTemp =a[a.length - i -1];
a[a.length - i -1] =a[max];
a[max] =maxTemp;
int temp =a[i];
if (a[i] >a[min]) {
a[i] =a[min];
a[min] =temp;
}
}
}
long second =System.currentTimeMillis();
System.out.println(second -first);
printArrays(a);
}
每次排序同时将最小的放在最前面，将最大的放在最右边，循环的时候，也不需要每次都循环到链表的最后段，每次循环都踢掉链表的两端，在进行排序操作.
实际上这两种写法，在效率上相差并不大，下面那种虽然在循环次数上变少了，但是循环类的操作变复杂了。之所以这样写，只是说明下，我么并不是只能每次找最小的数，也可以按照需要，变换写法。
插入排序(Insertion Sort)
插入排序是一种最简单的排序算法，在数据量小的情况下，是一种非常有效的排序方式，
他的核心思想，保证轮询到的数据前面的链表部分是顺序的，将需要比较的数字和前面的排序完成的链表进行比较，插入到一个合适的位置。
public static void main(String[] args) {
int[] a =new int[20];
for (int i =0; i <20; i++) {
int random =(int) (Math.random() *10);
a[i] =random;
}
for (int i =1; i
int current =a[i];
int seq = i;
while (seq >0) {
int temp =a[seq -1];
if (current >=temp) {
break;
} else {
a[seq -1] =current;
a[seq] =temp;
}
seq--;
}
}
printArrays(a);
}
插入排序比较适合.属于稳定的排序，适合于数据量小，部分数据有序的情况排序。他比较依赖于原链表的混乱程度。
当链表是有序的，也就是最优情况下，每个数只要和前面的一个数想比较，就可以了。这时候的时间复杂度是O(n);
当然逆向来说，如果链表是有序的，但是和我们需要排序的规则是相反的，那么每个数字都要和前面的所有数字比较。这个时候，时间复杂度就变成了O(n2)
个人博客>>>常见排序算法（一）
