3.3    随机编排考生座位
快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。
而本设计中的随机排序思想则是通过三对数组来实现的。首先将学号、学生姓名存入一个数组,其次将教室内的排、列分别封装如另外两个数组。然后通过循环学生数组的长度,同时每次循环内再嵌套一个生成随机数的循环,而所得随机数即成为排、列数组的索引。本系统的随机排序思路是通过数组的索引来实现的,首先将教室的排、列分别装入两个数组,而后通过选取两个随机数(两个数的范围分别在相应数组的索引内)作为数组的索引。将所对应的排、列数据取出,再与考生信息共同装入一个新的datatable内,同时在原有数组内剔除所挑选出来的数据。以此实现随机排序的核心功能。
建立两组数组的程序代码:
int[] row = new int[rows]; int[] col = new int[cols]; int stuSum = stuList.GetLength(0);
            for (int j = 0; j < rows; j++) { row[j] = j; }
            for (int k = 0; k < cols; k++) { col[k] = k; }
            string[] StuX = new string[stuSum]; string[] StuY = new string[stuSum];
            for (int L1 = 0; L1 < stuSum; L1++) { StuX[L1] = stuList[L1, 0]; }
            for (int L2 = 0; L2 < stuSum; L2++) { StuY[L2] = stuList[L2, 1]; }
通过嵌套循环实现随机挑选索引并且装入datatable的核心代码:
for (int a = 0; a < rows; a++)            //自动排序核心方法
            {
                for (int b = 0; b < cols; b++)
                {
                    if (StuX.Length > 0)
                    {
                        int rd = rand.Next(0, StuX.Length);
                        DataRow dr = seat.NewRow();
上一篇:Windows下USB驱动程序的设计
下一篇:OSPF大型企业内网构建设计与实现

jsp+mysql图书馆座位管理系统设计

C#+access人才招聘系统的设计+源代码

C3图书馆座位预约系统的设计

C#+access学生成绩管理系统设计+源代码

Java+mysql图书馆座位预约管理系统设计+源代码

C#+access个人理财软件的设计+源代码

JSP图书馆座位管理系统设计+文献综述

承德市事业单位档案管理...

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

C#学校科研管理系统的设计

医院财务风险因素分析及管理措施【2367字】

公寓空调设计任务书

国内外图像分割技术研究现状

神经外科重症监护病房患...

志愿者活动的调查问卷表

AT89C52单片机的超声波测距...