前言
在生活中，我们离不开排序，在数据结构中，排序算法也是很重要很经典的知识，更是每个程序员都必须得掌握的，在本篇我将总结一下常用的排序算法，便于自己以后复习。
冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。其算法思想是从要排序的数列的一端开始向另一端冒泡，也就是把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
原始冒泡排序
基本过程
- 相邻的元素两两比较，如果第一个比第二个大，就交换它们两个，这样在最后的元素将会是最大的数。
- 两层嵌套循环，外层冒泡轮数，里层依次比较，最后排序完成。
代码实现
/**
* 原始冒泡排序
* @param array
*/
public void bubbleSort(int[] array) {
int tmp;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
// 相邻元素两两比较
if (array[j] > array[j + 1]) {
// 元素交换
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}冒泡排序优化1-有序标记
冒泡排序算法的前提是无论数列是否有序无序，都会进行双层循环，但是如果数列在几轮排序之后已经有序了，没必要继续循环，浪费资源，在这种情况下，如果能判断出数列已经有序，并做出标记，那么剩下的几轮排序就不必执行了。
代码实现
/**
* 冒泡排序优化-有序标记
* @param array
*/
public void bubbleSortIsSort(int[] array) {
int tmp;
for (int i = 0; i < array.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < array.length - i - 1; j++) {
// 相邻元素两两比较
if (array[j] > array[j + 1]) {
// 元素交换
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
//因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false;
}
}
// 如果当前标记为true，则说明已是有序数组，直接跳出
if (isSorted) {
break;
}
}
}冒泡排序优化2-有序区界定
在上一步优化的基础上还可以继续优化，如果数列已经有一大部分原始是排好序的，比如数组{3,2,5,7,9}，可以看到后边{5,7,9}已经是排好序的，那我们就没必要继续进行比较了，那么，该如何避免这种情况呢？我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。
代码实现
/**
* 冒泡排序优化-有序区界定
* @param array
*/
public void bubbleSortBorder(int[] array) {
int tmp;
// 最后一次交换的位置
int lastExchangeIndex = 0;
//无序数列的边界
int sortBorder = array.length - 1;
for (int i = 0; i < array.length - 1; i++) {
//有序标记，每一轮的初始值都是true
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
// 相邻元素两两比较
if (array[j] > array[j + 1]) {
// 元素交换
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
//因为有元素进行交换，所以不是有序的，标记变为false
isSorted = false;
// 更新为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
// 如果当前标记为true，则说明已是有序数组，直接跳出
if (isSorted) {
break;
}
}
}鸡尾酒排序
鸡尾酒排序算法的思想
在无规律排放的数组中，先从左到右冒泡排序，则最大的元素去到最右端；再先从右到左冒泡排序，则最大的元素去到最左端。以此类推，直到完成排序。
考虑这样的一个序列：{2,3,4,5,1} 。如果使用鸡尾酒排序，一个来回就可以搞定；而冒泡排序则需要跑四趟。
代码实现
/**
* 冒泡排序优化-鸡尾酒排序（适用于大部分元素已经有序的情况）
* @param array
*/
public void bubbleSortTwo(int[] array) {
int tmp;
for (int i = 0; i < array.length / 2; i++) {
// 有序标记
boolean isSorted = true;
//奇数轮，从左向右比较和交换
for (int j = 0; j < array.length - i - 1; j++) {
// 相邻元素两两比较
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
isSorted = false;
}
}
if (isSorted) {
break;
}
// 在偶数轮之前，将isSorted重新标记为true
isSorted = true;
// 偶数轮，从右向左比较和交换
for (int j = array.length - i - 1; j > i; j--) {
// 相邻元素两两比较
if (array[j] < array[j - 1]) {
tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}鸡尾酒排序优化
同冒泡排序的有序区界定优化类似，我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。因为鸡尾酒是两边循环交替，因此需要设置两个边界值来判断。
代码实现
/**
* 鸡尾酒排序优化-有序区界定（适用于大部分元素已经有序的情况）
* @param array
*/
public void bubbleSortTwoBorder(int[] array) {
int tmp;
// 左侧最后一次交换的位置
int leftExchangeIndex = 0;
// 右侧最后一次交换的位置
int rightExchangeIndex = 0;
// 无序数组的左边界
int leftSortBorder = 0;
// 无序数组的右边界
int rightSortBorder = array.length - 1;
for (int i = 0; i < array.length / 2; i++) {
// 有序标记
boolean isSorted = true;
//奇数轮
for (int j = leftSortBorder; j < rightSortBorder; j++) {
// 相邻元素两两比较
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
isSorted = false;
rightExchangeIndex = j;
}
}
rightSortBorder = rightExchangeIndex;
if (isSorted) {
break;
}
// 偶数轮
isSorted = true;
for (int j = rightSortBorder; j > leftSortBorder; j--) {
// 相邻元素两两比较
if (array[j] < array[j - 1]) {
tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
isSorted = false;
leftExchangeIndex = j;
}
}
leftSortBorder = leftExchangeIndex;
if (isSorted) {
break;
}
}
}性质
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(1) |
| 稳定性 | 稳定 |
面经：
