升序排列偶数元素，降序排列奇数元素

2021年4月23日17:03:07 发表评论 1,265 次浏览

本文概述

我们给了n个不同数字的数组。任务是按升序对所有偶数和奇数进行排序。修改后的数组应包含所有排序的偶数编号, 后跟反向排序的奇数编号。

请注意, 第一个元素因其索引为0而被认为是偶数放置。

例子：

Input:  arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
Output: arr[] = {0, 2, 4, 6, 7, 5, 3, 1}
Even-place elements : 0, 2, 4, 6
Odd-place elements : 1, 3, 5, 7
Even-place elements in increasing order : 
0, 2, 4, 6
Odd-Place elements in decreasing order : 
7, 5, 3, 1

Input: arr[] = {3, 1, 2, 4, 5, 9, 13, 14, 12}
Output: {2, 3, 5, 12, 13, 14, 9, 4, 1}
Even-place elements : 3, 2, 5, 13, 12
Odd-place elements : 1, 4, 9, 14
Even-place elements in increasing order : 
2, 3, 5, 12, 13
Odd-Place elements in decreasing order : 
14, 9, 4, 1

这个想法很简单。我们分别创建两个辅助数组evenArr []和oddArr []。我们遍历输入数组, 并将所有偶数放置的元素放置在evenArr []中, 将奇数放置的元素放置在oddArr []中。然后, 我们按升序对evenArr []和按降序对oddArr []进行排序。最后, 复制evenArr []和oddArr []以获取所需的结果。

C ++

//Program to separately sort even-placed and odd
//placed numbers and place them together in sorted
//array.
#include <bits/stdc++.h>
using namespace std;
  
void bitonicGenerator( int arr[], int n)
{
     //create evenArr[] and oddArr[]
     vector<int> evenArr;
     vector<int> oddArr;
  
     //Put elements in oddArr[] and evenArr[] as
     //per their position
     for ( int i = 0; i <n; i++) {
         if (!(i % 2))
             evenArr.push_back(arr[i]);
         else
             oddArr.push_back(arr[i]);
     }
  
     //sort evenArr[] in ascending order
     //sort oddArr[] in descending order
     sort(evenArr.begin(), evenArr.end());
     sort(oddArr.begin(), oddArr.end(), greater<int>());
  
     int i = 0;
     for ( int j = 0; j <evenArr.size(); j++)
         arr[i++] = evenArr[j];
     for ( int j = 0; j <oddArr.size(); j++)
         arr[i++] = oddArr[j];
}
  
//Driver Program
int main()
{
     int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
     int n = sizeof (arr) /sizeof (arr[0]);
     bitonicGenerator(arr, n);
     for ( int i = 0; i <n; i++)
         cout <<arr[i] <<" " ;
     return 0;
}

Java

//Java Program to separately sort
//even-placed and odd placed numbers
//and place them together in sorted
//array.
import java.util.*;
  
class GFG {
  
     static void bitonicGenerator( int arr[], int n)
     {
         //create evenArr[] and oddArr[]
         Vector<Integer> evenArr = new Vector<Integer>();
         Vector<Integer> oddArr = new Vector<Integer>();
  
         //Put elements in oddArr[] and evenArr[] as
         //per their position
         for ( int i = 0 ; i <n; i++) {
             if (i % 2 != 1 ) {
                 evenArr.add(arr[i]);
             }
             else {
                 oddArr.add(arr[i]);
             }
         }
  
         //sort evenArr[] in ascending order
         //sort oddArr[] in descending order
         Collections.sort(evenArr);
         Collections.sort(oddArr, Collections.reverseOrder());
  
         int i = 0 ;
         for ( int j = 0 ; j <evenArr.size(); j++) {
             arr[i++] = evenArr.get(j);
         }
         for ( int j = 0 ; j <oddArr.size(); j++) {
             arr[i++] = oddArr.get(j);
         }
     }
  
