Python 对波形图中的数组进行排序

在这篇文章中，我们将学习一个Python程序来对波形中的数组进行排序。

假设我们已经采取了一个未经排序的输入数组。现在我们将在波形中对输入数组进行排序。一个数组’arr[0…n-1]’在波形中被排序，如果arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

使用的方法

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

• 使用内置sort()函数

• 不使用内建函数

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

算法（步骤）

以下是执行所需任务时需要遵循的算法/步骤。-

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

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

• 使用 for循环 遍历到数组的长度（step=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)。

这里，给定的数组是用排序函数进行排序的，其时间复杂度通常为O(NlogN)。

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

方法2：只使用一个循环

算法（步骤）

以下是执行所需任务时需要遵循的算法/步骤。-

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

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

• 如果条件为 真 ，则交换这些元素。

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

• 如果条件为 真 ，则交换这些元素。

• 通过传递输入数组和数组的长度作为参数，调用上述定义的 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)。

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

总结

在这篇文章中，我们学习了如何使用两种不同的方法对给定的波形阵列进行排序。一个新的逻辑，比第一种方式的时间复杂度降低了O(log N)，这就是我们用来降低时间复杂度的方法。在许多情况下，这类算法有助于降低时间复杂度并进行有效的解决。