C++ 排序算法实现 - 冒泡排序、快速排序、归并排序

#include #include #include <stdlib.h> #include #include #include

using namespace std;

int size = 10000; // 随机数大小范围 bool a; // 冒泡中判断值 int arr_zx[100000]; // 归并中临时数组 double arr_fd[100000]; char arr_zf[100000];

// 冒泡排序(整型) void function_mp_zx(int dp_zx[], int num) { if (num <= 1) { return; } int sl_zx = num - 2; int itmp_zx = 0; // 中间量 while (sl_zx >= 0) { a = false; for (int i = 0; i <= sl_zx; i++) { if (dp_zx[i] > dp_zx[i + 1]) { itmp_zx = dp_zx[i]; dp_zx[i] = dp_zx[i + 1]; dp_zx[i + 1] = itmp_zx; a = true; } } if (a == false) { break; } sl_zx--; } }

// 冒泡排序(浮点型) void function_mp_fd(double dp_fd[], int num) { if (num <= 1) { return; } int sl_fd = num - 2; double itmp_fd = 0; // 中间量 while (sl_fd >= 0) { a = false; for (int i = 0; i <= sl_fd; i++) { if (dp_fd[i] > dp_fd[i + 1]) { itmp_fd = dp_fd[i]; dp_fd[i] = dp_fd[i + 1]; dp_fd[i + 1] = itmp_fd; a = true; } } if (a == false) { break; } sl_fd--; } }

// 冒泡排序（字符型） void function_mp_zf(char dp_zf[], int num) { if (num <= 1) { return; } int l_zf = strlen(dp_zf) - 2; char itmp_zf; bool a; while (l_zf >= 0) { a = false; for (int i = 0; i <= l_zf; i++) { if (dp_zf[i] > dp_zf[i + 1]) { itmp_zf = dp_zf[i]; dp_zf[i] = dp_zf[i + 1]; dp_zf[i + 1] = itmp_zf; a = true; } } if (a == false) { break; } l_zf--; }

}

// 快速排序（整型） void function_ks_zx(int dp_zx[], int low, int high) { if (low < high) { // 待排序区间至少有两个元素 int pivot = dp_zx[low]; // 选取最左侧元素作为基准元素 int i = low + 1; // i 指向待排序区间的第二个元素 int j = high; // j 指向待排序区间的最后一个元素

    while (i <= j) {
        while (i <= j && dp_zx[i] < pivot) {
            i++;  // 在左侧寻找第一个大于或等于 pivot 的元素
        }
        while (i <= j && dp_zx[j] > pivot) {
            j--;  // 在右侧寻找第一个小于或等于 pivot 的元素
        }
        if (i <= j) {  // 如果 i 和 j 尚未交错，则交换 arr[i] 和 arr[j]
            swap(dp_zx[i], dp_zx[j]);
            i++;
            j--;
        }
    }

    swap(dp_zx[low], dp_zx[j]);  // 将基准元素交换到正确的位置
    int mid = j;

    // 对左侧子区间递归排序
    function_ks_zx(dp_zx, low, mid - 1);
    // 对右侧子区间递归排序
    function_ks_zx(dp_zx, mid + 1, high);
}

}

// 快速排序（浮点型） void function_ks_fd(double dp_fd[], int low, int high) { if (low < high) { // 待排序区间至少有两个元素 double pivot = dp_fd[low]; // 选取最左侧元素作为基准元素 int i = low + 1; // i 指向待排序区间的第二个元素 int j = high; // j 指向待排序区间的最后一个元素

    while (i <= j) {
        while (i <= j && dp_fd[i] < pivot) {
            i++;  // 在左侧寻找第一个大于或等于 pivot 的元素
        }
        while (i <= j && dp_fd[j] > pivot) {
            j--;  // 在右侧寻找第一个小于或等于 pivot 的元素
        }
        if (i <= j) {  // 如果 i 和 j 尚未交错，则交换 arr[i] 和 arr[j]
            swap(dp_fd[i], dp_fd[j]);
            i++;
            j--;
        }
    }

    swap(dp_fd[low], dp_fd[j]);  // 将基准元素交换到正确的位置
    int mid = j;

    // 对左侧子区间递归排序
    function_ks_fd(dp_fd, low, mid - 1);
    // 对右侧子区间递归排序
    function_ks_fd(dp_fd, mid + 1, high);
}

}

// 快速排序（字符型） void function_ks_zf(char dp_zf[], int low, int high) { if (low < high) { // 待排序区间至少有两个元素 char pivot = dp_zf[low]; // 选取最左侧元素作为基准元素 int i = low + 1; // i 指向待排序区间的第二个元素 int j = high; // j 指向待排序区间的最后一个元素

    while (i <= j) {
        while (i <= j && dp_zf[i] < pivot) {
            i++;  // 在左侧寻找第一个大于或等于 pivot 的元素
        }
        while (i <= j && dp_zf[j] > pivot) {
            j--;  // 在右侧寻找第一个小于或等于 pivot 的元素
        }
        if (i <= j) {  // 如果 i 和 j 尚未交错，则交换 arr[i] 和 arr[j]
            swap(dp_zf[i], dp_zf[j]);
            i++;
            j--;
        }
    }

    swap(dp_zf[low], dp_zf[j]);  // 将基准元素交换到正确的位置
    int mid = j;

    // 对左侧子区间递归排序
    function_ks_zf(dp_zf, low, mid - 1);
    // 对右侧子区间递归排序
    function_ks_zf(dp_zf, mid + 1, high);
}

}

// 归并排序（整型） void function_gb_zx(int dp_zx[], int l, int r) { if (l >= r) { return;} int mid = (l + r) / 2; function_gb_zx(dp_zx, l, mid); function_gb_zx(dp_zx, mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (dp_zx[i] <= dp_zx[j]) { arr_zx[k++] = dp_zx[i++];} else { arr_zx[k++] = dp_zx[j++];} } while (i <= mid) { arr_zx[k++] = dp_zx[i++];} while (j <= r) { arr_zx[k++] = dp_zx[j++];} for (int i = l; i <= r; i++) { dp_zx[i] = arr_zx[i];} }

// 归并排序（浮点型） void function_gb_fd(double dp_fd[], int l, int r) { if (l >= r) { return;} int mid = (l + r) / 2; function_gb_fd(dp_fd, l, mid); function_gb_fd(dp_fd, mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (dp_fd[i] <= dp_fd[j]) { arr_fd[k++] = dp_fd[i++];} else { arr_fd[k++] = dp_fd[j++];} } while (i <= mid) { arr_fd[k++] = dp_fd[i++];} while (j <= r) { arr_fd[k++] = dp_fd[j++];} for (int i = l; i <= r; i++) { dp_fd[i] = arr_fd[i];} }

// 归并排序（字符型） void function_gb_zf(char dp_zf[], int l, int r) { if (l >= r) { return;} int mid = (l + r) / 2; function_gb_zf(dp_zf, l, mid); function_gb_zf(dp_zf, mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (dp_zf[i] <= dp_zf[j]) { arr_zf[k++] = dp_zf[i++];} else { arr_zf[k++] = dp_zf[j++];} } while (i <= mid) { arr_zf[k++] = dp_zf[i++];} while (j <= r) { arr_zf[k++] = dp_zf[j++];} for (int i = l; i <= r; i++) { dp_zf[i] = arr_zf[i];} }

// ... (主函数和其他代码)