排序算法
排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，性质也大多不同。
性质
稳定性
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 
和 ，且在原本的列表中 出现在 之前，在排序过的列表中 也将会是在 之前。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
选择排序、堆排序、快速排序、希尔排序不是稳定排序。
时间复杂度
主页面：复杂度
时间复杂度用来衡量一个算法的运行时间和输入规模的关系，通常用 表示。
简单计算复杂度的方法一般是统计「简单操作」的执行次数，有时候也可以直接数循环的层数来近似估计。
时间复杂度分为最优时间复杂度、平均时间复杂度和最坏时间复杂度。OI 竞赛中要考虑的一般是最坏时间复杂度，因为它代表的是算法运行水平的下界，在评测中不会出现更差的结果了。
基于比较的排序算法的时间复杂度下限是 的。
当然也有不是 的。例如，计数排序 的时间复杂度是 ，其中 代表输入数据的值域大小。
以下是几种排序算法的比较。
空间复杂度
与时间复杂度类似，空间复杂度用来描述算法空间消耗的规模。一般来说，空间复杂度越小，算法越好。
选择排序
定义
选择排序（英语：Selection sort）是一种简单直观的排序算法。它的工作原理是每次找出第 
最小的元素（也就是 中最小的元素），然后将这个元素与数组第 个位置上的元素交换。
性质
稳定性
由于 swap（交换两个元素）操作的存在，选择排序是一种不稳定的排序算法。
时间复杂度
选择排序的最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 
def selection_sort(a, n):
for i in range(1, n):
ith = i
for j in range(i + 1, n + 1):
if a[j] < a[ith]:
ith = j
a[i], a[ith] = a[ith], a[i]冒泡排序
定义
冒泡排序（英语：Bubble sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
过程
它的工作原理是每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。
性质
稳定性
冒泡排序是一种稳定的排序算法。
时间复杂度
在序列完全有序时，冒泡排序只需遍历一遍数组，不用执行任何交换操作，时间复杂度为
在最坏情况下，冒泡排序要执行
次交换操作，时间复杂度为
冒泡排序的平均时间复杂度为
代码实现
import java.util.Arrays;
class Main {
static void bubbleSort(int array[]) {
int size = array.length;
// 遍历数组中的每个元素以读取它们
for (int i = 0; i < size - 1; i++)
// 用一个循环比较数组的元素
for (int j = 0; j < size - i - 1; j++)
// 比较数组中的两个相邻元素
if (array[j] > array[j + 1]) {
// 如果元素不在正确的位置，就交换它们
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
public static void main(String args[]) {
int[] data = { 5, 3, 4, 1, 2 };
// 用 class 名调用方法
Main.bubbleSort(data);
System.out.println("Array sorted with bubble sort: ");
System.out.println(Arrays.toString(data));
}
}
// 输出：用冒泡排序法对数组进行排序： [1, 2, 3, 4, 5]