数据结构——冒泡、选择、插入和希尔排序

引言

冒泡排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

选择排序

1.算法思想

2.算法步骤

3.代码实现

(1)优化前

(2)优化后

4.复杂度分析

插入排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

希尔排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

结束语

引言

在数据处理、算法优化等领域中，排序是基础且关键的一环。本文将要探讨的四种排序算法：冒泡排序、选择排序、插入排序和希尔排序。

求点赞收藏关注！！！

冒泡排序

1.算法思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这意味着数列已经排序完成。

这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端（或底部）。

2.算法步骤

1.比较相邻的元素。如果第一个比第二个大（或小，根据排序顺序要求），就交换它们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（或最小的数）。

3.针对所有的元素重复以上的步骤，除了已完成排序元素。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

注意：如果一轮之后，元素并没有发生任何交换，此时说明此时排序已经完成，那么我们可以提前结束循环。

我们来看个动图就能很直观的理解什么是冒泡排序：

3.代码实现

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void bubble_sort(int arr[], int sz)
{// 外层循环，控制排序的轮数for (int i = 0; i < sz - 1; i++){// 定义一个标志位，用于判断是否在这一轮中有元素交换int flag = 0;// 内层循环，进行实际的元素比较和交换for (int j = 0; j < sz - i - 1; j++){// 如果当前元素大于后一个元素，则交换它们if (arr[j] > arr[j + 1]){// 设置标志位为1，表示发生了交换flag = 1;Swap(&arr[j], &arr[j + 1]);}}// 如果这一轮没有发生任何交换// 说明数组已经有序，可以提前结束排序if (flag == 0){break;}}
}

4.复杂度分析

时间复杂度：最坏情况是数组完全逆序，此时每一轮都需要进行 n - 1 次比较，并且每一轮都会进行至少一次交换.因此，总的比较次数和交换次数都接近 n (n - 1) / 2，其中 n 是数组的长度。所以，最坏情况下的时间复杂度是 O(n ^ 2) 。

空间复杂度：由于没有开辟额外的空间大小，因此空间复杂度为O(1)。

选择排序

1.算法思想

选择排序（Selection Sort）是一种简单直观的排序算法。通过不断选择剩余元素之中的最小（或最大）元素，然后与起始位置的元素交换（起始位置在每一次选择后都向后移动一位），直到整个序列排序完成。

2.算法步骤

1.在未排序序列中找到最小（大）元素。遍历未排序的数组，找到最小（或最大）的元素。

2.存放到排序序列的起始位置。将找到的最小（或最大）元素与未排序序列的第一个元素交换位置（如果第一个元素就是最小（大）元素，则它自己和自己交换）。

3.从剩余未排序元素中继续寻找：在剩下的未排序元素中继续执行步骤1和步骤2，直到所有元素都被排序。

看动图直观的感受一下：

3.代码实现

(1)优化前

void SelectSort(int* arr, int len)
{for (int i = 0; i < len - 1; i++){// 假设当前位置i的元素是最小的，记录其索引为miniint mini = i;for (int j = i + 1; j < len; j++){// 如果发现更小的元素，则更新mini为当前更小元素的索引if (arr[j] < arr[mini]){mini = j;}}swap(&arr[mini], &arr[i]);}
}

(2)优化后

我们可以对上面的代码进行点优化，我们可以同时选择最大与最小的元素，同时往起始与结尾位置交换。

注意：同时交换可能会改变原先最大或者最小元素的位置。因此我们需要进行判断。

代码如下：

//交换两个数据
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void SelectSort(int* arr, int n)
{int begin = 0;		// 未排序部分的起始索引int end = n - 1;	// 未排序部分的结束索引while (begin < end){int maxi = begin;int mini = begin;// 遍历未排序部分，找到最小值和最大值for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;	// 更新最小值的位置}if (arr[i] > arr[maxi]){maxi = i;	// 更新最大值的位置}}// 将当前范围的最小值交换到未排序部分的开始位置Swap(&arr[begin], &arr[mini]);// 如果begin与maxi重合，则更新maxiif (maxi == begin){maxi = mini;}// 将当前范围的最大值交换到未排序部分的结束位置Swap(&arr[end], &arr[maxi]);// 缩小未排序部分的范围++begin;--end;}
}

4.复杂度分析

时间复杂度：由于每次外层循环中的内层循环需要遍历几乎所有未排序的元素，因此时间复杂度为O(n^2)。

空间复杂度：由于没有开辟额外的空间大小，因此空间复杂度为O(1)。

插入排序

1.算法思想

插入排序（Insertion Sort）是一种简单直观的排序算法。它模拟了我们日常生活中整理扑克牌或排序书籍的过程。其基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、元素个数加一的有序数据，直到全部待排序的数据元素插完，排序完成。

2.算法步骤

1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2.遍历未排序部分，将扫描到的每个元素插入有序序列的适当位置。

3.依次重复1,2步骤，直至插入完成。

动图演示如下：

3.代码实现

void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;// tmp 存储当前需要插入的元素的值int tmp = arr[end + 1];// 内层循环，将比 tmp 大的元素向后移动一位// 为 tmp 找到正确的插入位置while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}// 将 tmp 插入到找到的正确位置arr[end + 1] = tmp;}
}

4.复杂度分析

时间复杂度：当处于最坏情况时，由于每次插入都会移动数据，因此时间复杂度为O(n^2)。

空间复杂度：由于没有开辟额外的空间大小，因此空间复杂度为O(1)。

希尔排序

1.算法思想

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，也称为缩小增量排序。基本思想是将待排序的数组元素按照某种增量（gap）进行分组，对每组使用插入排序算法进行排序。随着增量的逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组被视为一组进行最后的插入排序，从而完成排序过程。

2.算法步骤

1.选择一个增量 gap ，对数据进行分组，每间隔gap个元素分为一组，一共gap组。

2.以gap为基准单位，对其进行插入排序。

3.逐渐缩小gap的范围，直至gap为1，相当于进行一次正常的插入排序。

动图演示所下所示：

3.代码实现

void ShellSort(int* arr, int n)
{// 初始化增量gap为数组长度n，用于分组int gap = n;while (gap > 1){// 逐渐减少增量gap = gap / 3 + 1;// 对每个分组进行插入排序for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){// 如果当前位置的元素大于tmp// 则将当前位置的元素向后移动gap位if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}// 将tmp插入到找到的正确位置arr[end + gap] = tmp;}}
}