對陣列進行排列,以便在執行給定操作後獲得遞增順序


您必須使用合適的排序演算法,才能使用指定的操作將陣列按遞增順序排列。首先根據陣列大小和資料屬性確定最有效的方法。氣泡排序、合併排序和快速排序是一些常用的排序演算法。重複應用所選演算法,根據元素之間的比較來移動元素的位置,直到陣列按升序排列。演算法的效率取決於其耗時,最好的演算法會產生更快的結果。透過仔細使用所選的排序方法,可以有效地將陣列按遞增順序排列,從而更容易操作和分析資料。

使用的方法

  • 氣泡排序

  • 合併排序

  • 快速排序

氣泡排序

氣泡排序是一種簡單的排序技術,可用於將陣列按升序排列。它的工作原理是重複比較相鄰的陣列元素,檢視它們是否按正確的順序排列,如果不是,則交換它們。重複此過程,直到整個陣列排序完畢。您可以使用此排序方法快速將陣列按升序排列。但是,與合併排序或快速排序等其他排序演算法相比,氣泡排序對於較大的陣列效率較低,因為它的最壞情況時間複雜度為 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) 的平均時間複雜度。要使用的排序演算法取決於要排序資料的具體需求和屬性。

更新於:2023年8月2日

瀏覽量:102

啟動你的職業生涯

完成課程獲得認證

開始
廣告