比并排序算法实现详解

本文概述

• 双音排序
• 复杂

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。

双音排序

双音分类主要包括以下基本步骤。

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

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

复杂

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]+"	");
}
}