常用排序算法总结

1、冒泡排序

重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2、选择排序

每次找出最小/最大，确定一个位置

选择排序的交换操作介于0和(n − 1)次之间。选择排序的比较操作为n(n − 1) / 2次之间。选择排序的赋值操作介于0和3(n − 1)次之间。

比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

3、SHELL排序（分组插入）

也称为递减增量排序算法，是插入排序的一种高速而安定的改良版。

对有n个元素的可比较资料，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

4、插入排序

在已有序列将元素逐个插入到适应的位置

缺点：需移动元素位置

改进：二分查找插入

5、快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列sub-lists。

步骤为：

Ø 从数列中挑出一个元素，称为 "基准"（pivot），

Ø 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。

Ø 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

Ø 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

6、归并排序（分治法）



算法描述

Ø 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

Ø 设定两个指针，最初位置分别为两个已经排序序列的起始位置

Ø 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位

Ø 重复步骤3直到某一指针达到序列尾

Ø 将另一序列剩下的所有元素直接复制到合并序列尾

7、堆排序

选择排序的升级，减小比较次数，利用堆性质，每次找出最大和最小，交换位置后再次构造堆，直到排好序。

Ø 初始化操作：将R[1..n]构造为初始堆；

Ø 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

Ø 重复

8、箱排序

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

分配过程的时间是O(n)；收集过程的时间为O(m) （采用链表来存储输入的待排序记录）或O(m+n)。因此，箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n)，则箱排序的时间是线性的，即O(n)。