C语言实现数组快速排序（含对算法的详细解释）

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]=27key=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=3key=32,--j,j变为8（这也是必然的，道理同前边分析）；a[j]=a[8]=14key=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]=23key=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]=39key=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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。