数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++数组中交叉线的计数
给定一个包含不同元素的未排序数组。目标是在数组排序后找到交叉线。交叉线的计数如下所示：
Arr[]={ 1,2,4,3,5 } 如图所示，共有3条交叉线。
Arr[]= { 1,2,3,4,5 }。因为数组已排序，所以没有交叉线。
我们将使用插入排序来计算交叉线，其中从右边取一个元素添加到其左边的已排序元素中。每次元素添加到已排序部分时，都将计数器递增，因为它移动到其正确的位置。它将通过穿过所有大于它的元素来进行。
让我们通过例子来理解。
输入 − arr[]= {4,3,1,2 }
输出− 数组中交叉线的数量 − 5
解释 − 4-4 和 3-3 交叉 1-1 和 2-2。共有 4 条交叉线。
4-4 和 3-3 互相交叉一次。共有 4+1=5 条交叉线。
输入 − arr[]= { 0,1,5,3 }
输出 − 数组中交叉线的数量 − 1
解释 − 5-5 和 3-3 互相交叉一次。共有 1 条交叉线。
下面程序中使用的算法如下：
我们使用一个用不同数字初始化的整数数组 arr[]。
函数 insertionSort(int arr[], int n) 以数组及其长度作为输入，排序后返回交叉线的数量作为结果。
将交叉线的初始数量设为 0。使用计数变量。
第一个元素已经排序，所以从第二个元素到结尾 (i=1 到 i<n)，取每个元素作为 item。(item=arr[i]) 并令 j=i-1。
如果元素 > item 且 j>0，则将所有元素向右移动。对于每次移动，计数器递增，因为这些元素都被 item 交叉。
在 while 循环结束时，将 item 放置到其正确的位置，即 arr[j+1]。
对所有元素执行此操作，并计算它们交叉的元素数。
将计数器值递增为可能的交叉线数。
示例
#include <bits/stdc++.h>
using namespace std;
int insertionSort(int arr[], int n){
int count=0;
int item;
int j;
for (int i = 1; i < n; i++){
item = arr[i];
j = i - 1;
//insert element at correct position in sorted part, no. of elements it passes
//from right till correct position is count of cross lines.
while (j >= 0 && arr[j] > item){
arr[j + 1] = arr[j];
j = j - 1;
count++;
}
arr[j + 1] = item;
}
return count;
}
int main(){
int arr[] = { 4,5,3,1,2};
int n = 5;
cout<<"Number of cross lines: "<<insertionSort(arr, n);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Number of cross lines: 8
更新于：2020年8月29日
163 次浏览
广告