1 波形排序

所谓“波形排序”就是一大一小。

将n个身高互不相同的人排成一行 ,对于每个人 ,要求他要么比相邻的人均高 ,要么比相邻的人均矮 ,问共有多少种排法 ,这一问题称为波形排列问题。

2 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// C#实现了对波形中的数组进行排序的朴素方法
    /// </summary>
    public static class Array_Sort_In_Wave_Form
    {
        // A utility method to swap two numbers.
        private static void Swap(int[] arr, int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        public static void Sort_In_Wave(int[] arr)
        {
            Array.Sort(arr);
            int n = arr.Length;
            for (int i = 0; i < n - 1; i += 2)
            {
                Swap(arr, i, i + 1);
            }
        }

        public static void Sort_In_Wave_2th(int[] arr)
        {
            int n = arr.Length;
            for (int i = 0; i < n; i += 2)
            {
                if (i > 0 && arr[i - 1] > arr[i])
                {
                    Swap(arr, i - 1, i);
                }
                if (i < n - 1 && arr[i] < arr[i + 1])
                {
                    Swap(arr, i, i + 1);
                }
            }
        }
    }
}

3 源代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// C#实现了对波形中的数组进行排序的朴素方法
    /// </summary>
    public static class Array_Sort_In_Wave_Form
    {
        // A utility method to swap two numbers.
        private static void Swap(int[] arr, int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        public static void Sort_In_Wave(int[] arr)
        {
            Array.Sort(arr);
            int n = arr.Length;
            for (int i = 0; i < n - 1; i += 2)
            {
                Swap(arr, i, i + 1);
            }
        }

        public static void Sort_In_Wave_2th(int[] arr)
        {
            int n = arr.Length;
            for (int i = 0; i < n; i += 2)
            {
                if (i > 0 && arr[i - 1] > arr[i])
                {
                    Swap(arr, i - 1, i);
                }
                if (i < n - 1 && arr[i] < arr[i + 1])
                {
                    Swap(arr, i, i + 1);
                }
            }
        }
    }
}