相关排序方式
- 选择、插入、归并、快速等等
| 算法 | 最坏时间 | 最好时间 | 最坏交换次数 | 是否原址 |
|---|---|---|---|---|
| 选择排序 | O(n^2) | O(n^2) | O(n) | 是 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | 是 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 是 |
| 快速排序 | O(n^2) | O(nlogn) | O(n2) | 是 |
选择排序
-
定义
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。 -
时间复杂度
O(n^2): n 表示数组的长度 -
是否原址
是（不需要借助其他数组） -
程序实现
public void sort(int A[]) {
for (int i = 0; i < A.length; i ++) {
int min = i;
for (int j = i + 1; j < A.length; j ++) {
if (A[j] < min) {
min = j;
}
}
// 最小值放到索引 i 的位置
int temp = A[min];
A[i] = A[min];
A[min] = temp;
}
}
插入排序
- 定义
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
-
时间复杂度
O(n^2): n 表示数组的长度 -
是否原址
是（不需要借助其他数组） -
程序实现
public void sort(int A[]) {
for (int i = 1; i < A.length; i ++) {
for (int j = i; j > 0 && A[j] < A[j - 1]; j --) {
// 交换下标j与下标j-1的值
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
}
}
}
- 缺点
在最坏的情况（数组逆序），数组元素移动的次数为O(n^2) - 与选择排序的对比
- 都是维护两个数组：左边的有序，右边的无序
- 插入排序在写入左边的数组时，需要寻找插入点。选择排序则是在现在右边找到最小的，然后直接写入左边数组的末尾。
- 插入排序在写入左边数组时，插入点后面的元素都要后移一位
归并排序
- 定义
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序使用分治法，将原问题分解为类似原问题的子问题。
-
时间复杂度
O(nlogn): n 表示数组的长度 -
是否原址
否（需要借助其他数组） -
程序实现
/**
* 归并排序
* @param A 数组
* @param p 要操作的起始位置
* @param r 要操作的终点位置
*/
public void mergeSort(int A[], int p, int r) {
if (p >= r) {
return;
}
// 分解为两个子问题
int q = (p + r) / 2;
mergeSort(A, p, q);
mergeSort(A, q + 1, r);
// 归并
merge(A, p, q, r);
}
public void merge(int A[], int p, int q, int r) {
int n1 = q - p + 1; // 数组左部长度
int n2 = r - q; // 数组左部长度
// 将数组copy到新数组中
int B[] = new int[n1 + 1];
int C[] = new int[n2 + 1];
System.arraycopy(A, p, B, 0, n1);
System.arraycopy(A, q + 1, C, 0, n2);
// 新数组的最后一位设置为最大值, 防止数组越界。这里应该设置为正无穷大，但需要用double。
// 这里先用int的最大值。所以数组不可以存在大于int最大值的元素
B[n1] = Integer.MAX_VALUE;
C[n2] = Integer.MAX_VALUE;
// 归并两个新数组
int i = 0, j = 0;
for (int k = p; k <= r; k ++) {
if (B[i] <= C[j]) {
A[k] = B[i];
i ++;
} else {
A[k] = C[j];
j ++;
}
}
}
- 缺点
需要额外的内存空间开销
快速排序
-
定义
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。 -
与归并排序的对比
归并：分解-》排序-》归并......
快速：粗略排序（数组分为做大右小两部分）-》分解（左右两部分）-》粗略排序...... -
时间复杂度
最好：O(nlogn): n 表示数组的长度
最坏：O(n^2)：数组本身就是有序的
平均：O(nlogn) -
是否原址
是（不需要借助其他数组） -
程序实现
/**
* 快速排序
* @param A 数组
* @param p 要操作的起始位置
* @param r 要操作的终点位置
*/
public void quickSort(int A[], int p, int r) {
if (p >= r) {
return;
}
// 将数组分解为左右两部分(两部分都是无序的，但右边的都比左边的大)，
// 并获取中间索引
int q = partTition(A, p, r);
// 将左右两部分递归排序
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
public int partTition(int A[], int p, int r) {
int q = p;
// 这里将r设置为主元（在数组
for (int u = p; u < r; u ++) {
if (A[u] < A[r]) {
int temp = A[q];
A[q] = A[u];
A[u] = temp;
q ++;
}
}
int temp = A[q];
A[q] = A[r];
A[r] = temp;
return q;
}
- 缺点
若排序时，主元为最大的，为最差情况，递归次数最多。
比如，数组本身有序，主元为最后一个元素，那么拆分后的左右两个数组，其中一个为原数组长度-1，每次拆分-1，最多需要拆分2n-1次
网友评论