快速排序—分类浮沉法

前言在计算机处理大量数据排序问题时,人们总希望用最快的速度来完成。为此,除选择运算速度快的机型、采用编译 BASIC 运行或用汇编语言编写程序外,更重要的是研究新的排序方法,以提高排序速度。本文介绍一种新的快速排序方法,即分类浮沉法。一、排序的基本原则与方法分类浮沉法的排序原则是利用数组下标变量的有序性,将数据按其大小的等级进行分类排队后,置入数组相应的下标变量中,完成排序工作。其方法是将待排序的 N 个数据,按大小等级划分成 M 组,一次置入二维数组 F(M,N)中,并用数组 T(M)记录每组数据的个数,完成一次排队。然后用浮沉法对各组内的数据按大小排序,即二次定位。所谓浮沉法,是对各组中的数据依次将大数和小数分别由外至内置入数组F(M,N)中。其特点是经过一个循环,同时将两个数定位于数组变量中,大数(或小数)浮起。