排序的几种方法及大体思想

插入排序

插入排序分为直接插入排序和希尔排序。

直接插入排序的思想：

顺序地把带待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大，当子集合大小最终和集合大小相同时排序完毕。

希尔排序的思想：

       把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序，小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。

 

交换排序

交换排序分为冒泡排序和快速排序。

冒泡排序的思想：

       从数组第一个元素开始，两两之间进行比较，如果前面一个大于后面一个，就互换位置，这样一趟下来之后，元素最大的的一个将会放在数组的最后，然后第二趟除去最后一个最大的元素，然后在按照前面的方法，会将数组中第二大的元素放在倒数第二个位置，这样，如果数组有n个元素，那么经过n-1次排序之后，数组就变成有序的了。

快速排序的思想：

       找一个元素（一般选择第一个元素），以它的关键字作为“中点”，凡其关键字小于中点的元素均移动至该元素之前，反之，凡关键字大于中点的元素均移动至该元素之后。这样一次过程结束之后，位于标准元素左边子数组中的元素的关键字均小于标准元素的关键字，位于标准元素右边子数组中元素的关键字均大于或等于标准元素的关键字。对这两个子数组中的元素分别再进行方法类同的递归快速排序，知道每个子序列只有一个元素为止。

 

归并排序

（二路）归并排序的思想：

       先将数组中的两两作为一组，进行排序，排好序之后在将上面的两个一组看成一组继续排序，知道最后只剩一组为止。通过“归并”两个或两个以上的有序子序列，逐步增加记录有序序列的长度，最终 “归并”为一个有序序列。

选择排序

选择排排序分为直接选择排序和堆排序。

直接选择排序的思想：

       从待排序的数据元素集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取关键字最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。

堆排序的思想：

       暂时空缺。

 排序.doc