升序排列偶数元素，降序排列奇数元素 _数据结构

本文概述

C ++
Java
Python3
C#
C ++
Java
Python3
C#

我们给了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, 1Input: 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# 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 - 2arr_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

//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

输出如下：