一、冒泡排序
冒泡排序是一种交换排序，基本思想就是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
下面给出 3 种冒泡排序，性能依次提升。
- 1.最简单的冒泡排序：
从第一个开始不断地和其他进行比较，如果大于其他的那么久互换数据，一轮下来第一个就会变成最小的一个。然后循环比较第二个，指导最后一个。这种事最简单的冒泡排序，时间复杂度为 O(n^2)。性能有待提升。
example：
/**
* 最简单的冒泡算法，依次比较两个记录的大小 如果 i > j,则交换两者，
*
* 一轮下来，i 将是最小的。
*
* 但是这样的效率很低，时间复杂度是 o(n^2)。
*/
public static void bubbleSort(int[] data) {
if (data == null || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
for (int i = 0; i < data.length; i++) { //每一轮下来 data[i] 将是最小的值
for (int j = i + 1; j < data.length; j++) {
if (data[i] > data[j]) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
}
- 2.改进的冒泡排序
假如我们不从头开始比较，然而从末尾开始比较，那么就能像冒泡那样，将最小值从末位提到首位。那么会对我们下次比较有帮助。
example:
/**
* 改进冒泡排序方法 从数组后端开始比较，将最小的数值从末端移到最前端
*/
public static void betterBubbleSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
for (int i = 0; i < data.length; i++) {
for (int j = data.length - 2; j >= i; j--) { //从末端开始比较，将最小的往上移动，就像冒泡过程
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
- 3.性能最优的冒泡排序
我们在改进版的冒泡排序的基础上发现，其实从末端往前比较的时候，假如一直没有发生交换，那么这个序列本身就是有序的，我们就不需要重复做这么多比较工作了。所以我们在改进版的基础上添加一个标志位表示我们是否需要再比较一次。
example：
/**
* 更好性能的冒泡排序，在改良版的冒泡排序中添加 flag 反映上一次从下往上 的比较是否已经有序了
*/
public static void bestBubbleSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
boolean notOrdered = true;
for (int i = 0; i < data.length && notOrdered; i++) { //假如已经有序
notOrdered = false;
for (int j = data.length - 2; j >= i; j--) {
//从末端开始比较，将最小的往上移动，就像冒泡过程
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp; //有交换就是无序，需要继续比较
notOrdered = true;
}
}
}
}
二、简单选择排序
简单选择排序的思想就是：每一趟在 n - i（i = 0,1,......n-1）个记录中选出关键字最小的记录，并和第 i （i = 0,1,......n-1）个记录作交换。
时间复杂度和冒泡排序相同，都是 O(n^2)，但比冒泡排序减少了交换数据的操作，性能要好一点。
example:
/**
* 简单选择排序
*/
public class WDSelectSort{
public static void selectSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
//标志最小记录的位置
int min = 0;
for (int i = 0; i < data.length; i++) { //假设最小的记录位置是 i
min = i; //找到剩下的 n - i 个记录中最小元素的位置
//跟冒泡排序的区别就是 找到但不替换
for (int j = i + 1; j < data.length; j++) {
if (data[min] > data[j]) {
min = j;
}
}
//找到之后和第 i 个进行比较，将最小的置为第 i 个
if (min != i) {
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
}
public static void main(String[] args) {
int[] data = { 13, 4, 3, 6, 9, 1, 5, 7 };
for (int i : data) {
System.out.printf(i + " ");
}
selectSort(data);
System.out.println("");
for (int i : data) {
System.out.printf(i + " ");
}
}
}
三、直接插入排序
直接插入排序的思想就是：将一个记录和已经有序的序列进行比较，将有序的序列中大于此记录的元素往后移，挪出一个合适的位置给待插入的记录，最后插入该元素到合适的位置，这样就能排好序了。
时间复杂度和冒泡排序以及简单选择排序相同，都是 O(n^2)，但比冒泡排序和简单选择排序性能要好一点。
example：
/**
* 直接插入排序
*/
public class WDInsertSort {
public static void insertSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
int i = 0;
int j = 0;
//临时变量保存当前比较位置的值
int temp = -1;
//从 1 开始，是假定第 0 个已经是排序好了的
for (i = 1; i < data.length; i++) {
j = i;
//保存当前比较位置的值，为了以后插入到合适的位置
temp = data[i];
//比较 i 位置之前的元素和 i 位置的元素的大小，大的右移，小的不动
while (j > 0 && data[j - 1] > temp) {
data[j] = data[j - 1];
//退出循环后，j 位置将是临时变量应该在的位置
j--;
}
//将临时变量插进应该在的位置
data[j] = temp;
}
}
public static void main(String[] args) {
int[] data = { 2, 4, 3, 6, 9, 1, 5, 7 };
for (int i : data) {
System.out.printf(i + " ");
}
insertSort(data);
System.out.println("");
for (int i : data) {
System.out.printf(i + " ");
}
}
}
四、堆排序
堆是具有如下性质的完全二叉树：每个结点的值都大于或者等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于左右孩子结点的值，称为小顶堆。
堆排序的思路：将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根结点，将它和堆数组的末尾元素交换，此时末尾元素就是最大值了。然后将剩下的 n-1 个序列重新构造成大顶堆，这样就能得到 n 个元素中的次大值。反复执行就能得到一个有序序列了。
堆排序的时间复杂度比冒泡排序、简单选择排序和直接插入排序好很多，为 O(nlogn)。
example：
/**
* 堆排序
*/
public class WDHeapSort {
/**
* 堆排序
*
* 将 n 个元素构造出一个大顶堆，然后将堆顶元素和末端元素互换， 这样末端元素就是最大值了。
*
* 然后将剩下的 n-1 个元素同样构造成 大顶堆，再将堆顶元素和倒数第二个元素互换就得到了次大值元素。
*
* 反复执行，直到最后整个序列都有序。
*/
public static void heapSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
//从完全二叉树的最下层的最右边的非终端结点开始构建
int i = data.length / 2;
//将 n 个元素构造成大顶堆
for (; i >= 0; i--) {
heapAdjust(data, i, data.length - 1);
}
for (i = data.length - 1; i > 0; i--) {
//将堆顶元素（最大值）和 序列末端元素互换
swap(data, 0, i);
//将剩下的 1..i-1 个元素再构造成大顶堆，然后重复这个操作
heapAdjust(data, 0, i - 1);
}
}
/**
* 构造大顶堆
*
* 从完全二叉树的最下层的最右非终端结点当成根结点，将其子树调整成大顶堆。
*
* 然后递归到最顶层的根结点。
*
* @param startIndex
* 开始调整的根结点在数组中的位置
* @param endIndex
* 数组中最后一个元素的位置
*/
private static void heapAdjust(int[] data, int startIndex, int endIndex) {
int temp = data[startIndex];
int j;
//根据完全二叉树的性质，当前结点序号为 j,其左孩子的序号一定是 2*j+1,右孩子为 2*j +2
for (j = 2 * startIndex + 1; j <= endIndex; j = j * 2 + 1) {
//循环遍历其结点的孩子
//找到孩子中的较大值
if (j < endIndex && data[j] < data[j + 1]) {
j++;
}
if (temp > data[j]) {
//根结点比孩子结点大，不需要更换值
break;
}
//将孩子结点的较大值和根结点的值互换
data[startIndex] = data[j];
//将孩子结点的位置传递给 startIndex
startIndex = j;
}
//完成孩子结点值和根结点值的互换操作
data[startIndex] = temp;
}
/**
* 互换两个数组的值
*
* @param data
* @param i
* @param j
*/
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) throws Exception {
int[] data = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
for (int i : data) {
System.out.printf(i + " ");
}
heapSort(data);
System.out.println("");
for (int i : data) {
System.out.printf(i + " ");
}
}
}
五、归并排序
归并排序思路：假设初始序列含有 n 个元素，可以看成 n 个有序的子序列，每个子序列长度为 1。然后两两合并，就得到了 ⌈n/2⌉（大于或等于 n/2 的最小整数） 个长度为 2 或者 1 的有序子序列，再两两合并，循环执行，直到得到一个长度为 n 的有序序列为止。
关键是要懂得如何分成两个子序列，然后合并。
时间复杂度为 O(nlogn)，是一个稳定的排序。空间复杂度为 O(n+logn)。
example：
/**
* 归并排序， 稳定的排序
*/
public class WDMergeSort {
public static void mergeSort(int[] data, int low, int high) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
//取中间点作为分开序列的节点，分成左右两个子序列
int mid = low + (high - low) / 2;
//不能是等于，等于就说明这个子序列只有一个元素，不需要排序了
if (low < high) {
//递归排序左边子序列
mergeSort(data, low, mid);
//递归排序右边子序列
mergeSort(data, mid + 1, high);
//将左右子序列合并为有序的序列
merge(data, low, mid, high);
}
}
/**
* 将左右子序列合并
*
* 用临时变量将两个子序列合并成一个子序列，然后塞进去原来数组的开始比较的位置
*
* @param low
* 左边子序列起点位置
* @param mid
* 左边子序列终点位置
* @param high
* 右边子序列终点位置
*/
public static void merge(int[] data, int low, int mid, int high) {
//用于临时存放合并左右子序列的有序序列
int[] temp = new int[high - low + 1];
//左子序列开始的位置,左指针
int i = low;
//右子序列开始的位置，右指针
int j = mid + 1;
int k = 0;
//比较左右子序列，将它们合并在临时变量的数组中
while (i <= mid && j <= high) {
//左边子序列的元素较小，将左边的子序列的元素方法能够进去
if (data[i] <= data[j]) {
temp[k] = data[i];
k++;
i++;
} else {
temp[k] = data[j];
k++;
j++;
}
}
// 把左子序列剩余的元素移入数组
while (i <= mid) {
temp[k] = data[i];
k++;
i++;
}
// 把右子序列剩余的元素移入数组
while (j <= high) {
temp[k] = data[j];
k++;
j++;
}
//将临时变量中有序的序列填入原数组中开始排序的位置，所以要加 low 位移
for (int l = 0; l < temp.length; l++) {
data[l + low] = temp[l];
}
}
public static void main(String[] args) {
int a[] = { 51, 46, 20, 51, 18, 65, 97, 82, 30, 77, 50 };
System.out.println("排序前：" + Arrays.toString(a));
mergeSort(a, 0, a.length - 1);
System.out.println("排序结果：" + Arrays.toString(a));
}
}
六、快速排序
快速排序思路：将一个序列通过一个枢轴分成两个序列，左边的子序列小于枢轴，右边的子序列大于枢轴，然后再重复此操作将左右两个子序列排列。
关键是找枢轴的过程。
时间复杂度：O(nlogn)，空间复杂度：O(logn)。不稳定的排序。
example：
/**
* 快速排序 不稳定的排序
*/
public class WDQuickSort {
/**
* 快速排序
*
* 找出枢轴值，将序列分成两半，然后再快排
*
* @param data
* @param low
* @param high
*/
public static void quickSort(int[] data, int low, int high) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
//枢轴的位置
int pivot = 0;
if (low < high) {
//将序列根据枢轴分成两个序列，得出枢轴值
pivot = getPivot(data, low, high);
//对低子表快速排序，pivot 枢轴已经有序
quickSort(data, low, pivot - 1);
//对高子表快速排序
quickSort(data, pivot + 1, high);
}
}
/**
* 从一个序列中得到枢轴值，并且将序列变成左边的元素都小于或等于枢轴， 右边的元素都大于或等于枢轴值
*
* @param low
* 起始位置
*
* @param high
* 末尾位置
*
* @return 枢轴的位置
*/
public static int getPivot(int[] data, int low, int high) {
//以起始位置为枢轴值
int pivotKey = data[low];
while (low < high) {
//将比枢轴小的记录交换到左边
while (low < high && data[high] >= pivotKey) {
high--;
}
if (low < high) {
//退出循环后，data[high] 是右边小于等于枢轴的元素，应该放在左边
//这个 low 的位置就是刚好插入的位置
data[low] = data[high];
}
//将比枢轴大的记录交换到右边
while (low < high && data[low] <= pivotKey) {
low++;
}
if (low < high) {
//退出循环后，data[low] 是左边大于等于枢轴的元素，应该放在右边
//这个 high 的位置就是刚好插入的位置
data[high] = data[low];
}
}
//low 指针最后所在的地方就是枢轴的位置
data[low] = pivotKey;
return low;
}
public static void main(String[] args) {
int[] data = { 13, 4, 3, 6, 9, 1, 5, 7 };
for (int i : data) {
System.out.printf(i + " ");
}
quickSort(data, 0, data.length - 1);
System.out.println("");
for (int i : data) {
System.out.printf(i + " ");
}
}
}
七、希尔排序
希尔排序基本原理是：现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序。
因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。希尔排序是对直接插入排序算法的优化和升级。
所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，例如｛2,1,3,6,4,7,5,8,9｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，9 在第三位，2 在倒数第三位就谈不上基本有序。
希尔排序时间复杂度是 o(n^1.3)。
希尔排序流程图
example：
/**
* 希尔排序
*/
public class WDShellSort {
public static void shellSort(int[] data) {
if (null == data || data.length < 1) {
System.out.println("输入数据不合法");
return;
}
//直接排序中用来保存当前比较位置的元素的值
int temp = 0;
//增量
int increment = 0;
/* 设置增量为数组长度的一半，这样就能将第 0 个元素考虑进去了
拆分成若干个序列进行插入排序
最后的增量一定要是 1，因为最后要进行一次插入排序
*/
for (increment = data.length / 2; increment > 0; increment = increment / 2) {
//下面就是直接插入排序的算法了
for (int i = increment; i < data.length; i++) {
//保存当前比较位置的元素的值
temp = data[i];
int j = 0;
// j -= increment 保证了按照增量对子序列进行插入排序
for (j = i - increment; j >= 0; j -= increment) {
//如果大于当前的比较位置的值，那么就右移，否则不动
if (data[j] > temp) {
data[j + increment] = data[j];
} else {
//没有挪动位置，因为前面已经给有序了，所以退出循环
break;
}
}
//因为上面减了 increment，所以加上才是合适的插入位置
data[j + increment] = temp;
}
}
}
public static void main(String[] args) {
int[] data = { 2, 4, 3, 6, 9, 1, 5, 7 };
for (int i : data) {
System.out.printf(i + " ");
}
shellSort(data);
System.out.println("");
for (int i : data) {
System.out.printf(i + " ");
}
}
}
八、总结
常见算法的时间复杂度以及稳定性（有的排序我没写）
常见算法的时间复杂度以及稳定性
网友评论