随机化极快排序的分治实现(java)

一，为什么要进行随机化快速排序？

快速排序的时间复杂度为：
最好的情况：O(nlogn)

最坏的情况：O()

由此我们可知，时间复杂度会因为固定主元的选取和次序的不一致而发生变化，如何摆脱输入导致最坏情况。

数组划分时选取固定位置主元，可以针对性构造最差情况。

数组划分时选取随机位置主元，无法针对性构造最差情况。

二，了解分治思想在快速排序中的实现

1，归并排序：重在合并，合并子问题

2，快速排序：侧重分解，简化合并

3，由此可见，分治思想在快速排序中的重点就是数组划分

 三，数组划分伪代码

 四，快速排序伪代码

 五，代码编译

1，代码框架

1.  
   import java.util.Arrays;
2.  
    
3.  
   public class QuickSort {
4.  
   public void ToQuickSort(int[] arr,int p,int q){
5.  
    
6.  
   }
7.  
   public int Partition(int[] arr,int p,int r){
8.  
    
9.  
   }
10.  
    public static void main(String[] args) {
11.  
    QuickSort quicksort=new QuickSort();
12.  
    int[] arr={2,1,3,4,7,5,6,6};
13.  
    System.out.println(Arrays.toString(arr));
14.  
    quicksort.ToQuickSort(arr,0,arr.length-1);
15.  
    System.out.println(Arrays.toString(arr));
16.  
    }
17.  
    }

2，如何生成随机数

在Java语言中生成随机数相对来说比较简单，因为有一个现成的方法可以使用。在Math类中，Java语言提供了一个叫做random的方法。通过这个方法可以让系统产生随机数。不过默认情况下，其产生的随机数范围比较小，为大于等于0到小于1的double型随机数。虽然其随机数产生的范围比较小，不能够满足日常的需求。如日常工作中可能需要产生整数的随机数。其实，只要对这个方法进行一些灵活的处理，就可以获取任意范围的随机数。
　　如我们可以先通过random方法生成一个随机数，然后将结果乘以10。此时产生的随机数字即为大于等于0小于10的数字。然后再利用Int方法进行转换(它会去掉小数掉后面的数字，即只获取整数部分，不是四舍五入)。最后即可获取一个0到9的整数型随机数字。其实现方法很简单，就是对原有的random方法按照如下的格式进行变型：(int)(Math.Random()*10)即可。其实我们还可以对这个方法进行扩展，让其产生任意范围内的随机数。至需要将这个10换成n即可，如改为(int)(Math.Random()*n)。此时应用程序就会产生一个大于等于0小与n之间的随机数。如将n设置为5，那么其就会产生一个0到5之间的整数型的随机数。如果将这个写成一个带参数的方法，那么只要用户输入需要生成随机数的最大值，就可以让这个方法来生成制定范围的随机数。注：这里random的取值范围始终是[0,n)，如果要生成负随机数，就0-(int)(Math.Random()*n)，这样就生成(-n,0]的随机数了。

3，一次数组划分后的步骤

再根据伪代码进行分治求解就出来了。

 4，完整代码

1.  
   import java.util.Arrays;
2.  
   public class QuickSort {
3.  
   public void ToQuickSort(int[] arr,int p,int r){
4.  
   if(p<r){
5.  
   int q=Partition(arr,p,r);
6.  
   ToQuickSort(arr,p,q-1);
7.  
   ToQuickSort(arr,q 1,r);
8.  
   }//递归入口(p<r)和出口
9.  
   }
10.  
    public int Partition(int[] arr,int p,int r){
11.  
    //取一个范围在[0,r-p 1)的随机数，本题中范围为[0,8)，然后递归求解
12.  
    int RandomLocation=p (int)(Math.random()*(r-p 1));
13.  
    //把随机主元放在数组末尾
14.  
    int temp=arr[RandomLocation];
15.  
    arr[RandomLocation]=arr[r];
16.  
    arr[r]=temp;
17.  
    int x=arr[r];
18.  
    //数组中的元素和主元比较
19.  
    int i=p-1;//i代表较小元素的集合坐标，j代表较大元素的集合坐标
20.  
    for(int j=p;j<=r-1;j ){
21.  
    if(arr[j]<=x){
22.  
    int temp1=arr[i 1];
23.  
    arr[i 1]=arr[j];
24.  
    arr[j]=temp1;
25.  
    i=i 1;/*!第一次编译出现错误的地方，i没有向后递加!*/
26.  
    }
27.  
    }
28.  
    //把主元放在适当位置
29.  
    int temp2=arr[i 1];
30.  
    arr[i 1]=arr[r];
31.  
    arr[r]=temp2;
32.  
    return i 1;//返回划分位置
33.  
    }
34.  
    public static void main(String[] args) {
35.  
    QuickSort quicksort=new QuickSort();
36.  
    int[] arr={2,1,3,4,7,5,6,6};
37.  
    System.out.println(Arrays.toString(arr));
38.  
    quicksort.ToQuickSort(arr,0,arr.length-1);
39.  
    System.out.println(Arrays.toString(arr));
40.  
    }
41.  
    }

 5，出现问题

主要集中在划分位置函数Partition

1.  
   public int Partition(int[] arr,int p,int r){
2.  
   //取一个范围在[0,r-p 1)的随机数，本题中范围为[0,8)，然后递归求解
3.  
   int RandomLocation=p (int)(Math.random()*(r-p 1));
4.  
   //把随机主元放在数组末尾
5.  
   int temp=arr[RandomLocation];
6.  
   arr[RandomLocation]=arr[r];
7.  
   arr[r]=temp;
8.  
   int x=arr[r];
9.  
   //数组中的元素和主元比较
10.  
    int i=p-1;//i代表较小元素的集合坐标，j代表较大元素的集合坐标
11.  
    for(int j=p;j<=r-1;j ){
12.  
    if(arr[j]<=x){
13.  
    int temp1=arr[i 1];
14.  
    arr[i 1]=arr[j];
15.  
    arr[j]=temp1;
16.  
    i=i 1;/*!第一次编译出现错误的地方，i没有向后递加!*/
17.  
    }
18.  
    }
19.  
    //把主元放在适当位置
20.  
    int temp2=arr[i 1];
21.  
    arr[i 1]=arr[r];
22.  
    arr[r]=temp2;
23.  
    return i 1;//返回划分位置
24.  
    }

int RandomLocation=p (int)(Math.random()*(r-p 1));

 这里给随机位置加上p，p是数组的首元素，对数组划分后数组一分为二，如果不加p，对前一个数组没啥影响，但是后一个数组的首元素的位置就没法计算了，因此加上这个p的同时，用r-p 1来计算数组的长度，这样后一个数组的随机位置划分也就可以计算了。

---

int temp=arr[RandomLocation];
arr[RandomLocation]=arr[r];
arr[r]=temp;
int x=arr[r];

 这里将随机主元放在数组末尾，也就是默认以末尾为固定主元的方式来快排，随机主元的设定只是对划分位置进行随机，快排方式不变。

数组结束排列后，还要将随机主元放回合适的位置，然后进行下一次递归。

---

for(int j=p;j<=r-1;j  ){
    if(arr[j]<=x){
        int temp1=arr[i 1];
        arr[i 1]=arr[j];
        arr[j]=temp1;
        i=i 1;/*!第一次编译出现错误的地方，i没有向后递加!*/
    }
}

 i和j要根据情况进行变化。

这篇好文章是转载于：学新通技术网