Ideas

冒泡排序在最壞情況下（完全逆序）的交換次數(shù)為$cnt=\frac{n(n?1)}{2}$，當n=14時，cnt=91，當n=15時，cnt=105。

要求字典序最小，cnt=105代表：由前15個字母組成的逆序排列進行冒泡排序需要交換105次。

15個字母組成的逆序排列：onmlkjihgfedcba，這種情況需要105此交換，所以我們要給它減少5次交換，即將某一位置的字母向前移動5位，為了保證字典序最小，我們把第6位的字母j移動到第1位：jonmlkihgfedcba，也就是說，前5次比較過程不進行位置交換。

然后我們可以寫一個冒泡排序驗證一下。

Code

C++

#include <iostream> using namespace std;int bubble_sort_cnt(char arr[], int n) {int cnt = 0;for(int i = n - 1; i > -1; i--) {for(int j = 0; j < i; j++) {if(arr[j] > arr[j + 1]) {cnt++;swap(arr[j], arr[j + 1]);}}}return cnt; }int main() {int n = 15;char a[n] = {'j', 'o', 'n', 'm', 'l', 'k', 'i', 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'};cout << bubble_sort_cnt(a, n); }

Python

def bubbleSortCnt(arr: list) -> int:cnt = 0for i in range(len(arr) - 1, -1, -1):for j in range(i):if arr[j] > arr[j + 1]:cnt += 1arr[j], arr[j + 1] = arr[j + 1], arr[j]return cntif __name__ == '__main__':print(bubbleSortCnt(list("onmlkjihgfedcba")))print(bubbleSortCnt(list("jonmlkihgfedcba")))

Answer：jonmlkihgfedcba

總結(jié)

以上是生活随笔為你收集整理的2020年第十一届蓝桥杯 - 省赛 - Java研究生组+Java大学B组+Python大学组 - E.排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。