2021秋季《数据结构》_EOJ 1050.冒泡排序

题目

思路

注意递归终止条件判断

• 不再发生交换
• 最后发生交换的元素为第0，1个元素

代码

#include<bits/stdc++.h>
using namespace std;int aa = 0;  // 比较次数
int bb = 0;  // 交换次数
int cc = 0;  // 冒泡排序的最小次序void bubbleSort_quick(int* a, int left, int right)
{
    int flag = 1;  // 是否需要交换int j = right - 1;for (int i = left; i < right; i++){
    aa++;if (a[i] > a[i + 1])  // 需要交换{
    bb++;int tmp = a[i];a[i] = a[i + 1];a[i + 1] = tmp;j = i;flag = 0;}}for (int i = 0; i < 5; i++)cout << a[i] << ' ';cout << endl;if (!(aa == 0 && bb == 0))cc++;  // 排除只有一个元素不需要比较//if (flag) return;if (flag || j == left) return;// flag：没有发生交换// j==left：此时交换了前两个元素，可以结束，避免下一次进入排序时c++return bubbleSort_quick(a, left, j);
}int main()
{
    int n; cin >> n;int* a = new int[n];for (int i = 0; i < n; i++){
    cin >> a[i];}//bubbleSort(b, 0, n-1);bubbleSort_quick(a, 0, n - 1);cout << aa << ' ' << bb << ' ' << cc << endl;//for (int i = 0; i < n; i++)//{
    // cout << a[i];//}return 0;
}