时间戳

首页 > 解决方案 > 如何使用插入排序正确排序数组？

c - 如何使用插入排序正确排序数组？

问题描述

我有整个程序，它可以工作，但不能正常工作。printArray 函数仅打印 Array 的第一个元素，并且似乎不对元素进行排序。我不知道如何处理它。

int main(){
    int number;
    printf( "Give a number of elements:" );
    scanf("%d",&number);
    printf("Array to sort:");
    int* Array = createArray(number);
    int sizeArr = sizeof(Array)/sizeof(Array[0]);
    int *sortedArr = insertionSort(Array,sizeArr);
    puts("");
    printf("Sorted array by Insertion Sort:");
    printArr(sortedArr,sizeArr);
    getch();
    return 0;
}
int* createArray(int number){
    int *arr =(int*) malloc(sizeof(int*)*number);
    srand((unsigned)time(NULL));
    for(int i=0;i<number;i++){
        arr[i] = 1 + rand()%10;
        printf("%d",arr[i]);
    }
    return arr;
}
int *insertionSort(int *arr,int sizeArr){
    int i, j,repArr;
    for(i=1;i<sizeArr;i++){
            repArr = arr[i];
            j=i-1;
    while(j>=0 && arr[j]>repArr){
        arr[j+1] = arr[j];
        j = j - 1;
    }
        arr[j+1] = repArr;
    }
return arr;
}

void printArr(int*arr,int sizeArr){
    for(int i=0;i<sizeArr;i++){
        printf("%d",arr[i]);
        }
       puts("");
}

标签： c

解决方案

tl; dr：您有责任了解分配中有多少元素。您分配了1 个 number元素，因此大小为number.

这条线没有做你认为它做的事情。它将比较 和 的int大小int *。在您的平台上，它们的大小相同。

int sizeArr = sizeof(Array)/sizeof(int);

您正在告诉所有函数您有一个包含 1 个元素的数组，因此您对该 1 个元素进行排序，并打印该 1 个元素。

你已经知道有多少ints （你在假装）存在，它是number。

与其将结果解释malloc为一堆ints （那里没有ints，所以你的程序是未定义的），你可以使用std::vector<int>，它有一个size成员。

这是一个更多的 C++ 方法

#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

std::random_device rd;  //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()

std::vector<int> createNumbers(int number){
    std::vector<int> arr(number);
    std::uniform_int_distribution<> d10(1, 10);
    std::generate_n(begin(arr), number, [&](){ return d10(gen); });
    return arr;
}

template<class FwdIt, class Compare = std::less<>>
void insertionSort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
    }
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    for (auto& el : vec)
    {
        os << el << ' ';
    }
    return os;
}

int main(){
    int number;
    std::cout << "Give a number of elements:";
    std::cin >> number;
    auto Numbers = createNumbers(number);
    std::cout << "Array to sort:" << Numbers;
    insertionSort(begin(Numbers), end(Numbers));
    std::cout << "Sorted array by Insertion Sort:" << Numbers;
    return 0;
}

现场观看

1：忽略 和 的混淆int，int *它们在您的平台上大小相同。在其他平台上，您有多个number元素。

推荐阅读