C語言實現數組快速排序（含對算法的詳細解釋）

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