一．问题描述

在操作系统中，我们总是希望以最短的时间处理完所有的任务。但事情总是要一件件地做，任务也要操作系统一件件地处理。当操作系统处理一件任务时，其他待处理的任务就需要等待。虽然所有任务的处理时间不能降低，但我们可以安排它们的处理顺序，将耗时少的任务先处理，耗时多的任务后处理，这样就可以使所有任务等待的时间和最小。

只需要将n 件任务按用时去从小到大排序，就可以得到任务依次的处理顺序。当有 n 件任务同时来临时，每件任务需要用时ni，求让所有任务等待的时间和最小的任务处理顺序。

二．基本要求

（1）数据的输入输出格式：

输入：

第一行是一个整数n，代表任务的件数。

接下来一行，有n个正整数，代表每件任务所用的时间。

输出：

输出有n行，每行一个正整数，从第一行到最后一行依次代表着操作系统要处理的任务所用的时间。按此顺序进行，则使得所有任务等待时间最小。

（2）使用快速排序，轴值采用随机数确定。

三．算法，数据结构

算法步骤为：

? 从数列中挑出一个元素，称为 "轴值"，

? 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割操作。

? 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代中，它至少会把一个元素摆到它最后的位置去。

数据结构：

function quicksort(q)

var list less, pivotList, greater

if length(q) ≤ 1 {

return q

} else {

select a pivot value pivot from q

for each x in q except the pivot element

if x < pivot then add x to less

if x ≥ pivot then add x to greater

add pivot to pivotList

return concatenate(quicksort(less), pivotList, quicksort(greater))

}

四．源程序

#include<iostream.h>

#include<stdlib.h>

#include<time.h>

const int N=50;

int Partition(int a[],int low,int high);

void QuickSort(int a[],int start,int end);

void change(int a[],int i,int j);

int main()

{

int a[N];

int l=0,sz;

cout<<"请输入数组的大小:\n";

cin>>sz;

srand(time(NULL));

// cout<<"请输入要排序的数组的值:\n"; for(int i=1;i<=sz;i++)

a[i]=rand()%20;//产生20以内的随机数 cout<<"排序前数组的值为:\n";

for(i=1;i<=sz;i++)

{

cout<<a[i]<<" ";

}

QuickSort(a,l,sz);

cout<<"\n排序后为:\n";

for(i=1;i<=sz;i++)

{

cout<<a[i]<<" ";

}

return 0;

}

int Partition(int a[],int low,int high)//以最后一位为轴 {

int temp=a[high];//轴

int i,j;

i=low;

j=high;

do

{

while(a[++i]<temp);//向右找到一个大于轴的值

while((a[--j]>temp)&&(j!=0));//向左找一个小于轴的值 change(a,i,j);//交换

}while(i<j);

change(a,i,j);//做多余的一次交换

return i;

}

void QuickSort(int a[N],int start,int end)

{

if(end<=start)

return;//没有数据或只有一个数据

int i;

if(start<end)//大于1个数据

{

i=Partition(a,start,end);

change(a,i,end);//交换轴的位置

QuickSort(a,start,i-1);

QuickSort(a,i+1,end);

}

}

void change(int a[N],int i,int j)

{

int t;

t=a[i];

a[i]=a[j];

a[j]=t;

}

五：测试分析

六：实验心得

这个实验中的关键代码老师上课都进行了重点讲解，所以不是很难。但是对于更好的理解快速排序有很大的帮助。

第二篇：《数据结构》实验报告——排序

《数据结构》实验报告 排序 实验题目：

输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。

实验所使用的数据结构内容及编程思路：

1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。

一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r［1..i-1］中插入一个记录r［i］后，变成含有i个记录的有序子序列r［1..i］；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在 r［0］处设置哨兵。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。

2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

