减治法插入排序c++

下面是使用减治法实现的插入排序的 C++ 代码：

#include <iostream>
using namespace std;

void insertSort(int arr[], int n) {
    // i 表示待排序元素的下标，j 表示已排序元素的下标
    for (int i = 1; i < n; i++) {
        int temp = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > temp) {  // 需要移动元素
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;  // 将待排序元素插入到正确的位置
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    insertSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

其中，insertSort 函数使用了减治法的思想，将待排序的序列分为已排序和未排序两部分，每次从未排序中取出一个元素，与已排序中的元素比较，找到其正确的位置插入，直到所有元素都被插入到已排序序列中。

相关问题

用python编写程序产生30000个随机整数，用蛮力法进行选择排序和冒泡排序，用归治法进行归并排序和快速排序，用减治法进行插入排序和堆排序；输出递增结果；统计每一种排序运行所花费的时间。

好的，我理解了你的要求。以下是 Python 代码实现：

import random
import time

# 产生30000个随机整数
nums = [random.randint(1, 100000) for _ in range(30000)]

# 蛮力法 - 选择排序
def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

# 蛮力法 - 冒泡排序
def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(n-i-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

# 归治法 - 归并排序
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res += left[i:]
    res += right[j:]
    return res

# 归治法 - 快速排序
def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[0]
    left = [x for x in nums[1:] if x < pivot]
    right = [x for x in nums[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

# 减治法 - 插入排序
def insertion_sort(nums):
    n = len(nums)
    for i in range(1, n):
        j = i
        while j > 0 and nums[j] < nums[j-1]:
            nums[j], nums[j-1] = nums[j-1], nums[j]
            j -= 1

# 减治法 - 堆排序
def heap_sort(nums):
    def heapify(nums, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and nums[l] > nums[largest]:
            largest = l
        if r < n and nums[r] > nums[largest]:
            largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            heapify(nums, n, largest)

    n = len(nums)
    for i in range(n//2-1, -1, -1):
        heapify(nums, n, i)
    for i in range(n-1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, i, 0)

# 统计每种排序运行所花费的时间
start = time.time()
selection_sort(nums)
end = time.time()
print("选择排序所花费的时间：", end-start, "秒")

start = time.time()
bubble_sort(nums)
end = time.time()
print("冒泡排序所花费的时间：", end-start, "秒")

start = time.time()
merge_sort(nums)
end = time.time()
print("归并排序所花费的时间：", end-start, "秒")

start = time.time()
quick_sort(nums)
end = time.time()
print("快速排序所花费的时间：", end-start, "秒")

start = time.time()
insertion_sort(nums)
end = time.time()
print("插入排序所花费的时间：", end-start, "秒")

start = time.time()
heap_sort(nums)
end = time.time()
print("堆排序所花费的时间：", end-start, "秒")

# 输出递增结果
print(nums)

希望能够帮到你！

C++中排序问题中的减治法-二叉排序树算法的实现实验分析

二叉排序树，也称为二叉搜索树，是一种数据结构，它是一棵二叉树，其中每个节点都包含一个键值，且左子树中的所有键值都小于该节点的键值，右子树中的所有键值都大于该节点的键值。通过这种方式，我们可以快速地对数据进行查找、插入和删除操作。

在排序问题中，我们可以使用减治法来实现二叉排序树算法。具体来说，我们可以将排序问题分解为两个子问题：首先，将前半部分数据排序；然后，将后半部分数据排序。在排序过程中，我们可以利用二叉排序树的特性来建立一棵树，并将数据按照顺序插入到树中。当所有数据插入完毕后，我们可以通过遍历树来将数据按照升序输出。

下面是使用C++实现二叉排序树算法的示例代码：

#include <iostream>
using namespace std;

// 二叉排序树结构体
struct BSTNode {
    int data;           // 数据
    BSTNode* left;      // 左子树指针
    BSTNode* right;     // 右子树指针
};

// 创建新节点
BSTNode* createNode(int data) {
    BSTNode* newNode = new BSTNode;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点
BSTNode* insertNode(BSTNode* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    }
    else {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// 中序遍历输出
void inorderTraversal(BSTNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

// 测试函数
int main() {
    int arr[] = { 6, 3, 8, 2, 5, 7, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);

    BSTNode* root = NULL;
    for (int i = 0; i < n; i++) {
        root = insertNode(root, arr[i]);
    }

    inorderTraversal(root);

    return 0;
}

在上述代码中，我们首先定义了一个二叉排序树结构体，并实现了创建节点、插入节点、中序遍历输出等函数。接着，我们定义了一个测试函数，用于测试二叉排序树算法的正确性。在测试函数中，我们首先定义了一个数据数组，并计算出数据个数。然后，我们通过循环将每个数据插入到二叉排序树中。最后，我们调用中序遍历函数来输出排序后的数据。

通过实验对比分析，我们可以发现，使用减治法实现二叉排序树算法的时间复杂度为O(nlogn)，空间复杂度为O(n)，与其他排序算法相比，效率较高。但是，在某些情况下，由于二叉排序树的不平衡性，可能会导致算法效率下降，因此我们需要采取一些措施来保证二叉排序树的平衡性，例如AVL树、红黑树等。