目录
快速排序原理
快速排序API设计
快速排序代码实现
归并排序的时间复杂度分析
快速排序是对冒泡排序的一种改进。
快速排序原理
1.首先设定一个分界值,通过该分界值将数组分成左右两部分﹔
2.将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值;
3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了。
切分原理
把一个数组切分成两个子数组的基本思想︰
1.找一个基准值,用两个指针分别指向数组的头部和尾部;
2.先从尾部向头部开始搜索一个比基准值小的元素,搜索到即停止,并记录指针的位置;
3.再从头部向尾部开始搜索一个比基准值大的元素,搜索到即停止,开记录指针的位置;
4.交换当前左边指针位置和右边指针位置的元素﹔
5.重复2,3,4步骤,直到左边指针的值大于右边指针的值停止
快速排序API设计
快速排序代码实现
public class Quick { public static void sort(Comparable[] a) { int low = 0; int high = a.length - 1; sort(a, low, high); } private static void sort(Comparable[] a, int low, int high) { if (high < low) { return; } //对a数组中,从low到high的元素进行切分 int partition = partition(a, low, high); //对左边分组中的元素进行排序 sort(a,low,partition-1); //对右边分组中的元素进行排序 sort(a,partition+1,high); } private static int partition(Comparable[] a, int low, int high) { Comparable key = a[low]; int left = low; int right = high + 1; //进行切分 while (true) { //先从右边往左边扫描,找到一个比基准值小的元素 while (less(key, a[--right])) { if (right == low) { break; } } //再从左往右扫描,找一个比基准值大的元素 while (less(a[++left], key)) { if (left == high) { break; } } if (left >= right) { break; } else { exchange(a, left, right); } } exchange(a,low,right); return right; } //比较v元素是否小于w元素 private static boolean less(Comparable v,Comparable w){ return v.compareTo(w)<0; } //数组元素i和j交换位置 private static void exchange(Comparable[] a,int i,int j){ Comparable t=a[i]; a[i]=a[j]; a[j]=t; } } //测试代码 class Test{ public static void main(String[] args) { Integer[] a={8,4,6,5,7,1,3,6,2}; Quick.sort(a); System.out.println(Arrays.toString(a)); } }
快速排序和归并排序的区别
快速排序是另外一种分治的排序算法,它将一个数组分成两个子数组,将两部分独立的排序。快速排序和归并排序是互补的︰归并排序将数组分成两个子数组分别排序,并将有序的子数组归并从而将整个数组排序,而快速排序的方式则是当两个数组都有序时,整个数组自然就有序了。在归并排序中,一个数组被等分为两半,归并调用发生在处理整个数组之前,在快速排序中,切分数组的位置取决于数组的内容,递归调用发生在处理整个数组之后。
归并排序的时间复杂度分析
最优情况O(nlogn)
最坏情况O(n^2)
平均情况O(logn)
第二种写法: