数据结构 排序的概念

数据结构-排序的概念


1、各种内排序方法可以归纳为以下五大类：
  1)插入排序
  2)交换排序
  3)选择排序
  4)归并排序
  5)基数排序

2、直接插入排序
  思路：
    每次从无序表中取出个元素，把它插入到有序表的合适位置，使有序表仍然有序。每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。
  方法：
    1)比较前两个数，然后把第二个数按大小插入到有序表中；
    2)把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；
    3)依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

3、折半插入排序
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
 
  注意：
    折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
    折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度为O(n^2)

4、链表插入排序
链表插入排序实际上是一个对链表遍历的过程。先将表置空为空表，然后依次扫描链表中每个结点，设其指针为p，搜索到p结点在当前子表的适当位置。

5、shell排序
  Shell排序属于插入排序的范畴，是对直接插入排序算法的改进。
直接插入排序在基本有序时效率较高，并且在序列规模不是很大时效率也很高，Shell排序就是针对这两点进行改进。
核心思想是：待排序列有n个元素，先取一个小于n的整数h1作为个增量，把待排序列以间隔h1分成若干子序列，子序列内使用插入排序；然后取第二个增量h2(< h1)，重复上述的划分和排序，直至所取的增量hl = 1 (h1 > h2 > ... > hl)。

这样不管序列多么庞大，在先前较大步长分组下每个子序列规模都不是很大，用直接插入效率很高；后面步长变小，子序列变大，但由于整体有序性越来越明显，排序效率依然很高，大大提高了时间效率。

6、冒泡排序
原理是临近的数字两两进行比较按照从小到大或者从大到小的顺序进行交换这样一趟过去后大或小的数字被交换到了后一位然后再从头开始进行两两比较交换直到倒数第二位时结束其余类似。

7、快速排序
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot)然后对数组进行分区操作使基准左边元素的值都不大于基准值基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。后每个元素都是在排序后的正 确位置，排序完成。
快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的终位置以便分治递归。