数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的位排序
位排序是一种并行排序算法，它被创建用于最佳实现，并且与硬件和并行处理器阵列一起使用时具有最佳用途。
虽然与归并排序相比，它并不是最有效的排序算法。但它非常适合并行实现。这是由于预定义的比较顺序使得比较独立于要排序的数据。
为了使位排序有效地工作，元素的数量应为特定类型的数量，即 2^n 阶。
位排序的一个主要部分是位排序序列，它是一个元素值先增加然后减少的序列。
位排序序列是一个数组 arr[0 … (n-1)]，如果在 0 到 n-1 的范围内存在一个索引值 i。对于该索引值，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)}
// creating bitonic sequence pairs…
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
现在，既然我们已经了解了位排序序列。我们将了解位排序。
位排序
使用以下步骤使用位排序对位排序序列进行排序 -
步骤 1 - 创建一个位排序序列。
步骤 2 - 现在，我们有一个位排序序列，其中一部分按升序排列，另一部分按降序排列。
步骤 3 - 我们将比较并交换两半的第一个元素。然后是第二个、第三个、第四个元素。
步骤 4 - 我们将比较并交换序列的每个第二个元素。
步骤 5 - 最后，我们将比较并交换序列的相邻元素。
步骤 6 - 在所有交换之后，我们将得到排序后的数组。
示例
显示位排序实现的程序 -
#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
877 次查看
