bitonic排序是为最佳实现而创建的并行排序算法，并与硬件和并行处理器数组配合使用。
与合并排序相比，它不是最有效的一种。但这对并行实现很有用。这归因于预定义的比较序列，该序列使比较独立于要分类的数据。
为了使双音排序有效地起作用，元素的数量应为特定数量的类型，即2 ^ n阶。
双音序列的一个主要部分是双音序列，该序列的元素值先增大然后减小。
如果索引值i在0到n-1之间，则双音序列为数组arr [0…(n-1)]。为此，arr [i]的值在数组中最大。即
arr[0] <= arr[1] … <= arr[i] and arr[i] >= arr[i+1] … >= aar[n-1]
重音序列可以旋转回到重音序列。
具有递增和递减顺序的元素的序列是双音序列。
为了创建一个双音序列，我们将创建两个子序列，一个具有升序元素，另一个具有降序元素。
例如，让我们看一下序列arr []并将以下序列转换为双音序列。
arr[] = {3, 4, 1, 9, 2, 7, 5, 6}首先，我们将制作成对的元素，然后以如下方式创建这些元素的双音序列：一个元素升序，另一个元素降序，依此类推。
对于我们的数组，让我们按音调序列创建对。
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
//创建双音序列对…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}然后，我们将创建这些对中的对。即4个元素的双音序列和比较元素之间的距离为2 [即i与i + 2]。
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}第一组中的升序双音将被创建为-
(3, 4, 9, 1) : comparing two distant elements. (3, 1, 9, 4) : Now, check adjacent elements. (1, 3, 4, 9) -> ascending bitonic sequence.
第二组降序音将被创建为-
(2, 7, 6, 5) : comparing two distant elements. (6, 7, 2, 5) : Now, check adjacent elements. (7, 6, 5, 2) -> descending bitonic sequence.
最后，我们将获得大小为8的双音序列。
1, 3, 4, 9, 7, 6, 5, 2
现在，由于我们已经了解了双音序列。我们将了解Bitonic Sorting。
使用这些步骤使用音调排序对音调序列进行排序-
步骤1-创建一个双音序列。
步骤2-现在，我们有了一个双音序列，其中一个部分按升序排列，其他部分按降序排列。
步骤3-我们将比较并交换两半的前几个元素。然后是第二，第三，第四要素。
步骤4-我们将比较并交换序列的每个第二个元素。
步骤5-最后，我们将比较并交换序列中的相邻元素。
步骤6-所有交换之后，我们将获得排序后的数组。
该程序显示Bitonic Sort的实现-
#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
for (int i=start; i<start+k; i++)
if (direction==(a[i]>a[i+k]))
swap(a[i],a[i+k]);
bitonicSeqMerge(a, start, k, direction);
bitonicSeqMerge(a, start+k, k, direction);
}
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
bitonicSortrec(a, start, k, 1);
bitonicSortrec(a, start+k, k, 0);
bitonicSeqMerge(a,start, BseqSize, direction);
}
}
void bitonicSort(int a[], int size, int up) {
bitonicSortrec(a, 0, size, up);
}
int main() {
int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
int size = sizeof(a)/sizeof(a[0]);
printf("Original array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
bitonicSort(a, size, 1);
printf("\nSorted array: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
return 0;
}输出结果
Original array: 5 10 51 8 1 9 6 22 Sorted array: 1 5 6 8 9 10 22 51