使用 Python 对波形中的数组进行排序
在本文中，我们将学习一个 Python 程序来对波形中的数组进行排序。
假设我们获取了一个未排序的输入数组。现在我们将对波形中的输入数组进行排序。如果 arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..，则数组"arr[0..n-1]"按波形排序。
使用的方法
以下是完成此任务所使用的各种方法 &miinus;
使用内置 sort() 函数
不使用内置函数
方法 1:使用内置 sort() 函数
算法(步骤)
以下是执行所需任务所要遵循的算法/步骤。 −
创建一个函数，通过接受输入数组和数组长度作为参数对波形中的数组进行排序。
使用 sort() 函数(按升序/降序对列表进行排序)按升序对输入数组进行排序。
使用 for 循环 交替遍历直到数组长度(step=2)
使用','运算符交换相邻元素，即当前元素和下一个元素。
创建一个变量来存储输入数组。
使用 len() 函数(返回对象中的项目数)获取输入数组的长度。
调用上面定义的sortingInWaveform() 函数，通过传递输入数组和数组长度作为参数
使用 for 循环 遍历数组的所有元素
打印数组的当前元素。
示例
以下程序使用 python 内置 sort() 函数对波形中的输入数组进行排序 −
# 创建一个函数，通过接受
# 输入数组、数组长度作为参数对波形中的数组进行排序
def sortingInWaveform(inputArray, arrayLength):
# 使用 sort() 函数按升序对输入数组进行排序
inputArray.sort()
# 交替遍历直到数组长度(step=2)
for k in range(0, arrayLength-1, 2):
# 交换相邻元素，即当前元素和下一个元素
inputArray[k], inputArray[k+1] = inputArray[k+1], inputArray[k]
# 输入数组
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# 获取输入数组的长度
arrayLength = len(inputArray)
# 打印给定的数组/列表
print("给定的列表是:", inputArray)
# 调用上面定义的 sortingInWaveform() 函数
# 传递输入数组、数组长度作为参数
sortingInWaveform(inputArray, arrayLength)
print("波形排序后的结果数组是:")
# 遍历数组的所有元素
for k in range(0, arrayLength):
# 打印数组/列表的当前元素
print(inputArray[k], end=" ")
输出
执行时，上述程序将生成以下输出 &miinus;
给定列表为:[12, 45, 15, 4, 6, 70, 68, 3, 25] 波形排序后的结果数组为: 4 3 12 6 25 15 68 45 70
时间复杂度 − O(nLogn)。
此处，给定的数组使用 sort 函数进行排序，该函数通常具有 O(NlogN) 时间复杂度。
如果应用 O(nLogn) 排序算法(如合并排序、堆排序等)，则上述方法具有 O(nLogn) 时间复杂度。
方法 2:仅使用一个循环
算法(步骤)
以下是执行所需任务需要遵循的算法/步骤。 −
使用 for 循环 遍历所有偶数索引元素，传递 0、数组长度和步长值作为参数
使用 if 条件 语句检查当前偶数索引元素是否小于前一个元素。
如果条件为 真，则交换元素。
使用 if 条件 语句检查当前偶数索引元素是否小于下一个元素。
如果条件为 真
，则交换元素。
通过传递输入数组和数组长度作为参数来调用上面定义的 sortingInWaveform() 函数
使用 for 循环，遍历数组的元素。
打印数组/列表的相应元素。
示例
以下程序仅使用一个 for 循环对波形中的输入数组进行排序，无需内置函数 -
# 创建一个函数，通过接受
# 输入数组、数组长度作为参数对波形中的数组进行排序
def sortingInWaveform(inputArray, arrayLength):
# 遍历所有偶数索引元素
for p in range(0, arrayLength, 2):
# 检查当前偶数索引元素
# 是否小于前一个
if (p > 0 and inputArray[p] < inputArray[p-1]):
# 如果条件为真，则交换元素
inputArray[p], inputArray[p-1] = inputArray[p-1], inputArray[p]
# 检查当前偶数索引元素
# 是否小于下一个元素
if (p < arrayLength-1 and inputArray[p] < inputArray[p+1]):
# 如果条件为真，则交换元素
inputArray[p], inputArray[p+1] = inputArray[p+1], inputArray[p]
# 输入数组
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# 获取输入数组的长度
arrayLength = len(inputArray)
print("给定的列表是:", inputArray)
# 调用上面定义的 sortingInWaveform() 函数
# 传递输入数组、数组长度作为参数
sortingInWaveform(inputArray, arrayLength)
print("按波形排序后的结果数组是:")
# 遍历数组的所有元素
for k in range(0, arrayLength):
# 打印当前元素
print(inputArray[k], end=" ")
输出
执行时，上述程序将生成以下输出 -
给定的列表是:[12, 45, 15, 4, 6, 70, 68, 3, 25] 波形排序后的结果数组为: 45 12 15 4 70 6 68 3 25
时间复杂度 − O(n)。
这里我们没有使用sort函数，而是用for循环遍历给定数组的元素，平均时间复杂度为O(N)。
结论
在本文中，我们学习了如何使用两种不同的方法对给定的波形数组进行排序。我们使用了一种比第一种方法时间复杂度降低为O(log N)的新逻辑来降低时间复杂度。在许多情况下，这类算法有助于降低时间复杂度并执行有效的解决方案。
