快速排序算法,排序算法(一)——快速排序

on 2011-4-7 in 博文摘选 | 0 Comment
基本快速排序算法
算法原理：
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法过程：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：
1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束)
程序实现：
/**
* 基本快速排序算法
* @param values 被排序的数组
* @param s 起始索引
* @param e 结束索引
*/
public static void quickSort(int[] values,int s,int e)
{
int i=s,j=e;
int length=values.length;
int key=0;
if(i>=j)
return;
if(length>0)
{
key=values[i];
}
while(i {
while(ikey)
j--;
while(i i++;
values=switchItem(values,j,i);
}
quickSort(values,s, i-1);
quickSort(values,j+1, e);
}
public static int[] switchItem(int[] values,int a,int b)
{
int temp=0;
temp=values[a];
values[a]=values[b];
values[b]=temp;
return values;
}
随机快速排序
算法原理：
快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
程序实现：
/**
* 随机快速排序算法实现
* @param values 被排序算法
* @param s 开始索引
* @param e 结束索引
*/
public static void random_Quick_Sort(int[] values,int s,int e)
{
int i=s,j=e;
int length=values.length;
int key=0;
int randIndex=-1;
if(i>=j||length<1)
{
return;
}
randIndex=new Random().nextInt(length);
key=values[randIndex];
while(i {
while(ikey)
j--;
while(i i++;
values=switchItem(values,j,i);
}
random_Quick_Sort(values,s, i-1);
random_Quick_Sort(values,j+1, e);
}
平衡排序算法：
算法原理：
每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说，选择这个数据的方法是取开头、结尾、中间 3个数据，通过比较选出其中的中值。取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微打乱，破坏退化的结构。
程序实现：
/**
* 平衡排序算法实现
* @param values 被排序的数组
* @param s 起始索引
* @param e 结束索引
*/
public static void blanced_QuickSort(int[] values,int s,int e)
{
int i=s,j=e;
int length=values.length;
int key=0;
int midIndex=-1;
if(i>=j||length<1)
{
return;
}
midIndex=(i+j)/2;
key=getMidValue(values[i],values[midIndex],values[j]);
while(i {
while(ikey)
j--;
while(i i++;
values=switchItem(values,j,i);
}
blanced_QuickSort(values,s, i-1);
blanced_QuickSort(values,j+1, e);
}
public static int getMidValue(int a,int b,int c)
{
if(a>=b&&a<=c)
return a;
else if(b>=a&&b<=c)
return b;
else return c;
}
算法测试：
public static void main(String[] arg)
{
long testTime=0;
int[] values={12,36,24,89,10,8,96,45};
System.out.print("base quick sort original array: ");
printArray(values);
testTime=System.nanoTime();
quickSort(values,0,7);
testTime=System.currentTimeMillis()-testTime;
System.out.print("base quick sort result array: ");
printArray(values);
System.out.println("the base quick sort west time : "+testTime);
System.out.println();
int[] values2={12,36,24,89,10,8,96,45};
System.out.print("random quick sort original array: ");
printArray(values2);
testTime=System.nanoTime();
random_Quick_Sort(values2,0,7);
testTime=System.nanoTime()-testTime;
System.out.print("random quick sort result array: ");
printArray(values2);
System.out.println("the random quick sort west time : "+testTime);
System.out.println();
int[] values3={12,36,24,89,10,8,96,45};
System.out.print("blanced quick sort original array: ");
printArray(values3);
testTime=System.nanoTime();
blanced_QuickSort(values3,0,7);
testTime=System.nanoTime()-testTime;
System.out.print("blanced quick sort result array: ");
printArray(values3);
System.out.println("the blanced quick sort west time :"+testTime);
System.out.println();
}
Tags:  快速排序 快速排序算法代码 快速排序算法分析 快速排序算法c 快速排序算法

延伸阅读

最新评论

发表评论