比并排序算法实现详解比并排序|数据结构

本文概述

双音排序
复杂

【比并排序算法实现详解】Bitonic排序是一种并行排序算法, 它执行O（n2 log n）比较。尽管比较的数量比任何其他流行的排序算法都多, 但是它对并行实现的效果更好, 因为元素是按预定义的顺序进行比较的, 而该序列不必依赖于要排序的数据。预定义的序列称为Bitonic序列。
什么是双音序列？
为了了解Bitonic排序, 我们必须了解Bitonic序列。重音序列是这样一种序列, 其中元素首先按升序排列, 然后在某个特定索引后开始递减。如果存在索引i, 则数组A [0 … i … n-1]被称为Bitonic,

A[0] < A[1] < A[2] .... A[i-1] < A[i] > A[i+1] > A[i+2] > A[i+3] > ... > A[n-1]

其中0 < = i < = n-1。 Bitonic排序的旋转也是Bitonic。
如何转换随机序列为双音序列？
考虑n个元素的序列A [0 … n-1]。首先通过使用序列的4个元素来构建Bitonic序列。将前2个元素按升序排序, 将后2个元素按降序排序, 将这对连接在一起, 形成4个元素的双音序列。对其余的元素对重复此过程, 直到找到双音序列。

文章图片
完成此步骤后, 我们得到给定序列的Bitonic序列为2、10、20、30、5、5、4、3。
双音排序双音分类主要包括以下基本步骤。

根据在上述步骤中形成的给定随机序列, 形成一个Bitonic序列。我们可以将其视为程序中的第一步。完成此步骤后, 我们得到一个序列, 其前半部分按升序排序, 而第二步按降序排序。
比较上半部分的第一个元素和下半部分的第一个元素, 然后比较上半部分的第二个元素和下半部分的第二个元素, 依此类推。如果发现下半部分的任何元素较小, 请交换这些元素。
完成上述步骤后, 我们使上半部分的所有元素小于后半部分的所有元素。比较和交换结果分别为两个长度为n / 2的序列。对每个序列递归地重复第二步中执行的过程, 直到获得长度为n的单个排序序列。

下图描述了Bitonic排序所涉及的整个过程。

文章图片
复杂

复杂	最好的情况	平均情况	最差的情况
时间复杂度	O（log 2 n）	O（log 2 n）	O（log 2 n）
Space Complexity			O（n log 2 n）

C程序

//this program works when size of input is power of 2. #include< stdio.h> void exchange(int arr[], int i, int j, int d){int temp; if (d==(arr[i]> arr[j])){temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}void merge(int arr[], int l, int c, int d){int k, i; if (c> 1){k = c/2; for (i=l; i< l+k; i++)exchange(arr, i, i+k, d); merge(arr, l, k, d); merge(arr, l+k, k, d); }}void bitonicSort(int arr[], int l, int c, int d){int k; if (c> 1){k = c/2; bitonicSort(arr, l, k, 1); bitonicSort(arr, l+k, k, 0); merge(arr, l, c, d); }} void sort(int arr[], int n, int order){bitonicSort(arr, 0, n, order); }int main(){int arr[]= {1, 10, 2, 3, 1, 23, 45, 21}; int n = sizeof(arr)/sizeof(arr[0]); int i; int order = 1; sort(arr, n, order); printf("Sorted array: \n"); for (i=0; i< n; i++)printf("%d ", arr[i]); }

输出：

Sorted array: 1 1 2 3 10 21 23 45

爪哇

//this program works when size of input is power of 2. public class BitonicSort{static void exchange(int arr[], int i, int j, boolean d){int temp; if (d==(arr[i]> arr[j])){temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}static void merge(int arr[], int l, int c, boolean d){int k, i; if (c> 1){k = c/2; for (i=l; i< l+k; i++)exchange(arr, i, i+k, d); merge(arr, l, k, d); merge(arr, l+k, k, d); }}static void bitonicSort(int arr[], int l, int c, boolean d){int k; if (c> 1){k = c/2; bitonicSort(arr, l, k, true); bitonicSort(arr, l+k, k, false); merge(arr, l, c, d); }} static void sort(int arr[], int n, boolean order){bitonicSort(arr, 0, n, order); }public static void main(String[] args){int arr[]= {1, 10, 2, 3, 1, 23, 45, 21}; int n = arr.length; int i; boolean order = true; sort(arr, n, order); System.out.println("Sorted array: \n"); for (i=0; i< n; i++)System.out.println(arr[i]); }}

输出：

Sorted array: 1 1 2 3 10 21 23 45

C＃

//this program works when size of input is power of 2. using System; public class BitonicSort{static void exchange(int[] arr, int i, int j, bool d){int temp; if (d==(arr[i]> arr[j])){temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}static void merge(int[] arr, int l, int c, bool d){int k, i; if (c> 1){k = c/2; for (i=l; i< l+k; i++)exchange(arr, i, i+k, d); merge(arr, l, k, d); merge(arr, l+k, k, d); }}static void bitonicSort(int[] arr, int l, int c, bool d){int k; if (c> 1){k = c/2; bitonicSort(arr, l, k, true); bitonicSort(arr, l+k, k, false); merge(arr, l, c, d); }} static void sort(int[] arr, int n, bool order){bitonicSort(arr, 0, n, order); }public void Main(){int[] arr= {1, 10, 2, 3, 1, 23, 45, 21}; int n = arr.Length; int i; bool order = true; sort(arr, n, order); Console.WriteLine("Sorted array: \n"); for (i=0; i< n; i++)Console.WriteLine(arr[i]+" "); }}