一、冒泡排序
冒泡排序：相邻元素进行比较和交换，将最大值逐步移至末尾。
c++ 代码解读复制代码template<typename T>
void bubbleSort(T arr[], int n) {
//n-1次冒泡(最后1次自然有序)
for (int i = 0; i < n - 1; i++) {
//每次冒泡，相邻两个元素进行比较，将当前数组中最大元素移至末尾
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
1.1、冒泡排序优化
1、优化方案1
由于冒泡排序采用相邻元素进行比较和交换，如果某次冒泡，未发生交换，则表示数组已经有序
c++ 代码解读复制代码template<typename T>
void bubbleSort1(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool isSwap = false; //记录本次遍历是否发生过交换
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
isSwap = true;
}
}
if (!isSwap) {
break;
}
}
}
2、优化方案2
c++ 代码解读复制代码template<typename T>
void bubbleSort2(T arr[], int n) {
int lastSwapPos = n - 1;//记录最后一次交换的位置,意味着后面的数组已经有序
int tempPos;
do {
tempPos = lastSwapPos;
lastSwapPos = 0;
for (int j = 0; j < tempPos; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
lastSwapPos = j;
}
}
} while (lastSwapPos > 0);
}
1.2、鸡尾酒排序(双向冒泡排序)
c++ 代码解读复制代码template<typename T>
void cocktailSort(T arr[], int n) {
int left = 0;
int right = n - 1;
while (left < right) {
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
right--;
for (int j = right; j > left; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
}
}
left++;
}
}
改进鸡尾酒排序
c++ 代码解读复制代码template<typename T>
void cocktailSort1(T arr[], int n) {
int left = 0;
int right = n - 1;
int swapPos = left;
while (left < right) {
for (int i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapPos = i;//此时记录向右冒泡最后一次交换位置
}
}
right = swapPos;//将最后一次交换位置作为右冒泡起点
for (int j = right; j > left; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
swapPos = j;//此时记录向左冒泡最后一次交换位置
}
}
left = swapPos;//将最后一次交换位置作为左冒泡起点
}
}
二、选择排序
选择排序：从数组中找到最小元素，放到第一位；然后找到第二小元素，放到第二位......
效率不高，但比冒泡排序要好，原因：
- 1、每次都需要遍历整个未排序数组
- 2、每次遍历只做一次元素交换（冒泡排序存在大量相邻元素交换）
c++ 代码解读复制代码template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++) {
//寻找[i,n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
改进后的选择排序，每次遍历，同时找到最大值和最小值
c++ 代码解读复制代码template<typename T>
void selectionSort1(T arr[], int n) {
int left = 0, right = n - 1;
while (left < right) {
int minIndex = left;
int maxIndex = right;
// 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
if (arr[minIndex] > arr[maxIndex]) {
swap(arr[minIndex], arr[maxIndex]);
}
for (int i = left + 1; i < right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
else if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
swap(arr[left], arr[minIndex]);
swap(arr[right], arr[maxIndex]);
left++;
right--;
}
}
三、插入排序
插入排序：将未排序元素依次插入到已排序的列表合适的位置，使得插入后依旧保持有序。
c++ 代码解读复制代码template<typename T>
void insertionSort(T arr[], int n) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
swap(arr[j], arr[j - 1]);
}
}
}
c++ 代码解读复制代码template<typename T>
void insertionSort1(T arr[], int n) {
for (int i = 1; i < n; i++) {
//寻找元素arr[i]合适的插入位置
T e = arr[i];
int j;//j保存元素e应该插入的位置
for (j = i; j > 0 && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1];
}
arr[j] = e;
}
}
四、希尔排序
希尔排序是插入排序的一种改进版，它的核心思想是分组插入排序，通过逐渐缩小的间隔来让元素移动得更有效。
比如一个数组是[8,3,6,2,4,5]，当gap是2的时候，分成两组，比如索引0、2、4为一组，1、3、5为另一组。分别对这些组进行插入排序。比如第一组8、6、4排序后变成4、6、8，第二组3、2、5排序后变成2、3、5，这样数组可能变成[4,2,6,3,8,5]。然后gap变为1，这时候就是普通的插入排序，整个数组变得容易排序了。
希尔排序的核心就是确定最优间隔
- 原始希尔序列：gap = n/2, n/4, ..., 1（时间复杂度约为O(n²)）。
- 优化序列：如Hibbard序列（2^k-1）、Sedgewick序列（9×4^k-9×2^k+1），可提升至O(n^(4/3))。
c++ 代码解读复制代码template<typename T>
void shellSort(T arr[], int n) {
int gap = 1;//间隔控制
while (gap < n / 3) {
gap = 3 * gap + 1;
}
while (gap >= 1) {
for (int i = gap; i < n; i++) {//插入排序
T e = arr[i];
int j = i;
for (; j >= gap && e < arr[j - gap]; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = e;
}
gap /= 3;
}
}
五、堆排序
c++ 代码解读复制代码template<typename T>
void __shiftDown(T arr[], int n, int k) {
T e = arr[k];
int j = 2 * k + 1; //从k的左子孩子开始往后shiftDown
while (j < n) {
if (j + 1 < n && arr[j + 1] > arr[j]) { //判断是否有右孩子，并比较左右孩子的大小
j++;
}
if (e >= arr[j]) {
break;
}
arr[k] = arr[j];
k = j;
j = 2 * k + 1;
}
arr[k] = e;
}
template<typename T>
void heapSort(T arr[], int n) {
//Heapify:创建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
__shiftDown(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]); //将最大值依次放到末尾
__shiftDown(arr, i, 0); //重新维护最大堆
}
}
六、归并排序
c++ 代码解读复制代码template<typename T>
void __merge(T arr[], int l, int mid, int r) {
T* aux = new T[r - l];
for (int i = l; i < r; i++) { //复制数据
aux[i - l] = arr[i];
}
int i = l, j = mid;
for (int k = l; k < r; k++) {
if (i >= mid) {//左子数组已归并结束，将右子数组剩余部分直接copy进归并数组即可完成归并
//由于右子数组剩余部分与归并数组剩余空间中的内容一致，可以省略copy步骤
//arr[k] = aux[j - l];
//j++;
break;
}
else if (j >= r) {//右子数组已归并结束，将左子数组剩余部分直接copy进归并数组即可完成归并
arr[k] = aux[i - l];
i++;
}
else if (aux[i - l] < aux[j - l]) {
arr[k] = aux[i - l];
i++;
}
else {
arr[k] = aux[j - l];
j++;
}
}
delete[] aux;
}
template<typename T>
void __mergeSort(T arr[], int l, int r) {
//if(r - l <= 1) //只有一个元素时，无需排序
// return;
//优化二：当元素较少时，采用插入排序
if (r - l < 16) {
insertionSort1(&arr[l], r - l);
return;
}
int mid = (l + r) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid, r);
//优化一：如果左半部分最后一个数<=右半部分第一个数，就不需要进行合并
if (arr[mid - 1] > arr[mid]) {
__merge(arr, l, mid, r);
}
}
template<typename T>
void mergeSort(T arr[], int n) {
__mergeSort(arr, 0, n);
}
归并排序的优化方案：
- 1、预先分配内存，避免频繁的分配和释放内存
- 2、不使用递归
七、快速排序
c++ 代码解读复制代码//对arr[l....r)部分进行partition操作
//返回p，使得 arr[l...p) < arr[p] <= arr[p+1...r)
template<typename T>
int __partition(T arr[], int l, int r) {
//优化二：防止arr为近顺序序列，快速排序将退化为O(n^2)
swap(arr[l], arr[rand() % (r - l) + l]);
T v = arr[l];
//arr[l+1...p] < v <= arr(p....r)
int p = l;
for (int i = l + 1; i < r; i++) {
if (arr[i] < v) {
swap(arr[++p], arr[i]);
}
}
swap(arr[l], arr[p]);
return p;
}
//对arr[l....r)部分进行排序
template<typename T>
void __quickSort(T arr[], int l, int r) {
//if(r - l <= 1) //只有一个元素时，无需排序
// return;
//优化一：当元素较少时，采用插入排序
if (r - l < 16) {
insertionSort1(&arr[l], r - l);
return;
}
int p = __partition(arr, l, r);
__quickSort(arr, l, p);
__quickSort(arr, p + 1, r);
}
template<typename T>
void quickSort(T arr[], int n) {
srand(time(NULL));
__quickSort(arr, 0, n);
}
7.1、两路快速排序
主要改进partition算法，解决在大量重复元素情况下，一边数组远大于另一数组的情况
c++ 代码解读复制代码template<typename T>
int __partition2Ways(T arr[], int l, int r) {
swap(arr[l], arr[rand() % (r - l) + l]);
T v = arr[l];
//arr[l+1...i) <= v; arr(j...r) >= v
int i = l + 1, j = r - 1;
while (true) {
//首先从左到右找到大于等于v的元素
while (i < r && arr[i] < v) i++; //这里不能换成arr[i] <= v，如果arr[l+1...r)=v，则左边的数组会远大于右边
//然后从右到左找到小于等于v的元素
while (j > l && arr[j] > v) j--; //这里不能换成arr[j] >= v，如果arr[l+1]>v，aar[l+2...r)=v，则左边的数组会远小于右边
if (i >= j) break;
swap(arr[i], arr[j]);
i++;
j--;
}
swap(arr[l], arr[j]);
return j;
}
7.2、三路快速排序
c++ 代码解读复制代码//对arr[l....r)部分进行排序
template<typename T>
void __quickSort3Ways(T arr[], int l, int r) {
//if(r - l <= 1) //只有一个元素时，无需排序
// return;
//优化一：当元素较少时，采用插入排序
if (r - l < 16) {
insertionSort1(&arr[l], r - l);
return;
}
//partition
swap(arr[l], arr[rand() % (r - l) + l]);
T v = arr[l];
int lt = l; //arr[l+1...lt] < v
int gt = r; //arr[gt...r) > v
int i = l + 1; //arr[lt+1...i] == v
while (i < gt) {
if (arr[i] < v) {
swap(arr[i], arr[++lt]);
i++;
}
else if (arr[i] > v) {
swap(arr[i], arr[--gt]);
//由于交换到位置i的值并不能保证其大小，故i不能自增，需要重新判定
//i++;
}
else { //arr[i] == v
i++;
}
}
swap(arr[l], arr[lt]);
__quickSort3Ways(arr, l, lt);
__quickSort3Ways(arr, gt, r);
}
//三路快速排序
template<typename T>
void quickSort3Ways(T arr[], int n) {
srand(time(NULL));
__quickSort3Ways(arr, 0, n);
}
评论记录：
回复评论：