假设待排序的序列为{L.r[s]，L.r[s+1],?L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i作为界线，将序列{L.r[s]，?，L.r[t]}分割成两个子序列{L.r[i+1],L.[i+2],?,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针low和high，他们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相 1

交换，重复这两不直至low=high为止。

具体实现上述算法是，每交换一对记录需进行3次记录移动（赋值）的操作。而实际上，在排列过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即low=high的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存在r[0]的位置上，排序过程中只作r[low]或r[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。

整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。

3.简单选择排序：其操作为，通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。

显然，对L.r[1?n]中的记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作。可以看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3（n-1）。然后，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为n(n-1)/2。

程序清单：

1．插入排序：

#include<stdio.h>

structsqlist

{int key[11];

int length;

}

insertsort(structsqlist *l)

{

inti,j;

for(i=2;i<=l->length;i++)

if(l->key[i]<l->key[i-1])

{l->key[0]=l->key[i];

l->key[i]=l->key[i-1];

for(j=i-2;l->key[0]<l->key[j];j--)

l->key[j+1]=l->key[j];

2

l->key[j+1]=l->key[0];

}

}

main()

{

inti,j,k;

structsqlistnum;

num.length=10;

for(i=1;i<=num.length;i++)scanf("%d",&(num.key[i])); insertsort(&num);

printf（“charu：”）；

for(i=1;i<=num.length;i++)printf("%d ",num.key[i]); }

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出：charu：8 9 12 23 34 37 45 56 67 98

2快速排序：

#include<stdio.h>

structsqlist

{

int key[11];

int length;

};

int partition(structsqlist *l,intlow,int high) {

intpivotkey;

l->key[0]=l->key[low];

pivotkey=l->key[low];

while(low<high)

{while(low<high&&l->key[high]>=pivotkey)high--; l->key[low]=l->key[high];

while(low<high&&l->key[low]<=pivotkey)low++; l->key[high]=l->key[low];

3

}

l->key[low]=l->key[0];

return low;

}

voidqsort(structsqlist *l,intlow,int high)

{intpivotloc;

if(low<high)

{pivotloc=partition(l,low,high);

qsort(l,low,pivotloc-1);

qsort(l,pivotloc+1,high);

}

}

void quicksort(structsqlist *l)

{

qsort(l,1,l->length);

}

main()

{

inti,j;

structsqlistnum;

num.length=10;

for(i=1;i<=num.length;i++)scanf("%d",&(num.key[i])); quicksort(&num);

printf（“kuaisu：”）；

for(i=1;i<=num.length;i++)printf("%d ",num.key[i]); }

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出：charu：8 9 12 23 34 37 45 56 67 98

3选择排序：

#include<stdio.h>

structsqlist

{int key[11];

int length;

4

};

intselectminkey(structsqlist *l,int a)

{

inti,j=a;

for(i=a;i<=l->length;i++)

if(l->key[i]<l->key[j])j=i;

return j;

}

voidselectsort (structsqlist *l)

{inti,j,k;

for(i=1;i<l->length;i++)

{j=selectminkey(l,i);

if(i!=j){k=l->key[i];

l->key[i]=l->key[j];

l->key[j]=k;}

}

}

main()

{

inti,j;

structsqlistnum;

num.length=10;

for(i=1;i<=num.length;i++)scanf("%d",&(num.key[i])); selectsort(&num);

printf（“xuanze：”）；

for(i=1;i<=num.length;i++)printf("%d ",num.key[i]); }

测试用例：

输入：23 34 12 98 56 45 67 8 9 37

输出：charu：8 9 12 23 34 37 45 56 67 98

编程感想：

5

本次编程总共使用了三种排序方法，而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻的了解。

首先，三种排序中，我们都像查表那样，设置了哨兵，而哨兵的使用可以减少对整个表的验空操作，使程序更加节省空间。

其次，对于插入排序，每次都要对一段序列进行检索，每排一次所要检索的序列长度减一，其时间发杂度为O（n^2）。

接着，对于快速排序，这个程序是比较复杂的，总共是3个函数，并且使用了递归的方法，这是但是，这种算法却是最优越的，平均性能也是最好的，我在编这个程序时，对其排序的思想有了进一步的了解，并努力拿他与冒泡排序进行比较，看出了些许其优越性。

还有，就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样，都是O（n^2），性能不如快速排序。

最后，本次试验是数据结构课的最后一次实验，经过数据结构试验课的锻炼，使我对数据结构有了更深刻的理解，对我对其知识起到了重要的影响，增加了我编程的实践活动，为我将来进一步学习打下了基础。

6