主观题：关于分而治之算法相关概念及应用

分而治之策略可以用来设计有效的计算机算法，利用分治思想设计的快速排序算法是二十世纪最伟大的十大算法之一。请回答以下问题：
（1）请简述快速排序的算法思想。（3分）
（2）快速排序的最好，最坏和平均时间复杂度分别各为多少？（3分）
（3）对于[8 1 4 9 0 3 5 2 7 6]这一组数，选择6为支点（划分元素），按照从两头往中间的方式扫描，进行一趟快速排序后的结果是什么？（3分）
（4）请再写出3个可以用分治法解决的问题。（6分）






answer：评分标准：
（1）把n个元素划分为3段：左端left、中间段middle和右段right。左端的元素都不大于中间段的元素，右段的元素都不小于中间段的元素。因此可以对left和right独立排序，并且排序后不用归并。Middle元素称为支点(pivot)或分割元素。（3分）
（2）最好和平均时间复杂度为O（nlogn），最坏的时间复杂度为O（n^2）。（3分）
（3）6为主元，一趟快速排序后的结果是[2 1 4 5 0 3 6 8 7 9]。（3分）
（4）归并排序、找假币问题、金块问题、矩阵乘法、残缺棋盘等。（写一个得2分，最多6分）