注意：本文中，所有算法的实现都是对数组进行单调递增（从小到大）的排序。
一、冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的大小顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
冒泡排序还有一种优化算法，就是设置一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。冒泡排序的时间复杂度未。
void sort(int[] nums) {
// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
boolean flag = true;
for (int i = 1; i < nums.length - 1; i++) {
for (int j = 0; j < nums.length - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
flag = false;
}
}
if (flag) break;
}
}
二、选择排序
选择排序是一种简单直观的排序算法，在未排序序列中找到最小（大）元素，放到已排序序列的末尾，重复该步骤直到所有元素均排序完毕。无论什么数据进去都是的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处就是不占用额外的内存空间。
void sort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int min = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) min = j;
}
if (min != i) swap(nums, i, min);
}
}
三、插入排序
插入排序，一般也被称为直接插入排序，时间复杂度为。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序]方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。
void sort(int[] nums) {
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for (int i = 1; i < nums.length; i++) {
// 记录当前需要插入的数据
int tmp = nums[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < nums[j - 1]) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = tmp;
}
}
四、希尔排序
五、归并排序
六、快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法分别对这两部分数据继续进行排序。快速排序的平均时间复杂度为。
算法步骤：
- 从数列中挑出一个元素，称为 "枢纽元素";
- 重新排序数列，所有元素比枢纽值小的摆放在枢纽前面，所有元素比枢纽值大的摆在枢纽的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）分别对小于枢纽值元素的子数列和大于枢纽值元素的子数列按步骤1和2进行排序；
void sort(int[] nums) {
int low = 0, high = nums.length - 1;
quickSort(nums, low, high);
}
void quickSort(int[] nums, int low, int high) {
if (low < high) {
int partitionIndex = partition(nums, low, high);
//对左分区进行排序
quickSort(nums, low, partitionIndex - 1);
//对右分区进行排序
quickSort(nums, partitionIndex + 1, high);
}
}
int partition(int[] nums, int low, int high) {
//这里选择当前子数组中的第一个元素作为枢纽元素，注意枢纽元素位置的不同，其代码实现也不同
int key = nums[low];
while (low < high) {
//将比枢纽元素小的元素交换到左端
while (low < high && nums[high] >= key)
high--;
swap(nums, low, high);
//将比枢纽元素大的元素交换到左端
while (low < high && nums[low] <= key)
low++;
swap(nums, low, high);
}
//返回枢纽所在位置
return low;
}
七、堆排序
堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的个序列重新构造成一个堆，这样就会得到n个元素的次最大值。如此反复执行，便能得到一个有序序列了。
