实验八 概率算法_实验8概率与频率
实验八 概率算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验8概率与频率”。
实验八
概率算法（2学时）
一、实验目的与要求
熟悉快速排序算法；
通过本实验加深对概率算法的理解。
二、实验内容：
利用随机序列选取枢轴值，改进快速排序算法。
三、实验步骤
理解算法思想和问题要求； 编程实现题目要求；
上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。实验提示
void QuickSort(int r[ ], int low, int high)
{
if(low
i=Random(low, high);
r[low]←→r[i];
k=Partition(r, low, high);
QuickSort(r, low, k-1);
QuickSort(r, k+1, high);
}
}
四、实验过程 优化选取枢轴
三数取中，即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivo tkey，因此还有个办法是所谓的九数取中，先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。
public cla QuickSortRealize {
public static void QuickSort(int[] arr){ QSort(arr,0,arr.length-1);}
/*
* 对顺序表子序列作快速排序 待排序序列的最小下标值low和最大下标值high
*/
public static void QSort(int[] arr,int low,int high){ int pivot;if(low
QSort(arr, low, pivot-1);//对低子表递归排序
QSort(arr, pivot+1, high);//对高子表递归排序 } }
/*
* 选择一个关键字，想尽办法将它放到一个位置，使得它左边的值都比小，* 右边的值都比它大，我们称这个关键字叫枢轴。*/
public static int Partition(int[] arr,int low,int high){
if(arr == null || low=arr.length){ new Exception();}
int pivotkey;
ChoosePivotkey(arr,low,high);//选取枢轴值
pivotkey = arr[low];
while(low=pivotkey){ //如果大于枢轴值，则下标减一，否则，跳出循环
high--;} Swap(arr, low, high);while(low
low++;} Swap(arr, low, high);} return low;}
public static void Swap(int[] arr,int low,int high){ int temp = arr[low];arr[low] = arr[high];arr[high] = temp;}
/*
* 三数取中 选择枢轴 将枢轴值调至第一个位置 */
public static void ChoosePivotkey(int[] arr,int low,int high){ int mid = low +(int)(high-low)/2;if(arr[low]>arr[high]){ //保证左端较小
Swap(arr, low, high);} if(arr[mid]>arr[high]){ //保证中间较小
Swap(arr, mid, high);}
if(arr[mid]>arr[low]){ //保证中间较小
Swap(arr, mid, low);} }
public static void main(String[] args){ int[] arr = {50,10,90,30,70,40,80,60,20};QuickSort(arr);for(int array : arr){ System.out.print(array+“ ”);} System.out.println();} }
五、实验结果
六、心得体会
通过本次利用随机序列选取枢轴值，改进快速排序算法的实验，我熟悉快速排序算法，并加深对概率算法的理解。
