2

基本的に、順序が乱れている配列内のペアの数を決定するアルゴリズムを Java で記述しようとしています。したがって、i と j を取り、j が配列内で i よりも高い位置にあるが、A[i] > A[j] の場合、これら 2 つの数値は反転としてカウントされます。現在、これは私が持っているものです：

for(int i = 0; i<n-1; i++){
    if (A[i] > A[i+1]){
        k++;

これが行うことは、互いに隣り合っているペアのみを比較するため、これを変更して、配列内で下の位置が上の数値よりも高い値である 2 つの数値を見つけようとしています。私はそのようなことをする方法を知っていますが、実行時間を (n+k) にしたいです。ここで、n は配列の長さ、k は配列内の反転の数です。

編集:挿入ソートを実装する私の試みは次のとおりです。

int k = 0;
int [] A = {5, 4, 3, 2, 1};
int n = A.length;
for(int i = 1; i < n; i++){
    int temp = A[i];
    int j;
    for (j = i - 1; j >=0 && temp < A[j]; j--){
        A[j + 1] = A[j];
    A[j + 1] = A[j];
        k++;

k は、反転の数を追跡することになっています。配列 5、4、3、2、1 の場合、返される数値は 6 です。そうですか?

4

2 に答える 2

0

配列の反転カウントは、配列がソートされていない (または近い) ことを示します。配列が既にソートされている場合、反転カウントは 0 です。配列が逆の順序でソートされている場合、その反転カウントは最大です。正式には、2 つの要素 a[i] と a[j] は、a[i] > a[j] かつ i < j の場合に反転を形成します。例: シーケンス 2、4、1、3、5 には 3 つの反転があります (2、 1)、(4、1)、(4、3)。

各要素について、その右側にあり、それよりも小さい要素の数を数えます。

int getInvCount(int arr[], int n)
{
  int inv_count = 0;
  int i, j;

  for(i = 0; i < n - 1; i++)
    for(j = i+1; j < n; j++)
      if(arr[i] > arr[j])
        inv_count++;

  return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
  int arr[] = {1, 20, 6, 4, 5};
  printf(" Number of inversions are %d \n", getInvCount(arr, 5));
  getchar();
  return 0;
}
于 2015-10-14T04:31:45.193 に答える