论坛 › 数据结构与算法 › 快速排序算法

951923615 发表于 2016-3-28 12:23:14

快速排序算法

看了小甲鱼的快速排序算法，有一部分不懂，就是如视频后留的问题：
#include <stdio.h>

void swap(int k[], int low, int high)
{
        int temp;

        temp = k;
        k = k;
        k = temp;
}

int Partition(int k[], int low, int high)
{
        int point;

        point = k;

        while( low < high )
        {
                while( low < high && k >= point )//这里为何是>=,>号完全可以啦，不懂求解释
       
                        high--;
                }
                swap(k, low, high);
               
                while( low < high && k <= point )//这里为何是<=,<号完全可以啦，不懂求解释
                {
                        low++;
                }
                swap(k, low, high);
        }
   
        return low;
}

void QSort(int k[], int low, int high)
{
        int point;

        if( low < high )
        {
                point = Partition(k, low, high);

                QSort(k, low, point-1);

                QSort(k, point+1, high);
        }
}

void QuickSort(int k[], int n)
{
        QSort(k, 0, n-1);
}

int main()
{
        int i, a = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};

        QuickSort(a, 10);

        printf("排序后的结果是：");
        for( i=0; i < 10; i++ )
        {
                printf("%d", a);
        }
        printf("\n\n");

        return 0;
}

emrson 发表于 2016-3-28 17:34:40

假如要排的数是1 3 5 2 2 7 8    while( low < high && k=2 >= 2)      （（high=5）--）=4;也就是
k=2

jzh823 发表于 2016-3-29 08:57:04

快速排序是不稳定算法，就是原来相同的值，位置会变化。所以大于等于号，是针对算饭稳定不稳定来说的吧。

951923615 发表于 2016-3-29 14:34:50

emrson 发表于 2016-3-28 17:34
假如要排的数是1 3 5 2 2 7 8    while( low < high && k=2 >= 2)      （（high=5）--）=4;也就是
k ...

大哥数组是从0开始的，k=7，在说当数值相等时，比如你这个例子中的
k = k = 2，用快速排序不影响最后的结果的

951923615 发表于 2016-3-29 14:36:07

jzh823 发表于 2016-3-29 08:57
快速排序是不稳定算法，就是原来相同的值，位置会变化。所以大于等于号，是针对算饭稳定不稳定来说的吧。

知道是不稳定的算法，但是能不能举个特殊的反例，帮我解释下，太抽象的不好理解

ligen超越 发表于 2016-3-31 10:27:20

代码表示看不懂，能搞简单搞简单点，别一层套一层，这样速度回拖慢好多倍！
>= 或者>这个是在比较，这个是看相等的数是放在左边还是右边！不管左边还是右边，都一样！
{:10_249:}

飘渺463431810 发表于 2017-1-7 15:32:36

代码看不太明白

查看完整版本: 快速排序算法