排序算法Java版-快速排序算法

• 快速排序原理就是荷兰国旗问题原理，java实现如下，注意每次选定中间值需要使用随机来取，如果选取开头或者结尾的数容易遇到最坏的情况，最坏的情况的复杂度为O（n2），当使用随机方式取的时候，复杂度为O(nlogn）

package sort;

import java.util.Arrays;

public class QuichSort {
public static void quichSort(int[] arr,int left,int right)
{
if(arr==null || arr.length<2 || left==right)
{
return;
}
int val=arr[left+(int)((right-left+1)*Math.random())];
int leftUpper=left-1;
int rightDown=right+1;
int i=left;
while(i<rightDown)
{
if(arr[i]<val)
{
leftUpper++;
if (i!=leftUpper)
{
swap(arr,i,leftUpper);
}
i++;
}
else if(arr[i]>val)
{
rightDown--;
swap(arr,i,rightDown);
}
else
{
i++;
}
}
if(left<leftUpper)
{
quichSort(arr, left, leftUpper);
}
if(rightDown<right)
{
quichSort(arr,rightDown,right);
}

}
public static void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void printArray(int[] arr)
{
for(int elem:arr)
{
System.out.print(elem+"\t");
}
System.out.println();
}

public static int[] generateRandomArray(int maxSize,int maxValue)
{
int[] arr=new int[(int)((maxSize+1)*Math.random())];
for(int i=0;i<arr.length;i++)
{
arr[i]=(int)((maxValue+1)*Math.random()-(int)(maxValue*Math.random()));
}
return arr;
}

public static int[] copyArray(int[] arr)
{
int[] arr2=new int[arr.length];
for(int i=0;i<arr.length;i++)
{
arr2[i]=arr[i];
}
return arr2;
}
public static boolean arrayIsEqual(int[] arr1,int[] arr2)
{
if(arr1.length != arr2.length)
{
return false;
}
else
{
for(int i=0;i<arr1.length;i++)
{
if (arr1[i]!=arr2[i])
{
printArray(arr1);
printArray(arr2);
return false;
}
}
return true;
}
}

public static void main(String[] args) {
int testTime=1000000;
int maxSize=100;
int maxValue=100;
boolean succeed=true;
for(int i=0;i<testTime;i++)
{
int[] arr1=generateRandomArray(maxSize,maxValue);
int[] arr2=copyArray(arr1);
quichSort(arr1,0,arr1.length-1);
Arrays.sort(arr2);
if(!arrayIsEqual(arr1,arr2))
{
succeed=false;
break;
}
}
System.out.println(succeed?"Nice":"Failed!");
int[] arr=generateRandomArray(maxSize,maxValue);
printArray(arr);
quichSort(arr,0,arr.length-1);
printArray(arr);
}
}

执行结果如下：同样，这里使用了随机100万个随机长度的随机数组进行了验证，OK

Nice
-18 -57 8 29 22 -38 27 45 51 -31 92 -70 -18 -16 2 58 -4 86 3 50 9 24 29 -59 27 28 -37 -29 1 -1 -21 -18 3 -3 -50 53 -66 40 32 65 -52 26 33 18 43 -30 -5 12 -18 -12 62 -23 -11 -76 -8 -12 16 27 -38 -24 -6 3 44 9 51 -72 -3 0 -22 -41 -67 12 -60 22 -68 -6 -29 -81
-81 -76 -72 -70 -68 -67 -66 -60 -59 -57 -52 -50 -41 -38 -38 -37 -31 -30 -29 -29 -24 -23 -22 -21 -18 -18 -18 -18 -16 -12 -12 -11 -8 -6 -6 -5 -4 -3 -3 -1 0 1 2 3 3 3 8 9 9 12 12 16 18 22 22 24 26 27 27 27 28 29 29 32 33 40 43 44 45 50 51 51 53 58 62 65 86 92