【C/C++ 01】初级排序算法

排序算法通常是针对数组或链表进行排序，在C语言中，需要手写排序算法完成对数据的排序，排序规则通常为升序或降序（本文默认为升序），在C++中，<algorithm>头文件中已经封装了基于快排算法的 std::sort() 函数，但是快速排序是不稳定的排序算法，于是<algorithm>中还包含了 stable_sort() 函数，即保留了等值元素的相对顺序。

稳定性：通常，在排序算法中，稳定性是指如果两个元素在原始数组中的相对顺序保持不变，则在排序后它们的相对顺序也应该保持不变。换句话说，如果有两个相等的元素，它们的位置在排序之前是 a 和 b，且 a 在 b 的前面，那么在排序后，a 仍然应该在 b 的前面。

在进行排序算法之前，先定义一个用于交换元素位置的函数：

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

一、冒泡排序（Bubble Sort）

冒泡排序的核心算法是暴力求解思维，是指将所有元素都相互比较一次，若靠前的数比靠后的数大，则将两个数交换位置。

• 排序对象：数组
• 时间复杂度：
• 空间复杂度：
• 是否稳定：是

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; ++i){for (int j = 0; j < n - i - 1; ++j){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}}
}

二、插入排序（Insert Sort）

插入排序的核心算法是将当前遍历到的地方的末尾数据往前比较，找到合适的位置进行插入，直到遍历到最后一个数据。

• 排序对象：数组、链表
• 时间复杂度：
• 空间复杂度：
• 是否稳定：是

void InsertSort(int* arr, int n)
{int i = 1;for (; i < n; ++i){int j = i;int end = arr[j];while (j > 0 && arr[j - 1] > end){arr[j] = arr[j - 1];--j;}arr[j] = end;}
}

三、选择排序（Select Sort）

选择排序的算法核心是找到数组的最大值和最小值，将其和遍历数组的左右端进行交换，然后左端右移、右端左移。简易版的选择排序算法会只找一个最值进行交换。

• 排序对象：数组、链表
• 时间复杂度：
• 空间复杂度：
• 是否稳定：否

void SelectSort(int* arr, int n)
{int left = 0;int right = n - 1;while (left < right){int iMin = left; int iMax = right;for (int i = left; i <= right; ++i){if (arr[i] < arr[iMin])iMin = i;if (arr[i] > arr[iMax])iMax = i;} Swap(&arr[left], &arr[iMin]);if (left == iMax)iMax = iMin;Swap(&arr[right], &arr[iMax]);++left;--right;}
}