(C语言详细版)第十章 内部排序.ppt

快速排序(Quick Sort) 快速排序是对起泡排序的一种改进。 算法思想 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s]，L.r[s+1]，…，L.r[t]}， 首先任意选取一个记录(通常可选第一个记录L.r[s]作为枢轴(或支点)(pivot)，然后按下述原则重新排列其余记录： 将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。 这个过程称作一趟快速排序(或一次划分)。 10.3 快速排序 一趟快速排序的具体做法 附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则 首先从high所指位置起向前有哪些信誉好的足球投注网站找到第一个关键字小于pivotkey的记录和枢轴记录互相交换， 然后从low所指位置起向后有哪些信誉好的足球投注网站，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换， 重复这两步直至low=high为止。其算法如算法10.6(a)所示。 10.3 快速排序 int Partition(SqList L，int low，int high) { //交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位， //并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。 pivotkey = L.r[low].key； //用子表的第一个记录作枢轴记录 while(lowhigh){ //从表的两端交替地向中间扫描 while(lowhighL.r[high].keypivotkey) --high; L.r[low]?L.r[high]; //将比枢轴记录小的记录交换到低端 while(lowhighL.r[low].keypivotkey) ++low; L.r[low]?L.r[high]; //将比枢轴记录大的记录交换到高端 } return low; //返回枢轴所在位置 }//partition 算法10.6(a) 10.3 快速排序 int Partition(SqList L，int low，int high){ //交换顺序表L中子表r[low．．high]的记录， //枢轴记录到位，并返回其所在位置， //此时在它之前(后)的记录均不大(小)于它。 L.r[0]=L.r[low]； pivotkey=L.r[low].key； //枢轴记录关键字 while(lowhigh){ //从表的两端交替地向中间扫描 while(lowhighL.r[high].keypivotkey) --high; L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端 low while(lowhigh L.r[low].keypivotkey)++low; L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端 } L.r[low]=L.r[0]; //枢轴记录到位 return low； //返回枢轴位置 }//Partition 算法10.6(b) 10.3 快速排序 快速排序示例： 初始关键字： 49 38 65 97 76 13 27 49* low high 进行1次交换之后： 27 38 65 97 76 13 49*