以下是数据结构中有关排序算法的干货。建议背诵。
排序算法的分类
- 插入类排序：直接插入排序、折半插入排序、希尔排序
- 交换类排序：起泡排序、快速排序
- 选择类排序：简单选择排序、堆排序
- 归并类排序：二路归并排序
- 基数类排序：多关键字排序
排序算法代码（Java）
交换类
/**
* <h4>冒泡排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>1) 最坏情况：基本操作执行次数：n(n-1)/2,时间复杂度为O(n^2)</li>
* <li>2) 最好情况：时间复杂度为O(n)</li>
* <li>3) 空间复杂度为O(1)</li>
* </ul>
* </p>
*
* @Param arr
*/
public static void bubbleSort(int[] arr) {
int temp;
for (int i = arr.length - 1; i > 0; i--) {
boolean flag = false;
for (int j = 1; j <= i; j++) {
if (arr[j - 1] > arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
flag = true;
}
}
if (!flag)
return;
}
}
/**
* <h4>快速排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>1) 最坏情况：时间复杂度为O(n^2)</li>
* <li>2) 最好情况：时间复杂度为O(nlog_2n)</li>
* <li>3) 空间复杂度为O(log_2n)</li>
* </ul>
* </p>
*
* @param arr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
int temp, i = left, j = right;
if (left < right) {
temp = arr[left];
while (i != j) {
while (i < j && arr[j] > temp)
j--;
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < temp)
i++;
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = temp;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
}
插入类
```java
/**
* <h4>直接插入排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>1) 最坏情况：基本操作执行次数：n(n-1)/2,时间复杂度为O(n^2)</li>
* <li>2) 最好情况：时间复杂度为O(n)</li>
* <li>3) 空间复杂度为O(1)</li>
* </ul>
* </p>
*
* @param arr
*/
public static void straightInsertSort(int[] arr) {
int temp, j;
for (int i = 1; i < arr.length; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
```
```java
/**
* <h4>折半插入排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>1) 最坏情况：基本操作执行次数：n(n-1)/2,时间复杂度为O(n^2)</li>
* <li>2) 最好情况：时间复杂度为O(n)</li>
* <li>3) 空间复杂度为O(1)</li>
* </ul>
* </p>
*
* @param arr
*/
public static void binaryInsertSort(int[] arr) {
int i, j, low, high, m, t;
for (i = 1; i < arr.length; i++) {
low = 0; // 每次折半查找都要将low置为第0个位置
t = arr[i];
high = i - 1;
while (low <= high) {
m = (low + high) / 2;
if (arr[m] > t)
high = m - 1;
else
low = m + 1;
}
for (j = i - 1; j >= low; --j)
arr[j + 1] = arr[j];
arr[j + 1] = t;
}
}
```
```java
/**
* <h4>希尔排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>1) 最坏情况：时间复杂度为O(n^2)</li>
* <li>2) 最好情况：时间复杂度为O(nlog_2n)</li>
* <li>3) 空间复杂度为O(1)</li>
* </ul>
* </p>
*
* @param arr
*/
public static void shellSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
// 增量
int incrementNum = arr.length / 2;
while (incrementNum >= 1) {
for (int i = 0; i < arr.length; i++) {
// 进行插入排序
for (int j = i; j < arr.length - incrementNum; j = j + incrementNum) {
if (arr[j] > arr[j + incrementNum]) {
int temple = arr[j];
arr[j] = arr[j + incrementNum];
arr[j + incrementNum] = temple;
}
}
}
// 设置新的增量
incrementNum /= 2;
}
}
```
选择类
/**
* <h4>选择排序</h4>
*
* <p>
* 复杂度分析：<br/>
* <ul>
* <li>基本操作执行次数：n(n-1)/2,时间复杂度为O(n^2)</li>
* <li>空间复杂度为O(1)</li>
* </ul>
* </p>
*
* @param arr
*/
public static void simpleSelectSort(int[] arr) {
int i, j, minIndex, t; // minIndex是最小元素的下标
for (i = 0; i < arr.length; i++) {
minIndex = i;
for (j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
t = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = t;
}
}
/**
* <h4>堆排序</h4>
*
* <h5>复杂度分析</h5>
* <h6>时间复杂度</h6>
* <p>
* 对于sift()函数,
* 显然j走了一条从当前节点到叶子节点的路径，完全二叉树的高度为log_2(n+1)向上取整，即每个节点调整的时间复杂度为O(log_2n)。
* </p>
* <p>
* 对于heapSort()函数，基本操作总次数应该是两个并列的for循环中基本操作次数相加，第一个循环的基本操作次数为O(log_2n)*n/2，第二个循环基本操作次数为O(log_2n)*(n-1)，因此，整个算法的基本操作次数为O(log_2n)*n/2+O(log_2n)*(n-1),化简得O(nlog_2n)。
* </p>
* <h6>空间复杂度</h6>
* <p>
* 空间复杂度为O(1)。
* </p>
* <h5>应用说明</h5>
* <p>
* 堆排序适合的场景是记录很多的情况，典型的例子是从10 000个记录中选出10个最小 的，这种情况用堆排序最好。如果记录数较少，则不提倡使用堆排序。
* </p>
*
* @param arr
*/
public static void heapSort(int[] arr) {
/* i = arr.length / 2 - 1表示从最后一个非叶结点开始，依次向前调整， 全部非叶结点都调整好后，就建成了一个堆。 */
for (int i = arr.length / 2 - 1; i >= 0; i--) { // 创建堆
/*
* 注意：Java的数组是从0开始的，对于完全二叉树的数组存储的数据结构来说，最后一个非叶结点的索引是 arr.length / 2
* - 1
*/
sift(arr, i, arr.length - 1); // 调整的i位置处的节点，调整后，其连带的子节点若不满足定义，也会自动调整。
}
/* */
for (int i = arr.length - 1; i >= 1; i--) {
/*
* 下面三句是将堆的第0个元素(即根节点)与数组中第i个位置的节点交换。数组从i开始到最后都是有序部分，从0开始到i之前(不含i)，
* 是无序部分，也是堆部分。
*/
int t = arr[0];
arr[0] = arr[i];
arr[i] = t;
/*
* 因为交换后，原来的数组无序元素中最后一个元素(假设为b),
* 与堆得第一个元素(根节点，也是数组的第0个元素)交换后，b跑到堆得根部了，
* 此时堆中 唯一可能不满足堆的定义的节点只有b。因此，此处只调整根节点
*/
sift(arr, 0, i - 1);
}
}
/**
* 调整数组arr中low处的节点。数组arr从low处到high处构成一个堆。
* @param arr
* @param low
* @param high
*/
private static void sift(int[] arr, int low, int high) {
/* Java的数组是从0开始的，对于完全二叉树的数组存储的数据结构来说，这里i是父节点在数组中的索引，j是i的左儿子节点在数组中的索引 */
int i = low, j = 2 * (i + 1) - 1; // i是父节点在数组中的索引，j是左儿子节点在数组中的索引。
int t = arr[low]; // low是要调整的位置，用t记录该值,t是父节点的值
while (j <= high) { // 若i有左儿子和右儿子，或i只有左儿子，则执行循环
if (j < high && arr[j] < arr[j + 1]) // 若i有左儿子和右儿子，并且左儿子的值比右儿子的值小，则j指向右儿子。j指向的是i的较大的孩子。
j++;
if (t < arr[j]) { // 若父节点比它的较大孩子的值小
arr[i] = arr[j]; // 将父节点的较大孩子的值赋值给该父节点
/* 为了继续向下调整，要更新i和j的指向 */
i = j; // 更新i，令i指向刚刚调整过的孩子节点上
j = 2 * (i + 1) - 1; // j指向i的左儿子节点
} else // 若父节点不小于它较大的孩子节点，则调整结束
break;
}
arr[i] = t; // 被调整节点的值放入最终位置。
}
复杂度
1. 时间复杂度
- 平均情况下，快排、希尔排序、归并排序、堆排序的时间复杂度均为$O(n\log_2n)$,其他都是$O(n^2)$。一个特殊的是基数排序，其时间复杂度为$O(d(n+r_d))$.
- 最坏情况下，快速排序的时间复杂度为$O(n^2)$,其他都和平均情况下相同。
军训时，教官说：“快些以 $n\log_2n$ 的速度归队”，“快”指快速排序，“些”指希尔排序（谐音），“归”指归并排序，“队”指堆排序（谐音），这四种排序的平均复杂度都是$O(n\log_2n)$
2. 空间复杂度
快速排序$O(\log_2n)$，归并排序$O(n)$，基数排序$O(r_d)$，其他都是$O(1)$
3. 其他
直接插容易插变成$O(n)$，起泡起得好变成$O(n)$，所谓“容易插”和“起得好”都是指初始序列已经有序。
稳定性
心情不稳定，快些选一堆好友聊天吧！
“快” - 快速排序， “些” - 希尔排序（谐音），“选” - 简单选择排序， “堆” - 堆排序， 这4种是不稳定的，其他自然是稳定的。
细节
- 经过一趟排序，能够保证一个元素到达最终位置，这样的排序是：交换类的2种（起泡、快速）、选择类2种（简单选择、堆）
- 排序算法的元素比较次数和原始序列无关——简单选择排序和折半插入排序
- 排序算法的排序趟数和原始序列有关——交换类的排序
直接插入排序VS折半插入排序
二者的最大区别在于寻找插入位置的方式不同。直接插入按顺序查找的方式，而折半插入按折半查找的方式。
借助于“比较”进行排序的算法，在最坏情况下能达到的最好的时间复杂度为$O(n\log_2n)$
发表于 2024-3-2 00:17
|
发表于 2024-3-9 18:50
