超快速排序:Ultra-Quick Sort

超级快排:Ultra-QuickSort

总时间限制:

7000ms

内存限制:

65536kB

描述

在这个问题中，你需要分析一种特殊的排序算法。该算法通过操作一个包含n个元素的东西来实现排序。它不断地交换相邻两两比较的对象直至整个序列有序。对于输入序列9,1,0,5,4 Ultra-QuickSort最终生成的结果是0,1,4,5,9。你的目标是计算实现Ultra-QuickSort所需的最少交换次数以达到对任意给定输入排序的目的。

输入

测试数据包含多个组别。每个测试用例以一行给出整数n（小于50万）表示该用例的数据长度）。每个测试用例后面的n个数字依次为a[1], a[2], ..., a[n]）。当遇到输入中的一行数字为零时处理结束

输出

对于每组测试数据而言，请确保你的程序能够逐行读取输入，并计算该序列排序所需的最小交换次数。

样例输入

样例输出

思路：

最开始：

一开始看到这个问题的时候

中间：

因为冒泡排序已经严重超时无法继续使用

 #include<bits/stdc++.h>

    
 using namespace std;
    
 int n,a[20005],tmp[20005];