     //Driver code
     public static void main(String[] args)
     {
         int arr[] = { 1 , 5 , 8 , 9 , 6 , 7 , 3 , 4 , 2 , 0 };
         int n = arr.length;
         bitonicGenerator(arr, n);
         for ( int i = 0 ; i <n; i++) {
             System.out.print(arr[i] + " " );
         }
     }
}
  
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to separately sort 
# even-placed and odd placed numbers 
# and place them together in sorted array.
def bitonicGenerator(arr, n):
      
     # create evenArr[] and oddArr[]
     evenArr = []
     oddArr = []
  
     # Put elements in oddArr[] and evenArr[] 
     # as per their position
     for i in range (n):
         if ((i % 2 ) = = 0 ):
             evenArr.append(arr[i])
         else :
             oddArr.append(arr[i])
  
     # sort evenArr[] in ascending order
     # sort oddArr[] in descending order
     evenArr = sorted (evenArr)
     oddArr = sorted (oddArr)
     oddArr = oddArr[:: - 1 ]
  
     i = 0
     for j in range ( len (evenArr)):
         arr[i] = evenArr[j]
         i + = 1
     for j in range ( len (oddArr)):
         arr[i] = oddArr[j]
         i + = 1
  
# Driver Code
arr = [ 1 , 5 , 8 , 9 , 6 , 7 , 3 , 4 , 2 , 0 ]
n = len (arr)
bitonicGenerator(arr, n)
for i in arr:
     print (i, end = " " )
  
# This code is contributed by Mohit Kumar

C#

//C# Program to separately sort
//even-placed and odd placed numbers
//and place them together in sorted
//array.
using System;
using System.Collections.Generic;
  
class GFG 
{
  
     static void bitonicGenerator( int []arr, int n)
     {
         //create evenArr[] and oddArr[]
         List<int> evenArr = new List<int>();
         List<int> oddArr = new List<int>();
         int i = 0;
          
         //Put elements in oddArr[] and evenArr[] as
         //per their position
         for (i = 0; i <n; i++) 
         {
             if (i % 2 != 1) 
             {
                 evenArr.Add(arr[i]);
             }
             else 
             {
                 oddArr.Add(arr[i]);
             }
         }
  
         //sort evenArr[] in ascending order
         //sort oddArr[] in descending order
         evenArr.Sort();
         oddArr.Sort();
         oddArr.Reverse();
  
         i = 0;
         for ( int j = 0; j <evenArr.Count; j++) 
         {
             arr[i++] = evenArr[j];
         }
         for ( int j = 0; j <oddArr.Count; j++)
         {
             arr[i++] = oddArr[j];
         }
     }
  
     //Driver code
     public static void Main(String[] args)
     {
         int []arr = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
         int n = arr.Length;
         bitonicGenerator(arr, n);
         for ( int i = 0; i <n; i++) 
         {
             Console.Write(arr[i] + " " );
         }
     }
}
  
//This code contributed by Rajput-Ji

输出如下：

1 2 3 6 8 9 7 5 4 0

时间复杂度：O(n Log n)

空间复杂度：O(n)

上述问题也可以在不使用辅助空间的情况下解决。想法是将前半奇数索引位置与后半偶数索引位置交换, 然后以升序对前半数组进行排序, 然后以降序对后半数组进行排序。谢谢SWARUPANANDA DHUA建议这个。

C ++

//Program to sort even-placed elements in increasing and
//odd-placed in decreasing order with constant space complexity
  
#include <bits/stdc++.h>
using namespace std;
  
void bitonicGenerator( int arr[], int n)
{
     //first odd index
     int i = 1;
  
     //last index
     int j = n - 1;
  
     //if last index is odd
     if (j % 2 != 0)
         //decrement j to even index
         j--;
  
     //swapping till half of array
     while (i <j) {
         swap(arr[i], arr[j]);
         i += 2;
         j -= 2;
     }
  
     //Sort first half in increasing
     sort(arr, arr + (n + 1) /2);
  
     //Sort second half in decreasing
     sort(arr + (n + 1) /2, arr + n, greater<int>());
}
  
//Driver Program
int main()
{
     int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
     int n = sizeof (arr) /sizeof (arr[0]);
     bitonicGenerator(arr, n);
     for ( int i = 0; i <n; i++)
         cout <<arr[i] <<" " ;
     return 0;
}
//This code is contributed by SWARUPANANDA DHUA

Java

//Program to sort even-placed elements in increasing and
//odd-placed in decreasing order with constant space complexity
import java.util.Arrays;
class GFG {
  
