Kuasai algoritma pengisihan biasa dalam C++

C++ ialah bahasa pengaturcaraan yang digunakan secara meluas dalam pengaturcaraan komputer, dan algoritma pengisihan ialah salah satu algoritma yang biasa digunakan dalam pengaturcaraan. Menguasai algoritma pengisihan boleh meningkatkan keupayaan anda untuk menulis program yang cekap dan meningkatkan kemahiran pengaturcaraan anda. Artikel ini akan memperkenalkan algoritma pengisihan yang biasa digunakan dalam C++.

1. Isih buih

Isih buih ialah algoritma pengisihan asas yang mencapai pengisihan dengan membandingkan unsur bersebelahan dalam turutan dan menukar unsur yang lebih besar ke penghujung jujukan. Khususnya, isihan gelembung membandingkan saiz elemen bersebelahan dalam setiap pusingan dan menukar elemen yang lebih besar ke belakang sehingga elemen terakhir diisih.

Kod C++ adalah seperti berikut:

void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2. Isih pilihan

Isihan pilihan ialah algoritma pengisihan mudah Ia memilih elemen terkecil dalam bahagian yang tidak diisih setiap kali dan meletakkannya di hujung bahagian yang diisih, dengan itu Laksanakan. menyusun. Khususnya, isihan pemilihan memilih elemen terkecil dalam setiap pusingan dan menukarnya dengan elemen pada kedudukan semasa.

Kod C++ adalah seperti berikut:

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. Isihan sisipan

Isihan sisipan ialah algoritma pengisihan yang mudah dan intuitif yang memasukkan elemen ke dalam urutan yang telah diisih untuk mendapatkan urutan yang lebih panjang. Khususnya, setiap pusingan isihan sisipan memasukkan elemen ke dalam subarray yang diisih dan menggerakkan elemen yang tinggal ke belakang.

Kod C++ adalah seperti berikut:

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

4. Isih cepat

Isih cepat ialah algoritma pengisihan yang cekap Ia membahagikan urutan kepada dua bahagian dengan memilih elemen pangsi, satu bahagian lebih kecil daripada elemen pangsi. bahagian lain lebih besar daripada elemen pangsi , dan susun dua urutan secara rekursif. Khususnya, isihan pantas memilih elemen pangsi dalam setiap pusingan, dan meletakkan elemen yang lebih kecil daripada elemen pangsi di sebelah kiri elemen pangsi dan elemen yang lebih besar daripada elemen pangsi di sebelah kanan. Kemudian urutan kiri dan kanan diisih secara rekursif dengan cara yang sama.

Kod C++ adalah seperti berikut:

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

5. Merge sort

Merge sort ialah algoritma pengisihan bahagi-dan-takluk klasik Ia membahagikan jujukan kepada dua jujukan, mengisih setiap jujukan secara berasingan, dan akhirnya menyusun dua jujukan. . Khususnya, isihan gabungan mula-mula membahagikan urutan kepada dua urutan, mengisih dua urutan secara rekursif, dan kemudian menggabungkan dua urutan tertib menjadi satu urutan tertib.

Kod C++ adalah seperti berikut:

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; // 左侧子数组的索引
    j = 0; // 右侧子数组的索引
    k = left; // 合并后的数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 将左侧子数组的剩余元素拷贝到合并后的数组中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 将右侧子数组的剩余元素拷贝到合并后的数组中
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左侧和右侧的子序列
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

Di atas ialah lima algoritma pengisihan yang biasa digunakan dalam C++. Walaupun algoritma mungkin kelihatan membosankan, ia adalah bahagian penting dalam pengaturcaraan Dengan mempelajari algoritma pengisihan, kami boleh meningkatkan kecekapan dan kualiti pengaturcaraan.

Atas ialah kandungan terperinci Kuasai algoritma pengisihan biasa dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!