内容发布更新时间 : 2024/6/2 22:14:54星期一 下面是文章的全部内容请认真阅读。

快速排序

一、问题描述

排序是数据结构中典型的算法，经常有插入排序、选择排序、快速排序等。本文要求对排序表中的无序数据进行快速排序，并讨论快速排序的改进方法（双倍快速排序、基于归并的快速排序），这样可以对排序进行优化，提高效率。

二、基本要求

1、选择合适的存储结构建立排序表，并能遍历表输出元素。 2、编写快速排序算法，并能够输出排序的结果。

3. 快速排序及其改进—双倍快速排序和基于归并的快速排序算法。

三、测试数据

输入以下数据：5 、3、7、11、1、9、4、8

四、算法思想

1、普通快速排序的基本思想：可以运用一趟快速排序把序列分成分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行快速排序，以达到整个序列有序。一趟的快速排序是：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey,则首先从high所指位置起向前搜索到第一个关键字小于pivotkey大的记录和枢轴记录互相交换，然后从low所指位置向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两部直至low=high为止。

2、双倍快速排序思想：快速排序的基本思想是基于分支策略的思想。即对于输入的子序列L[low..high],如果规模足够小则直接进行排序,否则分三步处理:

1) 分解(Divide) :设输入的序列L[low..High],确定支点元素L[low]和L[High],并使L[Low].key<=Ll[High].key ,然后分解(Divide):将序列L[low ..High ]划分成三个子序列L[Low..L-1]、L[L+1..H-1]和L[H+1..High],使L[low ..High]中元素的关系为L[Low..L-1]

2) 递归求解(Conquer) :通过递归调用快速排序算法分别对L[Low..L-1]、L[L+1..H-1]和L[H+1..High]分别进行分解排序。

3) 合并(Merge):对分解出的三个子序列的排序是就地进行的,所以在L[Low..L-1]、 L[L+1..H-1] 和L[H+1..High]都排好序后不需要执行任何计算L[low..High]就已排好序。 3、基于归并的快速排序：对划分结果产生的两个子序列的长度进行检查，如果其中一个与另一个的长度比超过某一界限，则认为这是一个“畸形划分”，对较短的子序列继续使用“快速排序”，而把较长的子序列平分为两个子序列分别排序，然后再进行一次合并。两个有序序列的合并是可以实现为线性的时间复杂度的，因此可以在每次都是畸形划分时仍然

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

获得O(N*LogN)的时间复杂度。其中Partition就是众所周知的用于“快速排序”的划分子程序，Merge(Data, First,Size)把Data中[0,First)和[First, Size)两个有序列合并为一个有序序列并存放在Data中。Partition划分的位置M处的值就是划分的枢值，也就是说序列可以分成[0,M-1]、[M,M]和[M+1,Size-1]三部分。如果Partition的实现不能保证这一点，则MoreData应为Data[M]，而MoreSize也应为Size - M。

五、模块划分

1、void Create(SqList *L)，建立排序表。

2、void Traverse(SqList L)，遍历排序表(输出哨兵)。 3、void swap(int *a,int *b)，用于交换两个数。

4、int Partition(SqList *L, int low, int high)，将一个序列划分成两个子序列，后一子序列所有值都不大于前一子序列任意值。返回子序列分割处索引。 5、void QSort1(SqList *L, int low, int high)，调用快排函数进行排序。 6、int QSort2(SqList *L, int low, int high)，调用双倍快排函数进行排序。 7、void Merge (RedType SR[], RedType TR[], int i, int m, int n)，两个有序序列合并为一个有序列序。

8、void MSort(RedType SR[], RedType TR1[], int s, int t)，归并排序。 9、int qsort1(SqList *L, int low, int high)，快速排序。 10、void menu，输出时清晰。 11、int main()，主函数。

六、数据结构//(ADT)

数据类型

typedef int KeyType;/*定义关键字类型为整数类型 */ typedef struct

{ KeyType key;/*定义关键字*/ /*其它域:略*/ } RedType;/*记录类型*/ typedef struct

{ RedType r[MAXSIZE+1];/*定义数组*/ int length;/*表长*/ } SqList;/*顺序表类型*/

七、源程序

#include \

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

#include \#define MAXSIZE 100 #define N 10 #define M 3

#define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

typedef int KeyType; typedef struct { KeyType key; /*其它域:略*/ } RedType; typedef struct

{ RedType r[MAXSIZE+1]; int length; } SqList;

/* 排序表的建立 */ void Create(SqList *L) { int i,n;

printf(\请输入表长:\ printf(\请输入%d元素:\ for(i=1; i<=n; i++)

scanf(\ L->length=n; }

/* 遍历排序表(输出哨兵) */ void Traverse(SqList L) { int i;

for(i=1; i<=L.length; i++)

/*交换函数*/

void swap(int *a,int *b)

printf(\

wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802