数据结构的排序 数据结构中几种经典排序简介

除了归并排序以后，可以对其它6种排序进行分类，如下图：

选择排序：先将第一个位值上的数跟之后所有位置上的数依次进行比较，如果第一个位置上的数比第二个位置上的数大，则进行互换，然后继续将第一个位置上的数与第三个位置上的数进行比较，经过一轮的比较后，第一个位值上的数就是所有数中最小的一个，如此往复。

插入排序：给定的一组记录，将其分为两个序列组，一个为有序序列(按照顺序从小到大或者从大到小)，一个为无序序列，初始时，将记录中的第一个数当成有序序列， 剩下其他所有数都当做是无序序列组中的数据，然后将无序序列组中的数据插入到有序序列的适当位置。

冒泡排序：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较后，第n位上就是整个记录中最大的数，然后在对前n-1个记录进行第二轮比较，重复该过程直到进行比较的记录只剩下一个为止。

快速排序：将待排序记录分为独立的两个部分，左侧记录都是小于或等于轴值，右侧记录都是大于或等于轴值，然后分别对左侧部分和右侧部分重复前面的过程，也就是左侧部分又选择一个轴值，又分为两个独立的部分，如此继续。

希尔排序：是插入排序的操作，但是希尔排序并不是把一组记录看成一个整体，而将整个记录分为了若干组记录，然后在对每组记录进行插入排序。

堆排序：堆是一颗完全二叉树，先将一组拥有n个元素的序列构建成大顶堆或者小顶堆，在将根结点上的数跟堆最后一位数进行互换。

归并排序：将一个数组中每个元素都看成一个有序序列(数组长度为n)，然后将相邻两个有序序列合并成一个有序序列。