问题
问答题
【说明】 函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。 【函数】 void QuickSort( int A[ ],int s,int t) { int i=s,j=t+1,temp; int x=A[s]; do{do i ++ ;while (1) ;do j -- ;while(A[j]＞x);if(i＜j){temp=A[i]; (2) ; (3) ;}}while(i＜j); A[a] =A[j];A[j] =x; if(s＜i-1) (4) ; if(j+1＜t) (5) ; }
答案
参考答案：
解析：(1)A[i]＜x (2)A[i]=A[j] ＜3)A[j]=temp (4)QuickSort(A，s，j-1) (5)QuickSort(A，j+1，t)； 快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。