数据结构-快速排序

实验报告：快速排序算法的实现 一．问题描述

通过改进的交换排序，提高排序效率，是快速排序的基本思想。 二．数据结构

使用线性表来存储序列，通过对线性表的操作来完成排序

ADT sqlist{ 数据对象：实数

数据关系：L={A1,A2,…,An} 基本操作：

inputlist(sqlist *L);//输入待排序的数列 printlist(sqlist *L); }ADT sqlist

三．算法设计与实现

从要排序的数组中任意选取一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，完成一趟快速排序。 步骤如下：

1.设置两个变量low、high，排序开始的时候：low=0，high=length；

2.以L[low]作为枢轴，赋值给pivotkey，即pivotkey=L[low]，同时用L[0]存储L[low]； 3.从high开始向前搜索，即由后开始向前搜索(high--)，找到第一个小于pivotkey的值L[high]，将L[high]赋给L[low]；

4.从low开始向后搜索，即由前开始向后搜索(low++)，找到第一个大于pivotkey的L[low]，将L[low]赋给L[high]；

5.重复第3、4步，直到low=high；将L[low]赋值为L[0]；

数组经过步骤1后，数组变为两部分，一部分大于某个数，而另一部分小于某个数。对这两部分作为两个子数组，分别进行步骤1。如此递归，直至数组不能再分，即数组仅有一个元素。

四．预期结果和问题

预期：正确完成数列排序，时间复杂度优于其他排序。 问题：

本文来源：https://www.bwwdw.com/article/uv8g.html