qq_37335168
2022-05-25 16:45
采纳率: 84%
浏览 14

下面迭代法快速排序算法的方法体中有一个地方不明白,该怎样解释呢?


//定义结构体类型Range
typedef struct _Range {
    int start, end;
} Range;
//获得结构体变量的函数:它表示一个数组中的区间,由起始点和结束点构成
Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}
//将x指向的元素和y指向的元素交换顺序:如果基准点左侧某个元素大于基准点且右侧有一个元素小于基准点,交换这两个元素
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
//快速排序的方法
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負值時引發段錯誤(Segment Fault)
    //技巧: r[]模擬列表,p為數量,r[p++]為push(它先使用,r[--p]為定位到前一个元素并取出该元素
    Range r[len];//结构体变量组成的结构体数组:变量个数等于数组元素个数?
    int p = 0;
    r[p++] = new_Range(0, len - 1);//存入一个结构体变量:它的成员分别表示区间开始值和结束值
    while (p) {//存入一个结构体变量之后p的值变成1,此时条件成立
        Range range = r[--p];//取出结构体数组种存入的结构体变量(它表示一个区间);注意--p是先运算再使用
        if (range.start >= range.end)
            continue;//如果取出的开始值大于结束值,则进行下一次循环
        int mid = arr[(range.start + range.end) / 2]; // 满足条件,選取区间中間點对应的元素為基準點
        int left = range.start, right = range.end;//区间的起始值赋值作为最左端元素的索引,结束值作为最右端元素的索引

        do
        {
            while (arr[left] < mid) ++left;   /* 檢測基準點左側是否符合要求,什么要求?检查基准点左侧的第一个元素值是否小于它,满足就把索引加上1继续判断左侧的下一个元素是否小于基准点,直到左侧的某个元素索引值加上1之后对应的元素大于基准点,则循环结束*/
            while (arr[right] > mid) --right; /*檢測基準點右側是否符合要求,要求:检查基准点右侧的最后一个元素值是否大于它,满足就把索引减去1继续判断右侧的上一个元素是否大于基准点,直到右侧的某个元素索引值减去1之后对应的元素小于基准点,则循环结束*/
 
            if (left <= right)/*只有这样前面给left和right的赋值才有意义;上面两个循环都得进入,只要有不满足的
            元素,就将它们的值交换,但交换后的元素有可能小于他前面已经判断的元素(左侧),但交换后的元素有可能大于他后面已经判断的元素(右侧),这是确定的,因为上面并未判断基准点左侧和右侧的元素的顺序*/
            {
                swap(&arr[left],&arr[right]);
                left++;right--;               /*移動指針以繼續。继续什么:判断左侧的下一个元素和右侧的上一个元素是否是否在小于基准点或大于基准点*/ 
            }
        } while (left <= right);/*当数组有奇数个元素时可能出现相等(等于中间元素的索引)的情况:此时直接执行到if语句块,交换后left > right,如果是偶数个元素则最终出现的是left>right;do-while循环结束;do-while循环保证了当前基准点左侧(部)的元素小于基准点,右侧(部)的元素大于基准点
        */
        if (range.start < right) r[p++] = new_Range(range.start, right);/*right经过do...while循环后已经是小于基准点的索引了,如果此时区间的起始值还小于它,那就在原来基准的左侧再建立一个区间(Range对象),存入结构体数组,*/
        if (range.end > left) r[p++] = new_Range(left, range.end);/*left经过do...while循环后已经是大于基准点的索引了,如果此时区间的结束值还大于它,那就在原来基准的右侧再建立一个新的区间(Range对象),也存入结构体数组*/
        /*如果两个条件都满足那么结构体数组岂不是右两个Range变量:r[0],r[1];且进入while循环中的p就等于2,用r[--p]取出来的是r[1]对应原基准点右侧(右部)的一个区间,下面将使用while循环来使得该索引区间中通新的基准点左侧都是小于它的元素,右侧都是大于它的元素;那么r[0]怎么办?原来基准点左侧的新的区间中的元素并没有被基准点分到小的在新的基准点左侧大的在新基准点基准点右侧,如果条件还满足的化这个工作还没有做就将新的基准点左侧和右侧又分别建立一个区间,这样一来第一次划分基准点之后左侧的元素继续划分区间就省略了,怎么最终得到正确的排序呢?*/
    }
}

最后两个if语句如果同时满足条件该怎样继续进行下面的while循环才能达到快速排序的算法要求?

1条回答 默认 最新

相关推荐 更多相似问题