資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
