C语言——冒泡排序法与简单选择排序法及其区别
冒泡排序（Bubble Sort）
是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素，这表示该数列已经排序完成。
冒泡排序的名字由来是因为越小（或越大）的元素会经过交换慢慢“浮”到数列的顶端（或底部），就如同水中的气泡一样上浮到水面。
下面是使用C语言实现的冒泡排序算法的一个基本示例：
#include<stdio.h>
int main()
{
int i;
int j;
int array[]={99,77,55,88,66,44,11,33,22};
int arraySize;
int temp;
arraySize = sizeof(array)/sizeof(array[0]);
for(i=0;i<arraySize-1;i++){ //外层循环次数为数组长度减一是指排序的总轮数
for(j=0;j<arraySize-i-1;j++){ //内层循环负责在每轮中进行实际的元素比较和交换，
//由于外层循环每完成i次，代表i个数已经排好了位置，
//所以其循环次数要再减去i
if(array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
puts("经过冒泡排序后，从小到大依次为：");
for(i=0;i<arraySize;i++){
printf("%d ",array[i]);
}
return 0;
}输出将是：
经过冒泡排序后，从小到大依次为：
11 22 33 44 55 66 77 88 99它通过两层嵌套的循环来实现：外层循环控制排序的总轮数，内层循环负责在每轮中进行实际的元素比较和交换。每完成一轮内层循环，数组中的最大元素就会“冒泡”到它应该在的位置上，因此外层循环每次迭代时，内层循环的迭代次数可以相应减少。
注意，冒泡排序虽然实现简单，但其平均和最坏情况下的时间复杂度都是O(n^2)，因此对于大数据集来说效率较低。在实际应用中，通常会选择更高效的排序算法，如快速排序、归并排序等。
简单选择排序（Simple Selection Sort）
是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
以下是使用C语言实现简单选择排序的一个例子，这个例子将对一个整数数组进行升序排序：
#include<stdio.h>
int main()
{
int i;
int j;
int array[]={99,77,55,88,66,44,11,33,22};
int arraySize;
int temp;
arraySize = sizeof(array)/sizeof(array[0]);
for(i=0;i<arraySize-1;i++){ //外层循环次数
for(j=i+1;j<arraySize;j++){ //内层循环
if(array[i] < array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
puts("经过冒泡排序后，从小到大依次为：");
for(i=0;i<arraySize;i++){
printf("%d ",array[i]);
}
return 0;
}它首先使用外层循环遍历数组的每个元素（除了最后一个），因为最后一个元素在遍历完所有元素后将自然处于正确的位置。对于每个元素，内层循环遍历其后面的所有元素以找到最小元素的索引。一旦找到最小元素的索引，就将它与当前外层循环的元素进行交换。这个过程重复进行，直到数组完全排序。
主要区别：
简单选择排序和冒泡排序作为两种基础的排序算法，它们在实现方式、效率、稳定性等方面存在一些显著的区别。以下是它们之间的主要区别：
1. 工作原理
- 简单选择排序：它的基本思想是在未排序的序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 冒泡排序：它的基本思想是通过相邻元素之间的比较和交换，将序列中最大的元素交换到最后的位置，然后在剩余的序列中继续进行类似的操作。具体来说，就是重复地遍历要排序的数列，每次比较相邻两个元素，如果它们的顺序错误就交换位置，直到没有相邻元素需要交换，排序完成。
2. 交换次数
- 简单选择排序：在每一轮选择中，只需要进行一次交换（即将找到的最小或最大元素与当前轮次的起始位置的元素交换）。
- 冒泡排序：在每一轮比较中，如果相邻元素顺序错误，则进行交换。因此，冒泡排序的交换次数通常比选择排序多，尤其是在数组已经部分排序的情况下。
3. 效率
- 时间复杂度：两者在最坏情况下的时间复杂度都是O(n^2)，其中n是数组的长度。然而，在实际应用中，冒泡排序可能会因为频繁的元素交换而稍慢于简单选择排序，尤其是在数据规模较大时。
- 空间复杂度：两者都是原地排序算法，即不需要额外的存储空间，空间复杂度均为O(1)。
4. 稳定性
- 简单选择排序：是不稳定的排序算法。因为在选择最小（或最大）元素的过程中，可能会改变相同关键字之间的相对位置。
- 冒泡排序：是稳定的排序算法。在排序过程中，相等元素的相对位置不会发生改变。
5. 实际应用
- 由于简单选择排序和冒泡排序的时间复杂度都较高，它们在实际应用中通常不是首选的排序算法。在数据规模较大时，更高效的排序算法（如快速排序、归并排序、堆排序等）是更好的选择。
- 然而，在数据规模较小或对数据稳定性有要求的情况下，冒泡排序可能因其实现简单和稳定性而受到青睐。而简单选择排序则可能在某些特定场景下（如内存限制严格的环境）因其空间复杂度低而得到应用。
综上所述，简单选择排序和冒泡排序在工作原理、交换次数、效率、稳定性和实际应用等方面都存在明显的区别。在选择使用哪种排序算法时，需要根据具体的应用场景和数据特点进行综合考虑。
原文地址：https://blog.csdn.net/weixin_45720999/article/details/140397303
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！