一、排序的基本概念
排序就是把一组记录（元素）按照某个域值的递增或递减的次序重新排列的过程。通常将用于排序的域称为排序域或排序项，其值称为排序码。在解决问题时，有序序列常常比无序序列更容易操作，解决问题的效率更高。如在有序序列上进行二分法查找会优于在无序序列上按顺序查找。
目前常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序等。
如果某种排序方法只通过对任意两个元素的比较进行排序，则该方法称为基于比较的排序（comparison sort），或简称为比较排序。常见的比较排序方法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序等。如果排序方法不是基于比较的，则可以简称为非比较排序。常见的非比较排序方法包括基数排序和计数排序等。桶排序是允许多种排序策略并存的混杂方法，但是其主要框架是比较排序，因此常被分类为非比较排序方法。
在评估排序算法的性能时，一般需要考虑如下因素。
（1）时间复杂度（time complexity)：即算法对一个序列进行排序时需要运算的次数关于序列长度的数量级。可以证明，基于比较的排序算法的平均时间复杂度不可能低于O(nlogn)，而部分非比较排序算法则可以突破这个复杂度瓶颈。
（2）空间复杂度（space complexity）：即算法在排序过程中需要使用的内存空间关于序列长度的数量级。在排序算法的评估中，一般不考虑存储序列本身所用的空间，而是评估排序算法所用的额外空间的复杂度。
（3）稳定性（stability）：对于稳定的排序算法，序列中若存在若干相同的元素，排序后相同元素的相对位置不变。插入排序、冒泡排序、归并排序、计数排序等算法通常是稳定的，选择排序、快速排序、堆排序等算法通常是不稳定的。具体的排序算法是否稳定与代码实现有关。
常见的比较排序方法如下表（n为待排序元素的数量，稳定性仅就排序方法的常见实现而言）
| 方法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 | 备注 |
| 冒泡排序 |  |  | O(1) | √ | |
| 选择排序 |  |  | O(1) | ╳ | 如果使用O(n)的额外空间，可以做到稳定排序，此时需要使用链表，或采用元素插入而非交换方式。 |
| 插入排序 |  |  | O(1) | √ | 最坏时间复杂度可以更准确地表示为O(n+d)，其中d为原始序列中的逆序数量 |
| 归并排序 | O(nlog n) | O(nlog n) | O(n) | √ | |
| 快速排序 | O(nlog n) |  | O(log n) | ╳ | 可用原址（in-place）操作来减少存储空间占用 |
| 堆排序 | O(nlog n) | O(nlog n) | O(1) | ╳ |
常见的非比较排序方法如下表（n为待排序元素的数量，稳定性仅就排序方法的常见实现而言）
| 方法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 | 备注 |
| 基数排序 |  |  | O(n+maxiwi) | √ | |
| 计数排序 | O(n+w) | O(n+w) | O(n+w) | √ | 如果使用O(n)的额外空间，可以做到稳定排序，此时需要使用链表，或采用元素插入而非交换方式。 |
| 桶排序 |  |  | O(n+w) | √ | 最坏时间复杂度可以更准确地表示为O(n+d)，其中d为原始序列中的逆序数量 |
二、冒泡排序
冒泡排序是一种基于相邻元素比较的简单排序算法。其基本思想是通过相邻元素之间的比较和交换使排序码较大的元素逐渐从顶部移向底部，而排序码较小的元素逐渐上移，就像水底下的气泡一样逐渐上冒。对于长度为n的序列a，冒泡排序算法的主要步骤如下：
（1）扫描序列n-1次；
（2）第 i 次比较时，从前往后比较相邻的两个元素，即比较a[j]与a[j+1]，其中1≤j≤n-i；
（3）每次比较时，若靠前的元素比靠后的元素大，则交换它们，否则不做操作。
冒泡排序需要扫描序列n-1次，第i次扫描进行n-i次比较操作，总共比较(n-1)+(n-2)+···+1=
次，故时间复杂度为
。
冒泡排序算法的额外空间复杂度为O(1)。
冒泡排序算法在遇到两个相邻的相同元素时不会产生交换，故冒泡排序是稳定的算法。
冒泡排序的优化方法：如果某次扫描没有元素交换，说明序列已经有序，可以结束冒泡排序。使用该方法，最优情况下初始序列有序，则只需要进行一次扫描，最优时间复杂度为O(n)；最坏情况下初始序列反序，冒泡排序仍需扫描n-1次，故最坏时间复杂度为
。
冒泡排序算法代码实现如下： 