排序

排序（原文链接）

1、冒泡排序

基本思想：比较相邻的元素大小，将小的前移，大的后移，就像水中的气泡一样，最小的元素经过几次移动，会最终浮到水面上。原地排序，不需要返回值。

3、选择排序

基本思想：

第1趟，在待排序记录r1 ~ r[n]中选出最小的记录， 将它与r1交换；

第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；

以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

原地排序，不需要返回值

4、插入排序

当前需要排序的元素(array[i])，跟已经排序好的最后一个元素比较(array[i-1])，

如果满足条件继续执行后面的程序，否则循环到下一个要排序的元素。

缓存当前要排序的元素的值，以便找到正确的位置进行插入。

排序的元素跟已经排序好的元素比较，比它大的向后移动(升序)。

要排序的元素，插入到正确的位置。

5、基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），桶式排序

又称“桶子法”（bucket sort）或bin sort，顾名思义，

它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，

藉以达到排序的作用，基数排序法是属于稳定性的排序，

其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，

在某些时候，基数排序法的效率高于其它的稳定性排序法。

例如：对数组中的元素按照从低位到高位排序，对于[192,221,12,23]

第一轮按照个位数字相同的放在一组，是s[1] =[221],s[2]=[192,12],s[3]=23,

第二轮按照十位数字进行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],

第三轮按照百位数字进行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]

6、希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，

是直接插入排序算法的一种更高效的改进版本。

希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，

整个文件恰被分成一组，算法便终止。

7、桶排序

桶排序 (Bucket sort)或所谓的箱排序，顾名思义就是运用桶的思想来将数据放到相应的桶内，再将每一个桶内的数据进行排序，最后把所有桶内数据按照顺序取出来，得到的就是我们需要的有序数据

8、快速排序

快速排序（quickSort）

快速排序是对冒泡排序的改进

快排的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，

然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，

这个过程称为一趟快速排序。

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，

将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，

将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，

即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，

直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。

另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

时间复杂度：O(nlgn)

快速排序是原地排序，不需要返回值

递归：

栈：