在本文中，我们将学习一个Python程序，用于对数组进行波形排序。

假设我们有一个未排序的输入数组。我们现在将以波形的方式对输入数组进行排序。如果数组 'arr [0..n-1]' 满足 arr [0] >= arr [1] <= arr [2] >= arr [3] <= arr [4] >= .....，则该数组被排序为波形。

Methods Used

以下是用于完成此任务的各种方法 &miinus;

• 使用内置的sort()函数

• Without Using Built-in functions

Method 1: Using the Built-in sort() function

算法（步骤）

Following are the Algorithms/steps to be followed to perform the desired task. −

• 创建一个函数来按照波形对输入数组进行排序，接受输入数组和数组长度作为参数。

• Use the sort() function(sorts the list in ascending/descending order ) to sort the input array in ascending order.

• Use the for loop to traverse till the array length alternatively(step=2)

• Swap the adjacent elements i.e, current and its next using the ‘,’ operator.

• Create a variable to store the input array.

• 使用 len() 函数（返回对象中的项目数）来获取输入数组的长度。

• Call the above-defined sortingInWaveform() function by passing the input array, and length of the array as arguments

• 使用for循环遍历数组的所有元素

• Print the current element of an array.

Example

The following program sorts the input array in waveform using the python Built-in sort() function −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # sorting the input array in ascending order using the sort() function
   inputArray.sort()
   # travsersing till the array length alternatively(step=2)
   for k in range(0, arrayLength-1, 2):
         # swapping the adjacent elements i.e, current and it's next
         inputArray[k], inputArray[k+1] = inputArray[k+1], inputArray[k]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
# printing the given array/list
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element of the array/list
      print(inputArray[k], end=" ")

Output

On execution, the above program will generate the following output &miinus;

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
4 3 12 6 25 15 68 45 70 

Time complexity − O(nLogn).

Here, the array that was given was sorted using the sort function, which typically has an O(NlogN) time complexity.

如果应用O(nLogn)的排序算法，如Merge Sort，Heap Sort等，上述给出的方法的时间复杂度为O(nLogn)。

方法2：只使用一个循环

算法（步骤）

Following are the Algorithms/steps to be followed to perform the desired task. −

• Use the for loop to traverse through all the even index elements by passing 0, array length, and step value as arguments

• 使用if条件语句来检查当前偶数索引元素是否小于前一个元素。

• Swap the elements if the condition is true.

• 使用 if 条件语句 来检查当前偶数索引元素是否小于下一个元素。

• Swap the elements if the condition is true.

• Call the above-defined sortingInWaveform() function by passing the input array, and length of the array as arguments

• 使用for循环遍历数组的元素。

• Print the corresponding element of the array/list.

Example

The following program sorts the input array in wave form using only one for loop and without Built-in functions −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # traversing through all the even index elements
   for p in range(0, arrayLength, 2):
      # checking whether the current even index element
      # is smaller than the previous
      if (p > 0 and inputArray[p] < inputArray[p-1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p-1] = inputArray[p-1], inputArray[p]
            # checking whether the current even index element
            # is smaller than the next element
      if (p < arrayLength-1 and inputArray[p] < inputArray[p+1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p+1] = inputArray[p+1], inputArray[p]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element
   print(inputArray[k], end=" ")

Output

执行上述程序后，将生成以下输出 -

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
45 12 15 4 70 6 68 3 25

时间复杂度 - O(n)。

Here, we didn't use the sort function; instead, we just used the for loop to iterate through the elements of the given array, which, on average, has O(N) time complexity.

结论

在本文中，我们学习了如何使用两种不同的方法对给定的波形数组进行排序。我们使用了一种新的逻辑，它的时间复杂度比第一种方法降低了O(log N)。在许多情况下，这些类型的算法有助于减少时间复杂度并实施有效的解决方案。