序的过程，其结果分别让左右两个区域中的基准记录都到达它们的最终位置，同时将待排序记录序列分成更小的待排序区域，再次重复对每个区域进行一趟快束排序，直到每个区域只有一个记录为止，此时所有的记录都到达了它的最终位置，即整个待排序记录按关键值有序排列，至此排序结束。
对待排序记录序列进行一趟快速排序的过程描述如下：
(1) 初始化：取第一个记录作为基准，其关键字值为19，设置两个指针i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置。最开始从右侧开始比较，当发生交换操作后，转去再从左侧比较；
(2) 用基准记录与右侧记录进行比较：即与指针j指向的记录进行比较，如果右侧记录的关键字值大，则继续与右侧前一个记录进行比较，即j减1后，再用基准元素与j指向的记录比较，若右侧的记录小（逆序），则将基准记录与j指向的记录进行交换；
(3) 用基准元素与左侧记录进行比较：即与指针i指向的记录进行比较，如果左侧记录的关键字值小，则继续与左侧后一个记录进行比较，即i加1后，再用基准记录与i指向的记录比较，若左侧的记录大（逆序），则将基准记录与i指向的记录交换；
(4) 右侧比较与左侧比较交替重复进行，直到指针i与j指向同一位置，即指向基准记录最终的位置。
一趟快速排序之后，再分别对左右两个区域进行快速排序，以此类推，直到每个分区域都只有一个记录为止。下面是对关键字值为
（19,6,47,26,18,26,7,13）的记录序列进行快速排序的各趟状态
2. 快速排序算法
快速排序是一个递归的过程，只要能够实现一趟快速排序的算法，就可以利用递归的方法对一趟快速排序后的左右分区域分别进行快速排序。下面是一趟快速排序的算法分析：
(1) 初始化：将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置。
i=first; j=end;
将基准记录暂存在temp中。 temp=a[i];
(2) 对当前待排序区域从右侧将要进行比较的记录（j指向的记录）开始向左侧进行扫描，直到找到第一个关键字值小于基准记录关键字值的记录：
while (i (3) 如果i!=j，则将a[j]中的记录移至a[i]，并将i++： a[i]=a[j]; i++; (4) 对当前待排序区域从左侧将要进行比较的记录（i指向的记录）开始向右侧进行扫描，直到找到第一个关键字值大于基准记录关键字的记录： while (i (5) 如果i!=j，则将a[i]中的记录移至a[j]，并将j++： a[j]=a[i]; j++; (6) 如果此时仍i while （i 执行(2)、(3)、(4)、(5) 步骤 } a[i]=temp; 快速排序的完整算法： void quicksort (DataType a,int first,int end ) { i=first; j=end; temp=a[i]; //初始化 while(i { while (i while (i if (first if (i+1 } 快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记 录，从而加快了排序速度。到目前为止快速排序是平均速度最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。 快速排序是一种不稳定的排序，在递归调在递归调用时需要占据一定的存储空间用来保存每一层递归调用时必要信息。 9.4 选择排序 选择排序是指在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次小的记录、……，并分别将它们定位到序列左侧的第1个位置、第二个位置、……，最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到大排列的有序序列。 9.4.1 简单选择排序 1. 简单选择排序的基本思想 简单选择排序的基本思想是：每一趟在n-i+1(i=1,2,3,...,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。它的具体实现过程为： (1) 将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有n个记录。 (2) 设置一个整型变量index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将index改为这个新的最小记录位置，随后再用a[index].key 与后面的记录进行比较，并根据比较结果，随时修改index的值，一趟结束后index中保留的就是本趟选择的关键字最小的记录位置。 (3) 将index位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。 不断重复 (2)、(3)，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。 2. 简单选择排序算法 简单选择排序的整体结构应该为： for (i=1;i { 第i趟简单选择排序；} 进一步分析 \第i 趟简单选择排序\的算法实现。 （1）初始化：假设无序区域中的第一个记录为关键字值最小的元素，即将index=i; （2）搜索无序区域中关键字值最小的记录位置： for (j=i+1;j< =n;j++) if (a[j].key 将无序区域中关键字最小的记录与无序区域的第一个记录进行交换，使得有序区域由原来的i-1个记录扩展到i个记录。 完整算法： void selecsort ( DataType a, int n) { for( i=1; i
