create or replace package plsql_algorithm is-- Author : cs-- Created : 2019/9/4 14:27:08-- Purpose : plsql排序算法N constant int := 9;-- 数组类型type typ_array is table of int index by pls_integer;--初始化数组procedure init_array;procedure init_array_asc;procedure init_array_desc;--打印数组procedure print_array;--*********************常用排序算法*********************-- 选择排序procedure selectionSort;-- 冒泡排序procedure bubbleSort;-- 插入排序procedure insertSort;-- 快速排序procedure quickSort(p int default 1, r int default N);function Partition(p int, r int) return int;--归并排序procedure mergeSort(p int default 1, r int default N);procedure merge(p int, r int);
end plsql_algorithm;
create or replace package body plsql_algorithm is-- 私有静态变量-数组长度--n constant int := 9;-- 私有变量array typ_array;-- 临时数组--归并排序用array_tmp typ_array;--初始化数组procedure init_array isbegin-- 初始化array(1) := 8;array(2) := 1;array(3) := 2;array(4) := 7;array(5) := 4;array(6) := 6;array(7) := 3;array(8) := 9;array(9) := 5;end init_array;procedure init_array_asc isbegin-- 初始化array(1) := 1;array(2) := 2;array(3) := 3;array(4) := 4;array(5) := 5;array(6) := 6;array(7) := 7;array(8) := 8;array(9) := 9;end init_array_asc;procedure init_array_desc isbegin-- 初始化array(1) := 9;array(2) := 8;array(3) := 7;array(4) := 6;array(5) := 5;array(6) := 4;array(7) := 3;array(8) := 2;array(9) := 1;end init_array_desc;--打印数组procedure print_array isbeginfor i in 1 .. n - 1 loopdbms_output.put(array(i) || '->');end loop;dbms_output.put(array(n));dbms_output.put_line('');end print_array;-- selectionsort/*选择排序(以升序排序为例):每次从未排序区间选择一个最小的元素,放在已排序的末尾*/procedure selectionSort isi int;j int;m int; --最小值下标t int; --交换使用的临时变量begin--排序代码for i in 1 .. n loop--寻找最小元素m := i;for j in i + 1 .. n loopif (array(j) < array(m)) thenm := j;end if;end loop;--交换t := array(i);array(i) := array(m);array(m) := t;end loop;end selectionSort;-- bubblesort/*冒泡排序(以升序排序为例):它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从a到z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。*/procedure bubbleSort isi int;j int;t int; --交换使用的临时变量flag int := 0; --交换标记,如果一次冒泡没有元素交换,说明已经有序了,不需要再冒泡了begin--排序代码for i in 1 .. n loopflag := 0; --交换标记for j in 1 .. n - i loop--如果前者大于后者,交换if (array(j) > array(j + 1)) thenflag := 1;t := array(j);array(j) := array(j + 1);array(j + 1) := t;end if;end loop;--已经有序了,不需要再冒泡了,跳出if (flag = 0) thengoto next_loop;end if;end loop;<<next_loop>>null; --不可少 end bubbleSort;-- insertSort/*插入排序(以升序排序为例):每次从未排序区间选择第一个元素,插入到已排序区间。*/procedure insertSort isi int;j int;t int; --交换使用的临时变量begin--排序代码for i in 1 .. n loopfor j in reverse 2 .. i loop--查找插入位置if (array(j) < array(j - 1)) thent := array(j - 1);array(j - 1) := array(j);array(j) := t;end if;end loop;end loop;end insertSort;-- quickSort/*快速排序(以升序排序为例):递归实现每次从区间末尾选取一个元素,将区间分为2部分,前半部分小于给定值,后半部分大于等于给定值 需要先实现一个partition分区函数*/procedure quickSort(p int, r int) isq int;begin--递归结束条件if (p >= r) thenreturn;end if;--排序代码q := Partition(p, r);quickSort(p, q - 1);quickSort(q + 1, r);end quickSort;function Partition(p int, r int) return int isi int;j int;t int;pivot int; --分隔元素的值,默认选区间最后一个q int; --排序完成后,分割点的下标begini := p;j := p;pivot := array(r);--i指正依次后退,j指针在发生元素交换时后退(元素小于pivot时),指向下一个交换位置for i in p .. r - 1 loopif (array(i) < pivot) then--交换i和j的元素,同时j后移t := array(i);array(i) := array(j);array(j) := t;j := j + 1;end if;end loop;--交换array(j)和pivott := array(j);array(j) := pivot;array(r) := t;q := j;--dbms_output.put_line(q);return q;end Partition;--归并排序procedure mergeSort(p int, r int) isq int;beginq := trunc((p + r) / 2); --中点,前半部分的最后一个元素下标if (r <= p) thenreturn;end if;mergeSort(p, q);mergeSort(q + 1, r);merge(p, r);end mergeSort;procedure merge(p int, r int) isq int;i int;j int;k int := p; --临时数组指针beginq := trunc((p + r) / 2); --中点,前半部分的最后一个元素下标i := p; --前半部分指针j := q + 1; --后半部分指针while (i <= q and j <= r) loopif (array(j) < array(i)) thenarray_tmp(k) := array(j);j := j + 1;k := k + 1;elsearray_tmp(k) := array(i);i := i + 1;k := k + 1;end if;end loop;--剩下的直接拷贝while (i <= q) looparray_tmp(k) := array(i);i := i + 1;k := k + 1;end loop;while (j <= r) looparray_tmp(k) := array(j);j := j + 1;k := k + 1;end loop;--数组拷贝for i in p .. r looparray(i) := array_tmp(i);end loop;end merge;begin-- 初始化array(1) := 8;array(2) := 1;array(3) := 2;array(4) := 7;array(5) := 4;array(6) := 6;array(7) := 3;array(8) := 9;array(9) := 5;end plsql_algorithm;
---测试脚本
beginplsql_algorithm.init_array;plsql_algorithm.print_array;plsql_algorithm.selectionSort;plsql_algorithm.bubbleSort;plsql_algorithm.insertSort;plsql_algorithm.quickSort;plsql_algorithm.mergeSort;plsql_algorithm.print_array;
end;