本文概述
我们给了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 KumarC#
//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 DHUAJava
//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 29AjayKumarPython3
# 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 KunduC#
//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)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
