java中排序算法

   常用的排序算法有以下几类：插入排序（直接插入排序，希尔排序），选择排序（简单选择排序，堆排序），交换排序（冒泡排序，快速排序），归并排序，基数排序。排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量，进而影响整个软件的性能。 下面对这些算法一一的介绍他们究竟是怎么排的。

        

插入排序：

         直接插入排序 ：插入到已经排好序的数列中的一个数据。举一个形象的例子：在一个排好队打饭的对列中，张三是后来了，直接插到了队列中李四的后边，因为张三和李四是哥们儿。

         希尔排序 ：将所有的数据分组，小组内进行排序，之后重新分组，组内数据增多，重新排序（每个步骤都使用直接插入排序）。举一个形象的例子：还是排队打饭，学校有好多班级，不能所有班级都一起打，先按班级（分组）排好队，最后所有的班级再组成一个大组，再一个一个的排着打饭。

选择排序：

         简单选择排序 ：每次对剩余的数据中选择最小的和剩余的这些数据中的第一个进行交换。举个例子：毕业了，大家都在照毕业照，大家站在那里参差不齐，照相师傅一看，这可不行啊，瞅了一眼一下看到了最高的，好了，你就站到第一个，接着瞅剩下最高的，站第二个……最后就成了一个由高到低的队列

         堆排序 ：堆分为大顶堆（父节点大于子节点）和小顶堆（父节点小于子节点），根节点是最大的节点（或者最小的节点），每次挑出根节点之后，将剩余的节点进行重新建堆。

交换排序：

         冒泡排序 ： 从后到前（或者从前到后）相邻的两个两两进行比较，不满足要求就位置进行交换，一轮下来选择出一个最小（或最大）的放到了第一个位置上（或最后位置），之 后不考虑选出的元素，对剩余的元素进行循环的排列。再举一个例子：我们在火车站买票有军人、记者、两会代表优先的原则，大家排队买票，这时来了一个两会代 表买票，他从后往前问买票的人是否是军人、记者、两会代表，如果不是就和普通老百姓交换位置

         快速排序 ： 选 出一个关键字，比他小的放到他的左边，大的放到右边，设置两个指针，同时与关键字进行比较。举个例子：期末考试到了，考试完了我们要把成绩排序，我们先选 60为几个分数，大于等于60分的排到一边，小于60分的排到另一边，之后对小于60分的同学和大于60分的同学进行同样的排序。

归并排序：

归并排序  就是相邻两个元素组成一个组，组内进行排序，之后再将组内元素增加，循环比较

基数排序：

         基数排序 就是先对各位进行比较，进行排序，再对十位进行比较，进行排序……最后对最高位进行比较，进行排序。举个例子：每年在大学里我们都要进行评优，什么样的学生是最优的学生？各方面都要进行比较——成绩、人品、道德等

 

最后我们来总结一下各类排序算法的时间复杂度和空间复杂度，并进行对比：