基本排序简单介绍（一）
下一篇： 基本排序介绍（二）
提到数据结构，那就不得不提及一些排序的算法。废话不多说，下面上代码。
冒泡排序
冒泡排序是基于交换的一种算法， 时间复杂度为O(n^2)， 其核心算法是挨个两两比较， 如果后一个元素小于前一个元素，我们就交换这两个元素， 所以第一次排序后， 存放在末端的元素一定是数组中最大的元素。
/**
* @brief 冒泡排序
* @param arr 待排序数组
* @param length 待排序数组长度
*/
void bubbleSort(int arr[], int length) {
int save;
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
save = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = save;
}
}
}
}
选择排序
选择排序的核心在于将未排序数组分成两部分:
- 已经排序的部分
- 还未排序的部分
首先选择目前未排序的部分，找出未排序部分的最小值，将其插入到已经排序的部分的最后一位。因为我们排序的基本要求是在原数组上进行操作，所以我们实现“插入”操作的方法是交换。
/**
* @brief 选择排序
* @param arr 待排序数组
* @param length 待排序数组长度
*/
void selectSort(int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
int minIndex = i;
int save;
// 找到剩下的最小值的下标
for (int j = i + 1; j < length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
// 交换最小值 和 目前未排序的 第一个元素
save = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = save;
}
}
选择排序的时间复杂度为O(n^2)，因为每一次都会遍历剩余数找到最小值，所以选择排序的平均时间复杂度也为O(n^2)。
插入排序
插入排序的思想是边比较边交换。和简单选择排序一样，也需要将数组切分为两部分:
- 将要排序部分
- 未排序的部分
先默认放第一个数在已排序的部分。然后从第二个数开始，往前遍历，边查找边交换，直到发现比它小的数，停止查找交换（查找交换是一个动作）。这样这个数在这个部分里，一定是有序的。
/**
* @brief 插入排序
* @param arr 待排序数组
* @param length 待排序数组长度
*/
void insertSort(int arr[], int length) {
int save;
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j >= 1; j--) {
if (arr[j] < arr[j - 1]) {
save = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = save;
continue;
}
break;
}
}
}
插入排序的时间复杂度为O(n^2)
希尔排序
希尔排序依赖于直接插入排序的实现，希尔排序是一种缩小增量的直接插入排序。
希尔排序是一种优化的直接插入排序，其时间复杂度取决于增量序列。
1.希尔排序单次步骤
直接插入排序的增量为1，希尔排序只需将1变成增量序列中的值就行。
/**
* @brief 希尔排序单次排序
* @param arr 待排序数组
* @param length 待排序数组长度
* @param dk 步长
*/
void shellInsert(int arr[], int length, int dk) {
int save;
for (int i = 0; i < length - dk; i++) {
for (int j = i + dk; j >= dk; j -= dk) {
if (arr[j] < arr[j - dk]) {
save = arr[j - dk];
arr[j - dk] = arr[j];
arr[j] = save;
continue;
}
break;
}
}
}
2.希尔排序整体
不断的执行不同增量的排序
/**
* @brief 希尔排序
* @param arr 待排序数组
* @param arrLen 待排序数组长度
* @param dks 步长数组
* @param dksLen 步长数组长度
*/
void shellSort(int arr[], int arrLen, int dks[], int dksLen) {
for (int i = 0; i < dksLen; i++) {
shellInsert(arr, arrLen, dks[i]); // 不断执行不同步长的排序
}
}
3.增量数组的确立
希尔增量: {N/2, (N / 2)/2, ..., 1} // N为数组规模， 时间复杂度为O(n²)
Hibbard增量：{1, 3, 7, ..., 2^k-1} // 时间复杂度为O(n^(3/2))
Sedgewick：{1, 5, 19, 41, 109...} // 该序列中的项或者是94^i - 92^i + 1或者是4^i - 3*2^i + 1。
下一篇： 基本排序介绍（二）
