使用 Python 对数组进行波浪形排序

---

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

假设我们已经获取了一个未排序的输入数组。我们现在将对输入数组进行波浪形排序。如果数组 'arr[0..n-1]' 满足 arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..，则称该数组已排序成波浪形。

使用的方法

以下是完成此任务所使用的各种方法：

• 使用内置的 sort() 函数

• 不使用内置函数

方法 1：使用内置的 sort() 函数

算法（步骤）

以下是执行所需任务的算法/步骤：

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

• 使用 **sort()** 函数（按升序/降序对列表进行排序）按升序对输入数组进行排序。

• 使用 **for 循环** 交替遍历数组长度（步长=2）

• 使用“,”运算符交换相邻元素，即当前元素及其下一个元素。

• 创建一个变量来存储输入数组。

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

• 通过传递输入数组和数组长度作为参数来调用上面定义的 **sortingInWaveform()** 函数。

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

• 打印数组的当前元素。

示例

以下程序使用 Python 内置的 sort() 函数对输入数组进行波浪形排序：

# 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=" ")

输出

执行上述程序将生成以下输出：

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 

**时间复杂度** - O(nLogn)。

在这里，给定的数组使用 sort 函数进行排序，该函数通常具有 O(NlogN) 的时间复杂度。

如果应用了 O(nLogn) 的排序算法，例如 **归并排序、堆排序** 等，则上述方法具有 O(nLogn) 的时间复杂度。

方法 2：仅使用一个循环

算法（步骤）

以下是执行所需任务的算法/步骤：

• 使用 **for 循环** 通过传递 0、数组长度和步长值作为参数来遍历所有偶数索引元素。

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

• 如果条件为 **true**，则交换元素。

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

• 如果条件为 **true**，则交换元素。

• 通过传递输入数组和数组长度作为参数来调用上面定义的 **sortingInWaveform()** 函数。

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

• 打印数组/列表的对应元素。

示例

以下程序仅使用一个 for 循环且不使用内置函数对输入数组进行波浪形排序：

# 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=" ")

输出

执行上述程序将生成以下输出：

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)。

在这里，我们没有使用 sort 函数；相反，我们只是使用 for 循环迭代给定数组的元素，该循环平均具有 O(N) 的时间复杂度。

结论

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