快速排序
分治递归的应用,平均时间 O(nlogn), 最坏时间 O(n^2).
选取一个分界点,小于分界点的元素放在左边,大于等于分界点的元素放在右边,再分别对左右两边进行递归,递归终止条件是start >= end.
分界点的选取:
最简单的就是选取第一个元素。
public class QuickSort { private static void quickSort(int[] array, int start,int end){ //递归终止条件 if(start >= end) return;//选取第一个元素作为分界点 int key = array[start]; int i = start; for(int j = start+1; j<=end; j++){ //碰见比key小的元素,就把i往后移一位,再交换i和j位置的元素 //这样保证i及其左边放的都是小于key的元素 if(array[j]<key){ i++; int temp=array[i]; array[i]=array[j]; array[j]=temp; } } //把key放在i位置的元素交换,最终完成分割 array[start]=array[i]; array[i]=key; //分割后就对左右两边递归排序 quickSort(array, start, i-1); quickSort(array, i+1, end); } //testpublic static void main(String[] args) {int[] c = { 4,4,0,3,5};quickSort(c, 0, c.length-1);for (int i = 0; i < c.length; i++) {System.out.print(c[i] + " ");}}}
天不负;卧薪尝胆,三千越甲可吞吴。