C2.06 数组排序

选择排序与冒泡排序

• 选择排序_基本原理

选择排序首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

• 选择排序_参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	// 定义数组a，用于存储待排序的元素；n为数组元素的个数；t为临时变量，用于记录最小元素的位置
    int a[105], n, t;   
  
    cin >> n; // 输入待排元素的个数  

	// 循环输入 n 个元素，存入数组a 
    for(int i = 0; i <= n - 1; i++) cin >> a[i]; 

	// 外层循环，从数组的第一个元素开始，直到倒数第二个元素
    for(int i = 0; i <= n - 2; i++)   
    {
    	// 假设当前元素是最小的，记录其位置
        t = i;
        
        // 内层循环，从当前元素的下一个元素开始，遍历剩余未排序的元素
        for(int j = i + 1; j <= n - 1; j++)  
        {  
            if(a[j] < a[t]) t = j; // 如果发现更小的元素，更新最小元素的位置  
        }  
  
        swap(a[i], a[t]); // 将找到的最小元素与当前位置 i 的元素交换  
    }  
  
    for(int i = 0; i <= n - 1; i++) cout << a[i] << " "; // 输出排序后的数组  
  
    return 0;
}

• 选择排序_代码解析

• 首先输入元素的个数 n，然后通过循环输入 n 个元素到数组 a 中。
• 外层循环遍历数组的每个元素，从第一个元素开始到倒数第二个元素。
• 假设当前遍历的元素a[i]是最小的，将其位置记录在t中。
• 内层循环从a[i]的下一个元素开始，遍历剩余未排序的元素，如果发现比a[t]更小的元素，就更新t为那个更小的元素的位置。
• 内层循环结束后，t中存储的就是从a[i]到数组末尾中的最小元素的位置，使用swap函数将这个最小元素与a[i]交换位置。

• 冒泡排序_基本原理

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

• 冒泡排序_参考代码

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    // 定义一个大小为 105 的整数数组a 和一个整数 n  
    int a[105],n;  
  
    // 输入一个整数 n  
    cin>>n;  
  
    // 循环读取 n 个整数，并存储到数组a 中  
    for(int i=0;i<=n-1;i++) cin>>a[i];
  
    // 冒泡排序算法   
    for(int i=1;i<=n-1;i++)// 外层循环控制排序的轮数  
    {  
        // 内层循环控制每一轮的比较和交换  
        for(int j=0;j<=n-2;j++)  
        {  
            // 如果当前元素a[j]大于下一个元素a[j+1]，则交换它们的位置  
            if(a[j] > a[j+1])  
            {  
                swap(a[j],a[j+1]);  
            }  
        }  
    }  
  
    // 输出排序后的数组  
    for(int i=0;i<=n-1;i++) cout<<a[i]<<" ";  

    return 0;  
}

• 冒泡排序_代码解析

• 从数列的第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大（如果是降序排序，则是前一个元素比后一个元素小），则交换它们的位置。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（如果是降序排序，则是最小的数）。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较