對陣列進行排列,以便在執行給定操作後獲得遞增順序
您必須使用合適的排序演算法,才能使用指定的操作將陣列按遞增順序排列。首先根據陣列大小和資料屬性確定最有效的方法。氣泡排序、合併排序和快速排序是一些常用的排序演算法。重複應用所選演算法,根據元素之間的比較來移動元素的位置,直到陣列按升序排列。演算法的效率取決於其耗時,最好的演算法會產生更快的結果。透過仔細使用所選的排序方法,可以有效地將陣列按遞增順序排列,從而更容易操作和分析資料。
使用的方法
氣泡排序
合併排序
快速排序
氣泡排序
氣泡排序是一種簡單的排序技術,可用於將陣列按升序排列。它的工作原理是重複比較相鄰的陣列元素,檢視它們是否按正確的順序排列,如果不是,則交換它們。重複此過程,直到整個陣列排序完畢。您可以使用此排序方法快速將陣列按升序排列。但是,與合併排序或快速排序等其他排序演算法相比,氣泡排序對於較大的陣列效率較低,因為它的最壞情況時間複雜度為 O(n2),而其他演算法對於更大的資料集具有更好的時間複雜度。
演算法
從一個未排序的元素陣列開始。
比較第一個和第二個元素。如果第一個元素大於第二個元素,則交換這兩個元素。
如有必要,對後續一對相鄰元素重複比較和交換過程。
對每一對相鄰元素重複此過程,直到陣列的末尾。
遍歷一次後,陣列中最大的元素最終將“冒泡”到最後一個位置。
對其餘的陣列元素(除了已排序的最後一個元素)重複步驟 2 到 5,直到整個陣列按升序排列。
陣列現在按遞增順序排列,表示排序操作結束。
示例
#include <iostream> template <typename T, size_t N> void bubbleSort(T (&arr)[N]) { for (size_t i = 0; i < N - 1; ++i) { for (size_t j = 0; j < N - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); for (int num : arr) { std::cout << num << " "; } return 0; }
輸出
11 12 22 25 34 64 90
合併排序
合併排序使用分治策略將陣列按遞增順序排列。它將陣列分成兩半,然後遞迴地分別對每個子陣列進行排序。然後將排序後的子數組合並回一起,確保元素按升序排列。完成此操作後,陣列將完全排序。合併排序是實現陣列遞增順序的有效方法,因為它確保所有情況下的時間複雜度為 O(n log n),從而簡化資料管理和分析。
演算法
如果陣列只包含一個元素或為空,則陣列已排序。按原樣返回陣列。
將陣列分成兩個相等的部分。
迭代地對每一半應用合併排序,以獨立地對它們進行排序。
重新構造兩個已排序的半部分,確保元素按升序排列。
比較兩個半部分中的元素,較小的元素將新增到一個臨時組合陣列中。
繼續處理選擇較小元素的子陣列中的下一個元素。
直到兩個部分合並,再次比較和合並。
用組合陣列替換原始陣列。
排序整個陣列後繼續遞迴。
合併排序方法已成功地按升序對陣列進行排序。
示例
#include <iostream> #include <ctime> #include <cstdlib> using namespace std; void mergeSort(int arr[], int left, int right); void merge(int arr[], int left, int mid, int right); int main() { const int size = 10; int arr[size]; srand(time(0)); cout << "Original Array: "; for (int i = 0; i < size; i++) { arr[i] = rand() % 100; cout << arr[i] << " "; } mergeSort(arr, 0, size - 1); cout << "\nSorted Array: "; for (int i = 0; i < size; i++) { cout << arr[i] << " "; } return 0; } void mergeSort(int arr[], int left, int right) { } void merge(int arr[], int left, int mid, int right) { }
輸出
Original Array: 64 10 16 73 95 69 25 68 11 45 Sorted Array: 64 10 16 73 95 69 25 68 11 45
快速排序
根據常用的排序技術快速排序,透過從陣列中選擇一個“樞軸”元素將陣列分成較小和較大的子陣列。然後該方法迭代地對這些子陣列進行排序。完成此操作後,陣列將完全排序。快速排序由於其平均時間複雜度為 O(n log n),因此對於大型陣列非常有效。透過仔細使用快速排序,可以將陣列按升序重新排列,從而簡化資料處理和分析。
演算法
從列表中選擇一個樞軸元素;這個元素可以是任何一個,但通常是第一個、最後一個或中間的元素。
重新排列陣列的元素以建立一個分割槽,將較小的元素放在左邊,較大的元素放在右邊。
遞迴地對左分割槽和右分割槽(分別小於和大於樞軸的元素)應用快速排序。
對每個分割槽重複此過程,直到子陣列為空或只包含一個元素。
當遞迴展開時,子陣列連線起來以產生最終的排序陣列。
示例
#include <iostream> #include <vector> int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } int main() { std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; int n = arr.size(); quickSort(arr, 0, n - 1); std::cout << "Sorted array: "; for (int num : arr) { std::cout << num << " "; } return 0; }
輸出
Sorted array: 3 9 10 27 38 43 82
結論
總之,在考慮了三種排序演算法(氣泡排序、合併排序和快速排序)來將陣列按遞增順序排列之後,很明顯每種方法都有其優點和缺點。儘管氣泡排序易於實現,但由於其最壞情況時間複雜度為 O(n2),因此對於大型陣列效率較低。合併排序對於大型資料集適用,並且由於其 O(n log n) 的時間複雜度,因此在所有情況下都能提供一致的效能。快速排序以其效率而聞名,並且在大多數情況下表現良好。它也具有 O(n log n) 的平均時間複雜度。要使用的排序演算法取決於要排序資料的具體需求和屬性。