c语言插入法排序的算法步骤

Python011

c语言插入法排序的算法步骤,第1张

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

范例程式码

void insertion_sort(int array[], int first, int last)

{

int i,j

int temp

for (i = first+1i<=lasti++)

{

temp = array[i]

j=i-1

while((j>=first) &&(array[j] >temp))

{

array[j+1] = array[j]

　j--

}

array[j+1] = temp

}

}

        通过C语言实现插入排序算法：对于少量排序的元素，插入排序是一个有效的算法，其操作过程类似于手中的扑克牌，从第二个元素从左往右循环检查比较，满足A[i]<A[i-1],则交换A[i]与A[i-1]的值。往复循环直到最后一个元素比较完成。具体程序如下：

#include <stdio.h>

#include<conio.h>

/*----------

*INSERT_SORT

*

* args

* A[] int[],the number of A arrary

* len int ,A length

*

------------*/

void insert_sort(int A[],int len){

    int i,j,key

    //printf("A length %d\n",len)  //output arrary length

    for(j=1j<lenj++){

        key=A[j]

        i=j-1

        while (i>-1&&A[i]>key) {    //i from 0 to 5,so i>-1

            A[i+1]=A[i]

            i=i-1

            A[i+1]=key

        }

    }

    //output A arrary

    for(i=0i<leni++)

        printf("%d ",A[i])

}

int main()

{

    int A[10]

    int i=0

    char c

    while(1){

        scanf("%d",&A[i])//input unmbers

        c=getchar()

        if(c=='\n')

            break

        i++

    }

    //printf("%d %d %d %d %d %d %d %d\n",A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7])

    //use insert_sort

    insert_sort(A,i+1)//A length is i+1

    return 0

}

/*---test------------

* input 5 2 4 6 1 3

*

* output 1 2 3 4 5 6

* ------------------*/

以上程序使用的是Qt Creator 工具，用C语言实现，经调试已经通过。

但依然有个问题：在main（）函数中调用insert_sort(int A[])时，若单传数组参数A[]，再在insert_sort(int A[])函数里面调用len=sizeof(A)/sizeof(int)计算数组实际输入长度，但是得不到实际输入的数组长度，所以只能采用实参的方式将具体数字通过len传到insert_sort(int A[],int len )；在insert_sort(int A[])接收到A数组后直接计算A[]实际输入长度，有什么办法可以实现？

int main ()

{

int i

DataType a[MaxSize]

SqList L

srand((unsigned)time(NULL))

for (i=0i<MaxSizei++)

{

int number = rand()%MaxSize + 1

//printf ("%d ",number)

a[i].key = number

L.data[i].key = a[i].key

}

return 0

}