java 概率 算法_使用概率算法优化快速排序（JAVA）

前言

前面一篇文章系统介绍了快速排序算法，提到快速排序虽然平均时间复杂度为o(n*log2(n))，效率相对比较高。但是其在特殊情况下，比如降序的情况下，效率和冒泡排序一致，这就削弱了快速排序给人的好感。然而有没有办法，能够解决这种问题，使快速排序的时间复杂度与输入序列无关呢？答案是有的，使用舍伍德概率算法能够帮助解决这个问题。

舍伍德算法

舍伍德算法是三大概率算法之一，它的实质就是通过随机概率解决问题与输入顺序的关联，从而优化问题的解决。舍伍德算法还可用于层级链表问题，后续写概率算法时会进一步提到。

优化

思路很简单，为了使排序与输入序列顺序无关，在划分基准时，我们确定一个随机基准(low到high之间的一个随机位置)，将它与第一位(默认基准)进行交换，而后再进行基准位确定，进而分治快速排序其左半部分与右半部分。

Codes

package com.fairy.InnerSort;

import java.util.Scanner;

/**

* 舍伍德算法优化快速排序

* @author Fairy2016

*

*/

public class QuickSort {

//快速排序

public static void sort(int a[], int low, int high) {

if(low < high) {

int base = Depart(a, low, high);

//对基准左半边部分进行排序

sort(a, low, base-1);

//对基准右半边部分进行排序

sort(a, base+1, high);

}

}

//基准划分

public static int Depart(int a[], int low, int high) {

//舍伍德随机确定基准

int d = (int)Math.random()*(high-low)+low;

//交换默认基准与随机基准

a[0] = a[d];

a[d] = a[low];

a[low] = a[0];

while(low < high) {

//从右向左扫描找比基准小的元素

while(low < high && a[high] >= a[0])

high--;

a[low] = a[high];//赋值，更新基准位

//从左向右扫描找比基准大的元素

while(low < high && a[low] <= a[0])

low++;

a[high] = a[low];//赋值，更新基准位

}

//基准位最终位置已确定，是low或者high

a[high] = a[0];

return high;

}

public static void Print(int a[], int n) {

for(int i = 1; i <= n; i++) {

System.out.print(a[i]+" ");

}

}

public static void main(String args[]) {

int n;

int a[];

Scanner scanner = new Scanner(System.in);

while(scanner.hasNext()) {

n = scanner.nextInt();

if(n > 0) {

a = new int[n+1];

for(int i=1; i <= n; i++) {

a[i] = scanner.nextInt();

}

sort(a, 1, n);

Print(a, n);

}

}

scanner.close();

}

}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！