软件测试修炼之路 A Tester

快速排序

2016-05-30
Dex

算法概念

快速排序(Quicksort)是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

时间复杂度:平均为O(nlogn),最差为O(n^2)

算法代码(Java)

package algorithm;

public class QuickSort {
	public void QuickSort(int[] arr, int low, int high) {
		int l = low;
		int h = high;
		int povit = arr[low];
		
		while(l < h) {
			while(l < h && arr[h] >= povit)
				h--;
			if(l < h) {
				int temp = arr[h];
				arr[h] = arr[l];
				arr[l] = temp;
				l++;
			}
			
			while(l < h && arr[l] < povit)
				l++;
			if(l < h) {
				int temp = arr[h];
				arr[h] = arr[l];
				arr[l] = temp;
				h--;
			}
		}
		
		if(l > low) {
			QuickSort(arr, low, l-1);
		}
		if(h < high) {
			QuickSort(arr, l+1, high);
		}
	}
	
	public static void main(String[] args) {
		int[] x = {6, 2, 4, 1, 5, 9};
		QuickSort sort = new QuickSort();
		sort.QuickSort(x, 0, 5);
		for(int i = 0; i < x.length; i++)
			System.out.print(x[i]);
	}

}

Similar Posts

上一篇 冒泡排序

Comments