Case Study:快排序算法的并行化 *快速排序及其串行算法 *快速排序(Quick Sort)是一种最基本的排序算法，它的 基本思想是：在当前无序区[1，]中取一个记录作为比 较的“基准”（一般取第一个、最后一个或中间位置的 元素)，用此基准将当前的无序区R[1,]划分成左右两 个无序的子区R[1,i1]和R[i,n](1sisn),且左边的无序子 区中记录的所有关键字均小于等于基准的关键字，右边 的无序子区中记录的所有关键字均大于等于基准的关键 字；当R[1,i1]和R[i,n]非空时，分别对它们重复上述的 划分过程，直到所有的无序子区中的记录均排好序为止。 9 2011/10/18 快速排序及其串行算法  快速排序（Quick Sort）是一种最基本的排序算法，它的 基本思想是：在当前无序区R[1，n]中取一个记录作为比 较的“基准”（一般取第一个、最后一个或中间位置的 元素），用此基准将当前的无序区R[1，n]划分成左右两 个无序的子区R[1，i‐1]和R[i，n](1≤i≤n)，且左边的无序子 区中记录的所有关键字均小于等于基准的关键字，右边 的无序子区中记录的所有关键字均大于等于基准的关键 字；当R[1，i‐1]和R[i，n]非空时，分别对它们重复上述的 划分过程，直到所有的无序子区中的记录均排好序为止。 9 2011/10/18 Case Study:快排序算法的并行化