C語言實(shí)現(xiàn)數(shù)組快速排序（含對算法的詳細(xì)解釋）

 以數(shù)組 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 32 39 23 45 36 57 14 27 39 為例，說明核心代碼的實(shí)現(xiàn)機(jī)制 第一輪： 首先進(jìn)入quickSort(a, 0, 10); key=0，i=0，j=10，進(jìn)入外層while，進(jìn)入第一個內(nèi)層while，由于0是數(shù)組中最小的，故j一直掃到頭，j=0,arr[0] = arr[0]=0; 顯然無法進(jìn)入第二個內(nèi)層while，由于i=j=0，結(jié)束外層while，執(zhí)行a[0]=key=0;顯然不進(jìn)入第一個if，進(jìn)入第二個if，執(zhí)行quickSort(a, 1, 10);進(jìn)行從a[1]到 a[10]的排序，第一輪結(jié)束。 第二輪; 執(zhí)行quickSort(a, 1, 10),key=2，i=1，j=10，進(jìn)入外層while，進(jìn)入第一個內(nèi)層while，由于2是傳入段中最小的，故j一直掃到頭，j=1,arr[1] = arr[1]=2;顯然 無法進(jìn)入第二個內(nèi)層while，由于i=j=1，結(jié)束外層while，執(zhí)行a[1]=key=2;顯然不進(jìn)入第一個if，進(jìn)入第二個if，執(zhí)行quickSort(a, 2, 10);進(jìn)行從a[2]到 a[10]的排序，第二輪結(jié)束。 第三輪： 執(zhí)行quickSort(a, 2, 10),key=32，i=2，j=10，進(jìn)入外層while，進(jìn)入第一個內(nèi)層while，a[10]=39>key=32,--j,j變?yōu)?;a[9]=27<key=32,,退出第一個內(nèi)層while， 執(zhí)行a[i]=a[2]=a[j]=a[9]=27,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 27 39 23 45 36 57 14 27 39 注意此時a[j]（即a[9]）的值存入a[i]（即a[2]）中，a[j]可以被再賦值，32呢？32怎么沒了呢？注意32始終由key保存，不用擔(dān)心。注意此時i=2，j=9； 程序順次執(zhí)行，滿足第二個內(nèi)層while，進(jìn)入，開始從左往右掃。a[2]=27<key=32,++i,i變?yōu)?（注意這是必然的，因?yàn)榈谝淮蔚腶[i]是由上次內(nèi)層while的a[j]送給 的，而送給的條件是a[j]（即這里的a[i]）<key）；a[i]=a[3]=39>key=32,執(zhí)行a[j]（前邊已經(jīng)說過，此時a[j]=a[9]的值已保存到a[2]中，a[j]可修改）=a[9]=a[3] =39，數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 27 39 23 45 36 57 14 39 39 注意此時a[i]=a[3]又變?yōu)榭尚薷摹?注意此時i=3<j=9,未跳出外層while。 繼續(xù)執(zhí)行第一個內(nèi)層while，a[j]=a[9]=39>key=32,--j,j變?yōu)?（這也是必然的，道理同前邊分析）；a[j]=a[8]=14<key=32，退出第一個內(nèi)層while， 執(zhí)行a[i]=a[3]=a[j]=a[8]=14,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 27 14 23 45 36 57 14 39 39 注意此時a[j]=a[8]又變?yōu)榭尚薷?。此時i=3,j=8; 程序順次執(zhí)行，滿足第二個內(nèi)層while，進(jìn)入，開始從左往右掃。a[i]=a[3]=14<key=32,++i,i變?yōu)?（必然）；a[i]=a[4]=23<key=32,++i,i變?yōu)?；a[i]=a[5]= 45>key=32,退出第二個內(nèi)層while，執(zhí)行a[j]=a[8]=a[i]=a[5]=45,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 27 14 23 45 36 57 45 39 39 注意此時a[i]=a[5]可修改，且i=5,j=8,未跳出外層while。 繼續(xù)執(zhí)行第一個內(nèi)層while，a[j]=a[8]=45>key=32,--j,j變?yōu)?（必然）；a[j]=a[7]=57>key=32,--j,j變?yōu)?；a[j]=a[6]=36>key=32,--j,j變?yōu)?注意到此時i=j=5， 直接退出三個while。執(zhí)行a[i]=a[5]=key=32,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 27 14 23 32 36 57 45 39 39 注意此時a[5]前的數(shù)都小于key=32，a[5]后的數(shù)都大于key=32，且startPos=2，endPos=10。 顯然兩個if都滿足，（這是人一次性判斷的，計(jì)算機(jī)只能先判斷第一個if，等程序再返回到本輪時再判斷第二個if，我們一次性判斷是為了說明方便）首先進(jìn)入第一個 if，執(zhí)行quickSort(a, 2, 4)，排a[5]前面的a[2]到a[4]（a[0],a[1]在第二輪后已排好)，進(jìn)入下一輪（第四輪），但第三輪未結(jié)束，因?yàn)橛?jì)算機(jī)還并未判斷第二個 if。 第四輪： 執(zhí)行quickSort(a, 2, 4)，key=a[2]=27,i=2,j=4,startPos=2,endPos=4。 進(jìn)入外層while，進(jìn)入第一個內(nèi)層while，a[j]=a[4]=23<key=27,執(zhí)行a[i]=a[2]=a[j]=a[4]=23,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 23 14 23 32 36 57 45 39 39 此時a[j]=a[4]可修改，且i=2,j=4,程序順次執(zhí)行，進(jìn)入第二個while，a[i]=a[2]=23<key=27,++i,i變?yōu)?（必然）：a[i]=a[3]=14<key=27,++i,i變?yōu)?，注意到i= j=4,退出所有循環(huán)，執(zhí)行a[i]=a[4]=key=27,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 23 14 27 32 36 57 45 39 39 此時i=j=4,startPos=2,endPos=4，顯然滿足第一個if不滿足第二個if（key后已無數(shù)），故執(zhí)行quickSort(a, 2, 3)（排a[4]前的），進(jìn)入下一輪（第五輪），但 第四輪未結(jié)束，因?yàn)橛?jì)算機(jī)還并未判斷第二個if。 第五輪： 執(zhí)行quickSort(a, 2,3)，key=a[2]=23,i=2,j=3,startPos=2,endPos=3。 進(jìn)入外層while，進(jìn)入第一個內(nèi)層while，a[j]=a[3]=14<key=23,執(zhí)行a[i]=a[2]=a[j]=a[3]=14,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 14 14 23 32 36 57 45 39 39 此時a[j]=a[3]可修改，且i=2,j=3,程序順次執(zhí)行，進(jìn)入第二個while，a[i]=a[2]=14<key=23,++i,i變?yōu)?（必然）：注意到i=j=3,退出所有循環(huán)，執(zhí)行a[i]=a[3]= key=23,數(shù)組變?yōu)?a[0] a[1] a[2] a[3]  a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 14 23 27 32 36 57 45 39 39 此時i=j=3,startPos=2,endPos=3，顯然不滿足第一個if，再判斷第二個，也不滿足，故第五輪結(jié)束，返回到上一輪（第四輪）的第二個if處，前面已經(jīng)分析過，不 滿足第二if，故第四輪結(jié)束，返回到上一輪（第三輪）的第二個if處（至此，到第三輪最終的a[i]=a[5]=key=32前的元素，都已排好），這次滿足。執(zhí)行 quickSort(a, 6, 10)，排a[5]后的元素，進(jìn)入下一輪（記為第四*輪，為的是與上面的第四輪區(qū)別，同時也為了體現(xiàn)兩者的聯(lián)系）。第三輪結(jié)束。 第四*輪： 執(zhí)行quickSort(a, 6, 10)，key=a[6]=36,i=6,j=10,startPos=6,endPos=10。 此時a[j]=a[3]可修改，且i=2,j=3,程序順次執(zhí)行，進(jìn)入第二個while，a[i]=a[2]=14<key=23,++i,i變?yōu)?（必然）：注意到i=j=3,退出所有循環(huán)，執(zhí)行a[i]=a[3]= a[j]=a[10]=39>key=36,--j,j變?yōu)?；a[j]=a[9]=39>key=36,--j,j變?yōu)?；a[j]=a[8]=45>key=36,--j,j變?yōu)?；a[j]=a[7]=57>key=36,--j,j變?yōu)?；注意到i=j=6， 退出所有while，執(zhí)行a[i]=a[6]=key=36，數(shù)組不變。此時i=j=6,startPos=6,endPos=10。顯然不滿足第一個if，滿足第二個if，執(zhí)行quickSort(a, 7, 10)（排 a[6]后的元素），進(jìn)入第五*輪，第四*輪結(jié)束。 第五*輪： 執(zhí)行quickSort(a, 7, 10)，key=a[7]=57,i=7,j=10,startPos=7,endPos=10。 a[j]=a[10]=39<key=57,執(zhí)行a[i]=a[7]=a[j]=a[10]=39,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 14 23 27 32 36 39 45 39 39 此時i=7,j=10,程序順次執(zhí)行，進(jìn)入第二個內(nèi)層while，a[i]=a[7]=39<key=57,++i,i變?yōu)?（必然）；a[i]=a[8]=45<key=57,++i,i變?yōu)?；a[i]=a[9]=39<key=57，++i, i變?yōu)?0；注意到i=j=10，退出所有while，執(zhí)行a[i]=a[10]=key=57。數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6]  a[7] a[8] a[9] a[10] 0 2 14 23 27 32 36 39 45 39 57 此時i=j=10,startPos=7,endPos=10。顯然滿足第一個if，不滿足第二個if（a[i]=a[10]后面已沒有元素），執(zhí)行quickSort(a, 7, 9)（排a[10]前面的元素），進(jìn)入 第六*輪，但未退出第五*輪，因?yàn)橛?jì)算機(jī)并還未判斷第二個if。 第六*輪： 執(zhí)行quickSort(a, 7, 9)，key=a[7]=39,i=7,j=9,startPos=7,endPos=9。 a[j]=a[9]=39=key=39,--j,j變?yōu)?；a[j]=a[8]=4>key=39,--j,j變?yōu)?；注意到i=j=7,退出所有while，執(zhí)行a[i]=a[7]=key=39，數(shù)組不變。此時i=j=7,startPos=7, endPos=9。顯然不滿足第一個if（a[i]=a[7]前已無元素），滿足第二個，執(zhí)行quickSort(a, 8, 9)（排a[7]后面的元素）,，進(jìn)入第七*輪，第六*輪結(jié)束。 第七*輪： 執(zhí)行quickSort(a, 8, 9)，key=a[8]=45,i=8,j=9,startPos=8,endPos=9。 a[j]=a[9]=39<key=45,執(zhí)行a[i]=a[8]=a[j]=a[9]=39,數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 14 23 27 32 36 39 39 39 39 此時i=8,j=9,程序順次執(zhí)行，進(jìn)入第二個內(nèi)層while，a[i]=a[8]=39<key=45,++i,i變?yōu)?（必然）； 注意到i=j=9，退出所有while，執(zhí)行a[i]=a[10]=key=57。數(shù)組變?yōu)?a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] 0 2 14 23 27 32 36 39 39 45 57 此時i=j=9,startPos=8,endPos=9，顯然不滿足第一個if，再判斷第二個，也不滿足，第七*輪結(jié)束。程序回到第五*輪的第二個if，前面已經(jīng)分析過，不滿足，故第五*輪結(jié)束。 至此，整個quickSort函數(shù)結(jié)束，數(shù)組已排好，如上所示。