資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中找到導致歸併排序最壞情況的排列
假設我們有一組元素；我們必須找到這些元素的哪種排列會導致歸併排序的最壞情況？眾所周知，歸併排序在漸近意義上始終消耗 O(n log n) 時間，但某些情況需要更多比較並消耗更多時間。在這裡，我們必須找到輸入元素的排列，當使用典型的歸併排序演算法進行排序時，該排列將需要更多的比較次數。
因此，如果輸入類似於 [11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]，則輸出將為 [11,19,15,23,13,21,17,25,12,20,16,24,14,22,18,26]。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 merge()，它將接收陣列 arr、陣列 left、陣列 right、l_index、m_index、r_index 作為引數。
- 對於初始化 i := 0，當 i <= m_index - l_index 時，更新（i 增加 1），執行：
- arr[i] := left[i]
- 對於初始化 j := 0，當 j < r_index - m_index 時，更新（j 增加 1），執行：
- arr[i + j] = right[j]
- 定義一個函式 divide()，它將接收陣列 arr、陣列 left、陣列 right、l_index、m_index、r_index 作為引數。
- 對於初始化 i := 0，當 i <= m_index - l_index 時，更新（i 增加 1），執行：
- left[i] := arr[i * 2]
- 對於初始化 i := 0，當 i < r_index - m_index 時，更新（i 增加 1），執行：
- right[i] := arr[i * 2 + 1]
- 定義一個函式 gen_worst_seq()，它將接收陣列 arr[]、l_index、r_index 作為引數。
- 如果 l_index < r_index，則：
- m_index := l_index + (r_index - l_index) / 2
- 定義一個大小為 m_index-l_index+1 的陣列 left。
- 定義一個大小為 r_index-m_index 的陣列 right。
- divide(arr, left, right, l_index, m_index, r_index)
- gen_worst_seq(left, l_index, m_index)
- gen_worst_seq(right, m_index + 1, r_index)
- merge(arr, left, right, l_index, m_index, r_index)
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
for (int i = 0; i < size; i++)
cout << A[i] << " ";
cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
int i;
for (i = 0; i <= m_index - l_index; i++)
arr[i] = left[i];
for (int j = 0; j < r_index - m_index; j++)
arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
for (int i = 0; i <= m_index - l_index; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r_index - m_index; i++)
right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
if (l_index < r_index) {
int m_index = l_index + (r_index - l_index) / 2;
int left[m_index - l_index + 1];
int right[r_index - m_index];
divide(arr, left, right, l_index, m_index, r_index);
gen_worst_seq(left, l_index, m_index);
gen_worst_seq(right, m_index + 1, r_index);
merge(arr, left, right, l_index, m_index, r_index);
}
}
int main() {
int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
int n = sizeof(arr) / sizeof(arr[0]);
gen_worst_seq(arr, 0, n - 1);
display(arr, n);
}輸入
11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26
輸出
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
更新於：2020年8月28日
97 次檢視
廣告