之前看《算法導(dǎo)論》這本書，第一個算法就是（直接）插入排序，根據(jù)書里給出的偽代碼寫出了C語言代碼，也根據(jù)自己的理解重新寫了一個。雖然實(shí)現(xiàn)了算法的基本要求，但有些細(xì)節(jié)沒有處理好，今天就來完善一下。

在昨天實(shí)現(xiàn)的代碼中，用來測試的數(shù)組int array[] = {5,2,4,6,1,3};是固定的，如果要更換待排序數(shù)組話，原來程序中的相關(guān)變量就會因?yàn)閿?shù)組長度的改變要做相應(yīng)的改變。我想要的就是給定任意的數(shù)組，在不修改任意代碼的條件下實(shí)現(xiàn)插入排序。所以，核心問題就是怎么獲取給定數(shù)組中的元素個數(shù)。

自然而然想到的就是sizeof(C/C++中的一個操作符，其功能是返回一個對象或者類型所占的內(nèi)存字節(jié)數(shù))。
一、首先來看看怎么獲取整數(shù)數(shù)組的長度
sizeof的語法形式如下：
（1）sizeof(object); // sizeof( 對象 );
（2）sizeof(type_name); // sizeof( 類型 );
（3）sizeof object;// sizeof 對象;
個人喜歡使用sizeof(object)的形式，因?yàn)樾问浇y(tǒng)一，而且可以避免引起混亂導(dǎo)致出錯。
假設(shè)有一給定數(shù)組 int array[] = {5,2,4,6,1,3};，length為數(shù)組array[]中的元素個數(shù)，那么

length = sizeof(array)/sizeof(*array);            //表達(dá)式1
//length = sizeof(array)/sizeof(array[0]);        //表達(dá)式2
//length = sizeof(array)/sizeof(int);             //表達(dá)式3

上述三個表達(dá)式都能得到正確的結(jié)果，雖然表達(dá)式略有不同，但原理是相同的，即通過sizeof(array)獲取整個數(shù)組所占的內(nèi)存字節(jié)數(shù)，再通過sizeof(*array)或者sizeof(array[0])或者sizeof(int)來獲取每個元素所占的字節(jié)數(shù)，數(shù)組所占的字節(jié)數(shù)除以每個元素所占的字節(jié)數(shù)就是該數(shù)組的元素個數(shù)了。
二、字符串?dāng)?shù)組長度的獲取

char str[] = {"This is a string!"};
length = sizeof(str)-1;//包含空格

之所結(jié)果要減1，是因?yàn)樽址Y(jié)束符'\0‘在數(shù)組中占用了一個字節(jié)。

三、源代碼

/**************************************
*獲取字符串長度（元素個數(shù)）  By 羽墨
*print_length.c
***************************************/
#include <stdio.h>

void main()
{
    int array[] = {5,2,4,6,1,3};
    char str[] = {"This is a string!"};
    int length = sizeof(array)/sizeof(*array);
    printf("The length of string '%s' is %d\n",str,sizeof(str)-1);
    printf("The length of array is %d\n",length);
}

運(yùn)行結(jié)果

The length of string 'This is a string!' is 17
The length of array is 6

四、注意

1、如果在定義數(shù)組時就給定了數(shù)組的大小，如int array[len];，則不管數(shù)組中初始化了多少個（顯然應(yīng)不大于len）元素，最后的數(shù)組中的元素個數(shù)都是len。所以要想獲得數(shù)組中真實(shí)元素的個數(shù)，在初始化數(shù)組時應(yīng)注意這一點(diǎn)。

2、向子函數(shù)傳遞數(shù)組后，然后在子函數(shù)內(nèi)部獲取數(shù)組長度。先來看一個錯誤示例程序：

int getLength(int array[])
{
    int length;
    length=sizeof(array)/sizeof(array[0]); 
    return length;
}

len = getLength(array);
printf("The length of array is %d\n",len);

這樣得到的結(jié)果始終都是1。因?yàn)閿?shù)組作為參數(shù)傳給函數(shù)時傳的是指針而不是數(shù)組，傳遞的是數(shù)組的首地址。在本示例中，函數(shù)名array傳遞到子函數(shù)后就完全退化為一個指針，該指針指向的是數(shù)組array所在的地址，即數(shù)組array第一個元素array[0]所在的地址。也就是說系統(tǒng)只是告訴該函數(shù)這個存儲空間存有數(shù)據(jù)，但并沒有告訴函數(shù)這個數(shù)據(jù)存儲空間有多大。sizeof(array)的結(jié)果是指針變量array所占內(nèi)存的字節(jié)數(shù)，具體大小與系統(tǒng)有關(guān)，一般在32位機(jī)器上占4個字節(jié)，array[0]是int類型，同樣占4個字節(jié)，所以結(jié)果為1。所以要獲得數(shù)組的長度最好在數(shù)組定義所在的區(qū)域內(nèi)。

對于上述情形，查閱資料后給出兩種解決方案：

（1）進(jìn)入子函數(shù)后用函數(shù)memcpy將數(shù)組拷貝出來，函數(shù)memcpy所需要的長度由另一個形參傳遞進(jìn)來，像這樣：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**************************************
*摘自360百科（稍作修改）  By 羽墨
*將數(shù)組內(nèi)容拷貝到函數(shù)內(nèi)部
***************************************/
void fun(char *p, int len)
{
    char *pData;
    pData = (char*) malloc (len+1);      //申請內(nèi)存空間
    memcpy(pData, p, len+1);             //拷貝數(shù)組
    printf("%s\n",pData);
    //計(jì)算數(shù)組大小(略)
    free(pData);                          //釋放內(nèi)存
    pData = NULL;
}
void main ()
{
    char str[] = {"This is a string!"};//初始化數(shù)組
    fun(str, 17);
}

個人覺得沒有必要怎么做。如果能夠所需的長度作為形參傳遞到子函數(shù)中，顯然就不需要在子函數(shù)當(dāng)中另行計(jì)算，so，請看另一個方案。

（2）在子函數(shù)外部計(jì)算好元素個數(shù)后作為形參傳遞到子函數(shù)中進(jìn)行其他操作。在這里僅給出（直接）插入排序算法的main函數(shù)，insert_sort(array,length)函數(shù)只需將子函數(shù)中用于記錄數(shù)組元素個數(shù)的臨時變量length放進(jìn)子函數(shù)的參數(shù)列表即可。

void main()
{
    int array[] = {5,2,4,6,1,3};
    char str[] = {"This is a string!"};
    int length = sizeof(array)/sizeof(*array);    //計(jì)算數(shù)組中的元素個數(shù)

    printf("The original");
    print_array(array);

    insert_sort(array,length);                     //插入排序

    printf("The sorted");
    print_array(array);                             //輸出排序結(jié)果
}

這樣一來，對于任意的目標(biāo)序列都可以直接進(jìn)行排序而不需要修改任何程序語句。