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

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

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

使用的方法

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

• 使用内置的 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）.

在这里，给定的数组是使用排序函数排序的，该函数通常具有 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）。

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

结论

在本文中，我们学习了如何使用两种不同的方法对给定的波形阵列进行排序。与第一种方法相比，O（log N）时间复杂度降低的新逻辑是我们用来降低时间复杂度的逻辑。在许多情况下，这些算法有助于降低时间复杂性并执行有效的解决方案。