文档介绍：数据结构实验报告 4 (一)题目 1. 按下述原则编写快排的非递归算法: (1) 一趟排序之后,若子序列已有序( 无交换) ,则不参加排序,否则先对长度较短的子序列进行排序,且将另一子序列的上、下界入栈保存; (2) 若待排记录数<=3 ,则不再进行分割,而是直接进行比较排序。测试实例: {49 38 65 97 76 13 27 49 88 21 105} (二)算法思路(1) 建立存储序列上下界的栈序列。(2) 对栈顶作如下判断: A. 若栈顶中记录的头与尾相距小于 3 ,对对应的子序列进行排序,然后出栈,进入(3) ; B. 若栈顶中记录的头与尾相距大于等于 3 ,则进行分块,判断分块是否有序, a. 若两分块都有序,则出栈,进入(3) ; b. 若只有一分块有序,则改变栈顶内容为无序分块内容,进入(3) ; c. 若两分块都无序,则改变栈顶内容为较长的无序块,然后把较短的无序块压进栈。进入(3) (3) 重复(2) 的操作,直至栈空,得到最终结果。(三)程序结构定义的结构体及声明#define MAX_SEQ 100 // 最大输入数 typedef struct _stack{ int left; //lowerbound int right; //upperbound struct _stack *next; }qstack; //to store the child sequence's lowerbound and upperbound 主函数变量及其说明变量名说明 int array[MAX_SEQ] 存储输入序列 intn 输入的序列长度重要函数以及说明函数名功能变量说明 bool sorted(int *arr, int left, int right) 判断序列是否有序 arr 为等排序的数组, left 为下界, right 为下界。有序或者是 left>right 时返回 true ,否则返回 false void sort(int *arr, int left, int right) 给三个或三个以下的序列排序 arr 为等排序的数组; left 为下界; right 为下界。 void qsort(int *arr, int left, int right) 快速排序同上(四)源码#include <iostream> #define MAX_SEQ 100 using namespace std; typedef struct _stack{ int left; //lowerbound int right; //upperbound struct _stack *next; }qstack; //to store the child sequence's left and right void sort(int *arr, int left, int right){ //sort child sequence less than 3 for(int i= left; i <= right; i++){ intk= i; for(int j= i+1; j <= right; j++){ if(arr[k] > arr[j]) k= j;} if(k != i){ int t;t= arr[k]; arr[k] =