快速排序的递归和非递归实现 c语言版本

小鱼儿 2022-05-14 00:39 226阅读 0赞

# 代码 #

## 挖坑法 ##

### 解释 ###

1.  选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列第一个数为枢轴，也是初始的坑位。
2.  设置两个变量i = l;j = r;其中l = 0, r = n - 1;
3.  从j一直向前走，直到找到一个小于pivot的值，然后将该数放入坑中，坑位变成了array\[j\]。
4.  i一直向后走，直到找到一个大于pivot的值，然后将该数放入坑中，坑位变成了array\[i\]。
5.  重复3和4的步骤，直到left和right相遇，然后将pivot放入最后一个坑位。

**当left >= right时，将key放入最后一个坑，就完成了一次排序。  
注意，left走的时候right是不动的，反之亦然。因为right先走，所有最后一个坑肯定在array\[left\]。**

#include <iostream>
    
    void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
            int i = l, j = r, pivot = s[l];
            while (i < j)
            {
                while (i < j && s[j] >= pivot)
                {
                    j--;
                }
                s[i] = s[j];
                while (i < j && s[i] <= pivot)
                {
                    i++;
                }
                s[j] = s[i];
            }
            s[i] = pivot;
            quick_sort(s, l, i - 1);
            quick_sort(s, i + 1, r);
        }
    }
    
    
    
    int main(int argc, char* argv[]) {
        int n;
        scanf("%d", &n);
        int *s = (int *)malloc(n * sizeof(int));
        for (int i  = 0; i < n; i++)
        {
            scanf("%d", &s[i]);
        }
        quick_sort(s, 0, n - 1);
        for (int i = 0; i <n; i++)
        {
            printf("%d ", s[i]);
        }
        printf("\n");
        return 0;
    }

## 非递归 ##

int partition(int *a, int left, int right)
    {
        int pivot = a[left];
        while (left < right)
        {
            while (left < right && a[right] >= pivot)
                right--;
            a[left] = a[right];
            while (left < right && a[left] <= pivot)
                left++;
            a[right] = a[left];
        }
        a[left] = pivot;
        return left;
    }
    
    void q_sort_stack(int *a, int n)
    {
        int left = 0;
        int right = n - 1;
        stack<int> s;
        s.push(left);
        s.push(right);
        while(!s.empty())
        {
            right = s.top();
            s.pop();
            left = s.top();
            s.pop();
            int index = partition(a, left, right);
            if (index - 1 > left)
            {
                s.push(left);
                s.push(index - 1);
            }
            if (index + 1 < right)
            {
                s.push(index + 1);
                s.push(right);
            }
        }
    }

# 一个要注意的问题 #

[C语言如何计算数组的长度][C]

[32位与64位下各类型长度对比][32_64]

当我计算数组长度时候，要在传函数之前计算，而不是在传完函数之后再计算  
64位系统下一个整形指针变量长度是8，而在32位系统下是4

# 参考链接 #

[https://blog.csdn.net/qq\_36528114/article/details/78667034\#commentBox][https_blog.csdn.net_qq_36528114_article_details_78667034_commentBox]

[C]: https://blog.csdn.net/i_pangpang/article/details/80197865
[32_64]: https://blog.csdn.net/sky_qing/article/details/11650497
[https_blog.csdn.net_qq_36528114_article_details_78667034_commentBox]: https://blog.csdn.net/qq_36528114/article/details/78667034#commentBox