Question

C语言，快速排序算法

C语言，快速排序算法求详细分析这段快速排序的代码，quicksort(a,0,N-1)这里0和N-1代表是下标还是元素，又或者简单的数字0和9，还有递归那段请详细分析





Answer 1

你好！
首先 0 ，n-1 。应该是 数组的坐标（因为n个数字。所以数组的坐标是0 到n-1）
而a是你传入的数组。所以他会根据数组的坐标到数组中找到元素。比较并进行排序。
递归这段理解如下：
首先要了解快速排序的思想：
1）随意找一个基准数 。将比基准小的都放到它左边。比它大的都放到它右边。所以当返回基准的坐标的时候。其实这个坐标左边都是小于它的，右边都是大于等于它的。（这里主要是看代码的实现。图中代码是大于等于在右边。也可以自己写小于等于在左边。这个不影响最后结果）
2）那么第二次对于返回基准坐标的左右两边。我们同样利用返回的基准坐标找到两个“基准”（如下图）。就会使得返回的这两个基准左右两边有序
第三次  用返回的两个基准找到四个基准（如图）
然后不断递归..不断的在整体有序的情况下使局部变的有序。
假设 为  532348789
第一次以a【0】 5为基准 。
则：

图中红色标识为基准元素 最后会使得数组全局有序。
希望能对你有所帮助。

追问

思想我大概知道了，那两段while循环是怎么执行的，如果while()循环条件不成立的话？感觉有点看不懂，while没有{}的话他怎么执行？

还有，分割好左右数组后。那个quick的那个子函数是怎么进行快速排序的？

追答

恩，根据你图中的代码（老实讲，这图下次可以放好一些。方便看）
   1. while中如果循环条件不成立的话。
 要么是比较的元素坐标已经移动到当前位置。不需要再移动元素坐标了。
 要么是已经找到了比基准大（或者小的数）需要移动元素
   2.如果while没有{}的话就是
            只循环一句话 （到while最近的一个分号为while的内容）
  3. quick子函数快排的实现：
         划分为左右数组之后。quicksort子函数。就把每个数组。再次分为两个左右数组
         （直到不能分为止），循环调用 。P：如果这个明白，就不用看下面的了。
     通过代码看到 ： 该函数： 首先利用返回基准的函数 取得了一个中间基准的坐标。
     而返回中间基准坐标的函数，不仅是返回了基准的坐标，还按照基准把元素分成两部分了
     （我们知道这两部分相对来说是有序的，一部分都比另一部分大。但是单独一部分的内部是无序的）
     。所以 quicksort利用 返回基准的函数 。把自己传入的区间范围的元素。分为大小两个部分。
     然后获取范围的边界（基准元素坐标）。 
     再用返回的边界值。将这两个部分的范围 都再次传入 返回基准的函数 。 
     从而实现这两个部分 也 每个都分别分为相对有序的2个部分(1->2->4->...->2的n-1次方，n为调用quicksort的次数）.
      不断把大的范围变成小的范围。

1. while条件不成立的话。
   

   1）说明比较元素的坐标已经移动到当前位置，不需要在移动（此轮比较已经完成）

   2）已经找到比当前基准大（前一个while是大，后一个是小）的数字。需要移动元素位置。

2. while没有{} 就是执行一句话（离while最近的一个；）

3. 分割好左右数组之后。会返回左右数组的中间坐标（可能不太严谨。但是大概这个意思）

   然后quick利用中间值。可以确定左右数组的范围。将这两个左右数组的小范围分别调用

   返回基准的函数。就可以把左，右每个 数组都可以分割为两个更小的左右两个数组。

   这样循环调用一直分到不能分为止。整体便是有序的。

追问

最后一步还是不太理解他是怎么循环调用排序的

比如有七个元素
12 3 6 18 7 15 10
分割好数组后是10 3 6 7 12 15 18然后怎么递归的排序的？

我也知道，两个quick，一个是整理左边数组排序，一个是整理是右边数组排序。

但还是不明白，比如刚 才说的那个，10 3 6 7 12 15 18！12是分割元素的！不明白10是怎么排序过去的？

追答

不好意思，刚才没看到你所有问题， 补充一下：
10是怎么排序过去的：
while循环。第一个while从最后面开始遍历。比基准小的。会跟基准换位置。
第二个while 再从前面遍历。比基准大的。跟基准换位置。你可以按照程序流程走一走。
恩。对。第一次分割传入 a ， 0 ，6 之后是 10 3 6 7 12 15 18 返回的是： 4
然后获得 4 ，这时候
a【4】 = 12 不变了
1） 调用quick 传入 a ，0,3 a【0】-a【3】从 10 3 6 7 -> 3 6 7 10 返回 3
这时： a【3】=10 不变了
1.1） 返回3 调用 quick 传入 a ，0 ，2
a【0】-a【3】 367 - 》3 6 7
1.1.1）....
1.1.2).....
1.2 ）返回3 调用quick 传入 a ，4 ，3
这时候 low>high return ;
2）调用quick 传入 a ，5 ，6 a【5】-a【6】 15 18 -> 15 18返回 5
这时 a 【5】=15 不变了
.........
大致上是这样。你跟着流程自己按照程序走一遍应该就能理解了 。
就是分成两个数组。每个数组在调用quic分为两个数组。再次调用。 直循环调用到最后。
你把分割之后的数组看成独立的两个数组就可以了。

追问

脑子有点笨，a[0]-a[3]是怎么从10 3 6 7变成3 6 7 10的？

Answer 2

0和N-1表示的是数组下标。快排每一趟排序的目的是使值比设定的key值小的数都排到数组前部分，大的都排到后部分；然后对这两部分用新的关键值key分别重复上一步的操作；递归，直到数组有序。
其中关键值key=a[low]。
用题目给定的数组模拟第一趟排序如下：
下标    0    1    2    3    4    5    6    7    8    9
值      9    16   47   82   4    66   12   3    25   51
low=0 high=9
part_element=a[low]=9
进入for循环
进入第一个while
part_element<51，于是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不满足，结束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
进入第二个while
part_element<16,不满足，结束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一个循环结束，数组如下
3    16    47    82    4    66    12    16    25    51
low=1,high=6
for第二个循环同上，结束时数组如下
3    4    47    82    47    66    12    16    25    51
low=2,high=3
for第三个循环，第一个while中high--以后，low==high，直接break跳出for循环，此时
3    4    47    82    47    66    12    16    25    51
low=2,high=2
结束for以后
a[high]=a[2]=part_element=9,得到
3    4    9    82    47    66    12    16    25    51
split函数return high=2

quicksort函数中middle=2;
下面两句递归，仍然是调用split函数，对数组
0-2,3-9两部分分别重复上述操作

最后直到数组数据有序