C中的插入排序算法不起作用

Question

我正在尝试对一个整数数组进行排序，以查找同一数组的中值。我使用的代码只对10元素数组的前两个元素进行排序。我已经交叉检查了循环中变量的交换，但一切似乎都很好。

void sort(int *arr) {
//get the size of this array
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}

应用程序

#include <stdlib.h>
#include <stdio.h>
int main() {
int numbers[10];
numbers[0] = 10;
numbers[1] = 9;
numbers[2] = 8;
numbers[3] = 7;
numbers[4] = 6;
numbers[5] = 5;
numbers[6] = 4;
numbers[7] = 3;
numbers[8] = 2;
numbers[9] = 1;
sort(numbers);
//code sorts the element in the first and second index, the rest are unsorted please help
return 0;
}

我做错了什么？

Answer 1

函数参数具有指针类型

void sort(int* arr){

即使你会像一样重写函数声明

void sort( int arr[10] ){

然而，编译器将调整具有数组类型的函数参数，使其指向原始函数声明中写入的元素类型

void sort(int* arr){

在这个函数的调用中

sort(numbers);

数组指示符被隐式地转换为指向其第一个元素的指针。这就是上面的呼叫事实上与相同

sort( &numbers[0] );

因此，在指针表达式中使用运算符sizeof可以得到指针的大小。这是的这条线

//get the size of this array
int size=sizeof(arr)/sizeof(arr[0]);

相当于

//get the size of this array
int size=sizeof( int * )/sizeof( int );

并且根据所使用的系统产生2或1。

你需要像一样声明函数

void sort( int *arr, size_t n );

并将数组中元素的数量明确地传递给函数。

请记住，通常情况下，用户可以将函数用于动态分配的数组。

请注意，您使用的算法不是插入排序算法。它是具有冗余交换的选择排序算法。

实现插入排序算法的函数可以按照以下方式进行查找，如下面的演示程序所示。

#include <stdio.h>
void insertion_sort( int a[], size_t n )
{
for ( size_t i = 1; i < n; i++ )
{
int current = a[i];
size_t j = i;
for ( ; j != 0 && current < a[j - 1]; j-- )
{
a[j] = a[j - 1];
}
if ( j != i ) a[j] = current;
}
}
int main()
{
int a[] = { 9,8, 7, 6, 5, 4, 3, 2, 1, 0 };
const size_t N = sizeof( a ) / sizeof( *a );
for (size_t i = 0; i < N; i++)
{
printf( "%d ", a[i] );
}
putchar( 'n' );
insertion_sort( a, N );
for (size_t i = 0; i < N; i++)
{
printf( "%d ", a[i] );
}
putchar( 'n' );
}

程序输出为

9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

至于实现选择排序算法的函数，那么在没有冗余交换的情况下，它可以按照下面的方式显示，如下一个演示程序所示。

#include <stdio.h>
void selection_sort( int a[], size_t n )
{
for ( size_t i = 0; i < n; i++ )
{
size_t min = i;
for ( size_t j = i + 1; j < n; j++ )
{
if (a[j] < a[min]) min = j;
}
if ( min != i )
{
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}
int main()
{
int a[] = { 9,8, 7, 6, 5, 4, 3, 2, 1, 0 };
const size_t N = sizeof( a ) / sizeof( *a );
for (size_t i = 0; i < N; i++)
{
printf( "%d ", a[i] );
}
putchar( 'n' );
selection_sort( a, N );
for (size_t i = 0; i < N; i++)
{
printf( "%d ", a[i] );
}
putchar( 'n' );
}

程序输出与上述相同

9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9

Answer 2

这是因为int size = sizeof(arr) / sizeof(arr[0]);将返回2，因为sizeof(arr)将给sizeof一个指向int的指针，在您的情况下是8字节，然后sizeof(arr[0])将给sizeofint，在您情况下是4字节

所以，

8 / 4 = 2

修复：

• 为数组的长度添加另一个参数
• 为sort()函数键入从numbers到(int *)的强制转换
• 您的sort()函数不实现插入排序算法，而是选择排序算法。阅读更多
• 代码中不需要stdlib.h头文件

这样：TRY IT ONLINE

#include <stdio.h>
void sort(int *arr, size_t len)
{
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
if (arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
// using `const` keyword, because `arr` isn't modifying inside `print()` function
void print(const int *arr, size_t len){
for (size_t i = 0; i < len; i++)
{
printf("%dn", arr[i]);
}
}
int main(void)
{
int numbers[10];
numbers[0] = 10;
numbers[1] = 9;
numbers[2] = 8;
numbers[3] = 7;
numbers[4] = 6;
numbers[5] = 5;
numbers[6] = 4;
numbers[7] = 3;
numbers[8] = 2;
numbers[9] = 1;
size_t len = sizeof(numbers) / sizeof(numbers[0]);
sort((int *)numbers, len);
print(numbers, len);
return 0;
}