所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1. 算法步骤 （1) 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 （2) 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 （3) 针对所有的元素重复以上的步骤，除了最后一个。 （4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2. 动图演示 3. 举例演示
待排数组：{21，10，52，4，9，2}
4. 什么时候最快 当输入的数据已经是正序时（都已经是正序了，当然不需要排序了。在走访一遍数列后发现没有一对数字需要交换，就可以结束了）。
5. 什么时候最慢 当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢？不过计算机可不知道你输入的是不是反序哈哈哈，所以它会走访n - 1遍数列后使得数列有序）。
6. Java实现冒泡排序
public void bubbleSort(int[] a) { int n = a.length; // 一共n-1趟排序 for (int i = 1; i < n; i++) { // 第i趟排序从第0个元素到第n-i个元素 for (int j = 0; j < n - i; j++) { if (a[j] > a[j + 1]) { int temp; temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } }7. 优化一 对于一些连片有序而整体无序的序列，如{2，4，6，8，7}，按照上面的排序方式，第一趟排序后将8和7交换后，该数组已经有序，接下来的3趟排序就是多余的。因此我们可以增加一个标志，如果某一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去，就可以结束排序。具体的实现代码请看下面:
public void bubbleSort(int[] a) { int n = a.length; // 第一次判断时，要将flag置为true，使得后续排序可以进行 boolean flag = true; for (int i = 1; i < n && flag; i++) { // 每趟排序前先将flag置为false，因为这一趟排序还没开始，当然没有元素进行交换了 flag = false; for (int j = 0; j < n - i; j++) { if (a[j] > a[j + 1]) { int temp; temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; // 有数据交换了，falg设置为true flag = true; } } } }8. 优化二 优化一仅仅适用于连片有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。但是对于前面大部分是无序而后边小半部分有序的数据(3，2，4，7，4，3，7，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。怎么优化呢？我们可以记下最后一次交换的位置，在最后一次交换的位置后面，必然是有序的，然后下一趟排序从第一个比较到上次记录的位置结束即可，具体的实现代码请看下面：
public void bubbleSort(int[] a) { int n = a.length; boolean flag = true; // 最后一次发生交换的位置 int rightPos = n; int right = n - 1; for (int i = 1; i < n && flag; i++) { flag = false; for (int j = 0; j < right; j++) { if (a[j] > a[j + 1]) { int temp; temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = true; // 记录发生元素交换的位置 rightPos = j; } } right = rightPos; // 下一次只需比较到rightPos这个位置即可 } }选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
1. 算法步骤 （1）首先在未排序序列中找到最小元素，存放到排序序列的起始位置。 （2）再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。 （3）重复第二步，直到所有元素均排序完毕。
2. 动图演示
3. 举例演示
待排数组：{5， 2， 8， 4， 9， 1}
4. Java实现选择排序
public static void selectionSort(int[] arr) { int len = arr.length; // 长度为len的数组，需要len - 1次排序 for (int i = 0; i < len - 1; i++) { // min：用来记录这趟遍历中，最小数的位置 int min = i; // 从i位置向后开始找有没有小于arr[min]的元素 for (int j = i + 1; j < len; j++) { if (arr[j] < arr[min]) min = j; } // 内层循环结束，找到本次循环的最小数，进行交换 if (i != min) { int temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } }5. 优化 选择排序的思想是在要排序的一组数中，选出最小的那个数，然后与第一位置的数进行交换；然后再剩下的数中，找出最小的那个数与第二个数进行交换，直到第 n-1 个数与第 n 个数比较为止。而二元选择排序，顾名思义，从待排序的数组中找出一个最大值和一个最小值，分别与第一个数、最后一个数进行交换，这样可以使选择排序的时间复杂度降低，所以外层循环从 n 次变为了 n/2 次。代码实现如下：
public void selectionSort(int[] arr) { int len = arr.length; int rightPos = arr.length - 1; // 每次都选出了最大和最小的元素，则一共需要len / 2次排序 for (int i = 0; i < len / 2; i++, rightPos--) { int max = i; int min = i; for (int j = i + 1; j <= rightPos; j++) { if (arr[j] > arr[max]) max = j; if (arr[j] < arr[min]) min = j; } // 将这一趟遍历中最大的元素放到rightPos这个位置上 int temp1 = arr[rightPos]; arr[rightPos] = arr[max]; arr[max] = temp1; if (i != min) { int temp = arr[i]; // 有一种特殊情况就是，这一趟遍历中，最小元素刚好在rightPos这个位置上 // 经过上面放置最大元素的操作，最小元素的位置已经变为max了 if (min == rightPos) { arr[i] = arr[max]; arr[max] = temp; } else { arr[i] = arr[min]; arr[min] = temp; } } } }插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1. 算法步骤 （1）将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 （2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2. 动图演示 3.Java代码实现
public void insertSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int temp = arr[i]; int j = i; // 将比i位置上的元素大的元素往后移动一个位置 while (j > 0 && temp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } if (j != i) arr[j] = temp; } }4. 优化 在上面介绍的插入排序算法的思想，它是从有序序列的最后一个元素开依次向前找出待排元素的位置。其实，为了找出待排元素的位置，我们可以用二分查找算法来找，这样可以减少查找的次数。具体代码实现如下：
public static void insertSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int temp = arr[i]; // 使用二分查找算法找出元素arr[i]该插入的位置 int low = 0; int high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] > temp) high = mid - 1; else low = mid + 1; } // 元素后移，为插入temp腾出空间 for (int j = i - 1; j >= low; j--) { arr[j + 1] = arr[j]; } arr[low] = temp; } }