快速排序

代码片段

快速排序

适用于 PostgreSQL

8.4+

用

SQL

依赖于

无

使用递归 CTE 表达式实现的纯 SQL 快速排序算法，作者 N. Can KIRIK ( can(at)epati.com.tr )

PS。 此实现资源消耗极高，仅用于教育目的。 不要在生产环境中使用此实现，而是使用“intarray”扩展包的“sort”函数。

---

一个状态栈，用于模拟函数调用栈。 由于 CTE 表达式的递归功能本质上的差异，没有栈就无法实现这一点。

一个自定义复合类型，使用自定义枚举类型 (direction) 来跟踪状态 (调用栈数据类型)

CREATE TYPE "enum_quickSort_direction" AS ENUM ('up', 'down', 'left', 'right');

CREATE TYPE "t_quickSort_status" AS ("direction" "enum_quickSort_direction", "left" int4, "pivot" int4, "right" int4);

---

此简写函数用于交换数组中的元素。

CREATE OR REPLACE FUNCTION "fn_quickSort_swap"( "myArray" _int4, "old" int4, "new" int4) RETURNS _int4 AS $BODY$

SELECT
    CASE
    WHEN $2 = $3 THEN
        $1
    ELSE 
        CASE
        WHEN ARRAY_LOWER( $1, 1 ) <= LEAST( $2, $3 ) - 1 THEN 
            $1[ ARRAY_LOWER( $1, 1 ) : LEAST( $2, $3 ) - 1 ] || $1[ GREATEST( $2, $3 ) ]
        ELSE
            ARRAY[ $1[ GREATEST( $2, $3 ) ] ]
        END
    ||
        CASE
        WHEN $2 != $3 THEN
            $1[ LEAST( $2, $3 ) + 1 : GREATEST( $2, $3 ) - 1 ] || $1[ LEAST( $2, $3 ) ]
        ELSE
            ARRAY[ $1[ LEAST( $2, $3 ) ] ]
        END
    ||
        $1[ GREATEST( $2, $3 ) + 1 : ARRAY_UPPER( $1, 1 ) ]
    END
;

$BODY$ LANGUAGE 'sql' IMMUTABLE;

---

分区函数是快速排序算法的核心功能，使用递归 CTE 的“t_quickSort_partitionResult”自定义复合类型实现，能够返回两个不同的值，分别是枢轴索引和已分区数组。

CREATE TYPE "public"."t_quickSort_partitionResult" AS  ( "pivot" int4, "myArray" int4[] );

CREATE OR REPLACE FUNCTION "public"."fn_quickSort_partition"( "myArray" _int4, "left" int4, "right" int4 ) RETURNS "t_quickSort_partitionResult" AS $BODY$

WITH RECURSIVE
    "partition" AS (
        SELECT
             $2 AS i
            ,$2 AS "index"
            ,"fn_quickSort_swap"( $1, ( $2 + $3 ) / 2, $3 ) AS "a"
        WHERE
            $2 < $3
    UNION ALL
        SELECT
             i + 1
            ,"index" + ( "a"[ i ] <= "a"[ $3 ] )::INT
            ,CASE WHEN "a"[ i ] <= "a"[ $3 ] AND i != "index" THEN "fn_quickSort_swap"( "a", i, "index" ) ELSE "a" END
        FROM
            "partition"
        WHERE
            i < $3
    )
SELECT
    ROW(
         "index"
        ,"fn_quickSort_swap"( "a", "index", $3 )
    )::"t_quickSort_partitionResult"
FROM
    "partition"
WHERE
    i = $3
;

$BODY$ LANGUAGE 'sql' IMMUTABLE;

---

主函数 QuickSort，也使用递归 CTE 实现

CREATE OR REPLACE FUNCTION "fn_quickSort"( _int4 ) RETURNS _int4 AS $BODY$

WITH RECURSIVE
     "sort" AS (
        SELECT
             $1 AS "myArray"
            ,ARRAY[ ROW( 'down', ARRAY_LOWER( $1, 1 ), NULL, ARRAY_UPPER( $1, 1 ) )::"t_quickSort_status" ] AS "status"
    UNION ALL
        SELECT
             "myArray"
            ,CASE 
                WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'down'  THEN "status"[ 1 : "idx_active" - 2 ]
                WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'right' THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
                WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'left'  THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'right', ( "previous" )."left", ( "previous" )."pivot", ( "previous" )."right" )::"t_quickSort_status"
                WHEN "left" < "right"                                                         THEN "status" || ROW( 'left', "left", "pivot", "right" )::"t_quickSort_status"
                WHEN ( "active" )."direction" = 'right'                                       THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
                WHEN ( "active" )."direction" = 'left'                                        THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'right', ( "active" )."left", ( "active" )."pivot", ( "active" )."right" )::"t_quickSort_status"
            END
        FROM
            (
                SELECT
                    ( COALESCE(
                        "fn_quickSort_partition"( "myArray", "left", "right" )
                        ,ROW( ( "active" )."pivot", "myArray" )::"t_quickSort_partitionResult"
                    ) ).*
                    ,"left"
                    ,"right"
                    ,"status"
                    ,"idx_active"
                    ,"active"
                    ,"previous"
                FROM
                    (
                        SELECT
                             "myArray"
                            ,CASE ( "active" )."direction"
                                WHEN 'up'    THEN 0
                                WHEN 'down'  THEN ( "active" )."left"
                                WHEN 'left'  THEN ( "active" )."left"
                                WHEN 'right' THEN ( "active" )."pivot" + 1
                            END AS "left"
                            ,CASE ( "active" )."direction"
                                WHEN 'up'    THEN 0
                                WHEN 'down'  THEN ( "active" )."right"
                                WHEN 'left'  THEN ( "active" )."pivot" - 1
                                WHEN 'right' THEN ( "active" )."right"
                            END AS "right"
                            ,"status"
                            ,"idx_active"
                            ,"active"
                            ,"previous"
                        FROM
                            (
                                SELECT
                                    *
                                    ,ARRAY_LENGTH( "status", 1 ) AS "idx_active"
                                    ,"status"[ ARRAY_LENGTH( "status", 1 ) ] AS "active"
                                    ,"status"[ ARRAY_LENGTH( "status", 1 ) - 1 ] AS "previous"
                                FROM
                                    "sort"
                                WHERE
                                    ARRAY_LENGTH( "status", 1 ) > 0
                            ) s
                    ) s
            ) s
    )
SELECT
    "myArray"
FROM
    "sort"
WHERE
    "status"[ 1 ] IS NULL
LIMIT 1;

$BODY$ LANGUAGE 'sql' IMMUTABLE;

---

PS。 此实现资源消耗极高，仅用于教育目的。 不要在生产环境中使用此实现，而是使用“intarray”扩展包的“sort”函数。