使用 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)。在許多情況下，這些型別的演算法有助於降低時間複雜度並執行有效的解決方案。