排序算法整理

╰+哭是因爲堅強的太久メ 2022-07-12 13:51 138阅读 0赞

快速排序算法

快速排序关键在于分组法

public static void QSort(int\[\] a, int x, int y)  
    \{  
        if (x < y)  
        \{  
            int i = Partition(a, x, y);  
            QSort(a, x, i - 1);  
            QSort(a, i + 1, y);  
        \}  
    \}

先说一种:边界交换法

public static int Partition(int\[\] a, int x, int y)  
    \{  
        int pivot = x; // 选择x为轴，分小集合与大集合。此时状态\{null|pivot|大集合\}  
        for (int i = x; i <= y; i++) // 遍历  
        \{  
            if (a\[i\] < a\[x\]) // 当前元素小于轴元素，则与小集合的边界a\[pivot+1\]交换  
            \{  
                swap(a, i, pivot+1);//(注:不要交换pivot,其值变化将会引发后续比较错误。也可以先将其交换至最后)  
                pivot++;// 轴向右移动一位(每移动一位说明小集合中多一个元素)  
            \}  
        \}  
        swap(a, x, pivot);// 最后轴与小集合边界交换，构成\{小集合|pivot|大集合\}  
        return pivot;  
    \}

第二种：双向缩进法

public static int Partition1(int\[\] a, int x, int y)  
    \{  
        int pivot = a\[x\];  
        while (x < y)  
        \{  
            while (x < y && a\[y\] >= pivot)    y--;  
            a\[x\] = a\[y\];  
            while (x < y && a\[x\] <= pivot)    x++;  
            a\[y\] = a\[x\];  
        \}  
        a\[x\] = pivot;  
        return x;  
    \}