     static void bitonicGenerator( int arr[], int n)
     {
         //first odd index
         int i = 1 ;
  
         //last index
         int j = n - 1 ;
  
         //if last index is odd
         if (j % 2 != 0 )
             //decrement j to even index
             j--;
  
         //swapping till half of array
         while (i <j) {
             arr = swap(arr, i, j);
             i += 2 ;
             j -= 2 ;
         }
  
         //Sort first half in increasing
         Arrays.sort(arr, 0 , (n + 1 ) /2 );
  
         //Sort second half in decreasing
         Arrays.sort(arr, (n + 1 ) /2 , n);
         int low = (n + 1 ) /2 , high = n - 1 ;
         //Reverse the second half
         while (low <high) {
             Integer temp = arr[low];
             arr[low] = arr[high];
             arr[high] = temp;
             low++;
             high--;
         }
     }
     static int [] swap( int [] arr, int i, int j)
     {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         return arr;
     }
     //Driver Program
     public static void main(String[] args)
     {
         int arr[] = { 1 , 5 , 8 , 9 , 6 , 7 , 3 , 4 , 2 , 0 };
         int n = arr.length;
         bitonicGenerator(arr, n);
         for ( int i = 0 ; i <n; i++)
             System.out.print(arr[i] + " " );
     }
}
//This code has been contributed by 29AjayKumar

Python3

# Python3 Program to sort even-placed elements in increasing and
# odd-placed in decreasing order with constant space complexity
def bitonicGenerator(arr, n):
  
     # first odd index
     i = 1
  
     # last index
     j = n - 1
      
     # if last index is odd
     if (j % 2 ! = 0 ):
          
         # decrement j to even index
         j = j - 1
          
     # swapping till half of array
     while (i <j) :
         arr[j], arr[i] = arr[i], arr[j]
         i = i + 2
         j = j - 2
          
     arr_f = []
     arr_s = []
      
     for i in range ( int ((n + 1 ) /2 )) :
         arr_f.append(arr[i])
      
     i = int ((n + 1 ) /2 )
     while ( i <n ) :
         arr_s.append(arr[i])
         i = i + 1
      
     # Sort first half in increasing 
     arr_f.sort()
  
     # Sort second half in decreasing
     arr_s.sort(reverse = True )
      
     for i in arr_s:
         arr_f.append(i)
      
     return arr_f
  
# Driver Program
arr = [ 1 , 5 , 8 , 9 , 6 , 7 , 3 , 4 , 2 , 0 ] 
n = len (arr)
arr = bitonicGenerator(arr, n)
print (arr)
  
# This code is contributed by Arnab Kundu

C#

//Program to sort even-placed elements in 
//increasing and odd-placed in decreasing order
//with constant space complexity
using System;
      
class GFG
{
     static void bitonicGenerator( int []arr, int n)
     {
         //first odd index
         int i = 1;
  
         //last index
         int j = n - 1;
  
         //if last index is odd
         if (j % 2 != 0)
          
             //decrement j to even index
             j--;
  
         //swapping till half of array
         while (i <j) 
         {
             arr = swap(arr, i, j);
             i += 2;
             j -= 2;
         }
  
         //Sort first half in increasing
         Array.Sort(arr, 0, (n + 1) /2);
  
         //Sort second half in decreasing
         Array.Sort(arr, (n + 1) /2, n - ((n + 1) /2));
         int low = (n + 1) /2, high = n - 1;
          
         //Reverse the second half
         while (low <high)
         {
             int temp = arr[low];
             arr[low] = arr[high];
             arr[high] = temp;
             low++;
             high--;
         }
     }
      
     static int [] swap( int [] arr, int i, int j)
     {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         return arr;
     }
      
     //Driver Code
     public static void Main(String[] args)
     {
         int []arr = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
         int n = arr.Length;
         bitonicGenerator(arr, n);
         for ( int i = 0; i <n; i++)
             Console.Write(arr[i] + " " );
     }
}
  
//This code is contributed by PrinciRaj1992

输出如下：

1 2 3 6 8 9 7 5 4 0

时间复杂度：O(n Log n)

空间复杂度：O(1)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: