快速排序
描述
快速排序由C.A.R.Hoare在1962年提出，是冒泡排序的一种改进。其基本思想为：通过一趟排序将待排序数据分割成独立的两部分，其中一部分的所有值都比另一部分的所有值都小，然后再对分割的两部分分别进行快速排序，整个过程可以递归进行，最终所有数据变为有序序列。
特点
设待排序数组为a[0],a[1],…a[n-1]，快速排序步骤为：
1.初始化两个变量i、j，刚开始i=1，j=n-1。
2.将第一个元素a[0]作为基准数。
3.从i开始向后搜索，找到第一个大于基准数的元素a[i]。
4.从j开始向前搜索，找到第一个小于基准数的元素a[j]。
5.将a[i]与a[j]互换。
6.重复3到5步骤，直到i=j，然后将a[0]与a[j-1]对换。
7.序列被基准数分割成两个分区，前面分区全部小于基准数，后面分区全部大于基准数。
8.递归对分区子序列进行快速排序，最终完成整个排序工作。
每趟快速排序的核心工作是：选一个元素作为基准数，然后将所有比它小的数都放到它前面，大于它的都放在它后面。
选择排序
描述
选择排序是一种很简单直观的排序算法，主要思想就是每次从待排序的元素中选择出最大或最小的那个元素，然后将其放至已排序序列的末尾，直到全部待排序序列都排序完毕。
特点
1.初始状态时，待排序序列为a1,a2,…an，已排序序列为空。
2.第一趟排序，从待排序序列中找到最大或最小元素ak，将其与待排序序列的第一个元素a1对换，此时已排序序列为ak，长度为增加1，待排序序列长度减少1，变为n-1，其中ak被抽走了。
3.第二趟排序，从待排序序列中找到最大或最小元素aj，将其与待排序序列的第一个元素a2对换，此时已排序序列为ak,aj，长度增加1，变为2，待排序序列长度减少1，变为n-2，其中aj又被抽走了。
4.不断进行上面的排序操作，直到经过n-1趟排序后完成整个序列的排序。最终待排序序列为空，已排序序列长度为n。
冒泡排序
描述
冒泡排序是一种很简单的排序算法，主要思想就是不断走访待排序序列，每次只比较两个相邻元素，如果这俩元素顺序不符合要求则对换它们，不断重复知道没有相邻元素需要对换。在不断走访比较过程中，越大的元素经过交换会慢慢走到数列顶端，所以看起来它就像气泡一样不断往上冒，于是就叫冒泡。
特点
1.比较相邻两个元素，如果前一元素比后一元素大则对换它们的位置。
2.从头开始对每一对相邻元素都执行1的对比工作，直至结尾最后一对，执行完一轮后，该轮最大的元素被换置到最后。
3.针对所有元素执行若干轮1和2操作，每次经过2操作后都会将该轮的最大值换置到该轮最后，而最后元素不参与下一轮。
4.每一轮对越来越少的元素重复3操作，直至没有任何一对元素需要比较。
希尔排序
描述
希尔排序是希尔（Donald Shell）提出的一种排序方法，也属于插入排序，是简单插入排序的高效版本，也称为缩小增量排序。基本思想是将待排序元素进行增量分组，然后在分组组内进行插入排序，随着增量的减少，每个分组组内的元素越来越多，直至增量减至1时，所有元素都分到同一个组内，执行插入排序后完成整个排序操作。
特点
希尔排序
合并排序
描述
合并排序也叫归并排序，它的主要思想是分治法，把待排序序列分为若干有序子序列，然后将两个或两个以上的有序子序列进行合并，得到一个新的完整的有序序列。所以首先得先对子序列进行排序，得到有序子序列，然后再使序列段之间有序。
特点
既然是分治法，那么就涉及到分和治。分，即递归地将序列分成小序列再求解；治，即递归地将分成的小序列合并到一起。
1.设序列长度为L，将序列分为两个长度为(L/2)的子序列。
2.继续递归地对两个子序列分割，直至不能再继续分割，此时每个子序列只有一个元素。
3.对分割后的子序列进行递归地合并，按一定顺序组合成有序子序列，有序子序列之间继续合并。
4.最终合并成一个完整的长度为L的有序序列。
桶排序
描述
桶排序即Bucket Sort，也称箱排序。其基本思想是将待排序数组分配到若干个桶内，然后每个桶内再各自进行排序，桶内的排序可以使用不同的算法，比如插入排序或快速排序，属于分治法。每个桶执行完排序后，最后依次将每个桶内的有序序列拿出来，即得到完整的排序结果。
特点
桶排序
插入排序
描述
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
网友评论