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

输出

执行后，上述程序将生成以下输出 &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

时间复杂度 − O(nLogn)。

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

如果使用O(nLogn)的排序算法，如 合并排序，堆排序， 等等，上述方法的时间复杂度为O(nLogn)。

方法2：只使用一个循环

步骤

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

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

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

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

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

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

• 通过将输入数组和数组长度作为参数调用上述定义的 sortingInWaveform() 函数

• 使用 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)。

在这里，我们没有使用排序函数；相反，我们只是使用for循环来遍历给定数组的元素，这在平均情况下具有O(N)的时间复杂度。

结论

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