快速排序

快速排序使用分治法策略来把一个串行分为两个子串行。

步骤为：

1. 从数列中挑出一个元素，称为“基准”（pivot）,

2。重新排列数列，小的在基准前，大的在基准后，基准位于中间，称为分区（partition）操作

3。递归排列两个分区

 

最好的情况下，每次排列分区操作将数列分为等长的两个部分，这时调用次数为O(logn);

最坏的情况下，每次选中的基准为最小数或最大数，每次排列后的两部分的长度为N-i-1和1（i为次数），则调用次数为O(N)

因为每次调用都有n次比较，时间复杂度为O(n),所以时间复杂度为 O(nlogn) ~ O(n2).

 

在递归函数调用返回之前，使用的空间是固定的，但是每一层调用都要分配一定的空间进行分界点信息的保存。

 每次调用都会有1的空间，所以空间复杂度为O(logn)~O(n)

在最坏的情况下，需要进行O(n)次的函数调用，就需要占用O(n)的空间。而在最好的情况下，需要进行O(logn)次的函数调用，那么需要占用的空间的量为O(logn)。

 

package com.longshine.arthmetic.sort;

import java.util.ArrayList;
import java.util.List;

import com.longshine.arthmetic.Util;
/**
 * 快速排序
 * @author skymr
 *
 */
public class QuickSort {

	private List<SortElement> sortList;
	
	public QuickSort(List<SortElement> sortList) {
		this.sortList = sortList;
	}
	
	public void sort() {
		sort(0, sortList.size() - 1);
	}
	
	private void sort(int left, int right) {
		if (left >= right ) 
			return; 
		int pivotIndex = left + (right - left) / 2;
		SortElement pivot = sortList.get(pivotIndex);
		int i = left;
		int j = right;
		//分区操作
		while (i < j ) {
			while (i < pivotIndex && sortList.get(i).compareTo(pivot) <= 0) {
				i ++;
			}
			Util.swap(this.sortList, i, pivotIndex);
			pivotIndex = i;
			while(pivotIndex < j && sortList.get(j).compareTo(pivot) > 0){
				j --;
			}
			Util.swap(this.sortList, j, pivotIndex);
			pivotIndex = j;
		}
		sort(left, pivotIndex - 1);
		sort(pivotIndex + 1, right);
	}
	
	public void print(){
		System.out.println(this.sortList);
	}
	
	public static void main(String[] args) {
		int[] data = new int[] {5,8,1,20,15,13,7,6,30,45,3};
		List<SortElement> lists = new ArrayList<SortElement>();
		for (int d : data) {
			lists.add(new NumSortElement(d,""));
		}
		QuickSort sort = new QuickSort(lists);
		sort.print();
		sort.sort();
		sort.print();
	}
}

 以上是我自己实现的排序，教科书上可不是这么写的

 

package com.longshine.arthmetic.sort;

import java.util.ArrayList;
import java.util.List;

import com.longshine.arthmetic.Util;

public class NormalQuickSort {

	private List<SortElement> sortList;
	
	public NormalQuickSort(List<SortElement> sortList) {
		this.sortList = sortList;
	}
	
	public void sort() {
		sort(0, sortList.size() - 1);
	}
	
	private void sort(int left, int right) {
		if (left >= right ) 
			return; 
		SortElement pivot = sortList.get(left);
		int i = left;
		int j = right;
		//分区操作
		while (i < j ) {
			while (i < j && sortList.get(j).compareTo(pivot) >= 0){
				j --;
			}
 			Util.swap(this.sortList, i, j);
			while (i < j && sortList.get(i).compareTo(pivot) <= 0) {
				i ++;
			}
			Util.swap(this.sortList, i, j);
		}
		this.print();
		sort(left, i - 1);
		sort(i + 1, right);
	}
	
	public void print(){
		System.out.println(this.sortList);
	}
	
	public static void main(String[] args) {
		int[] data = new int[] {5,8,1,20,15,13,7,6,30,45,3};
		List<SortElement> lists = new ArrayList<SortElement>();
		for (int d : data) {
			lists.add(new NumSortElement(d,""));
		}
		NormalQuickSort sort = new NormalQuickSort(lists);
		sort.print();
		sort.sort();
		sort.print();
	}
	
}

 不一样的地方是分区操作部分，但我那样的也可以将数列分成两相部分

另一样分区算法：原地分区（In-Place）

	public static int partition(int[] data, int left, int right) {
		// i为小于等于A[q]数组的最大下标
		int i = left - 1;
		int key = data[right];
		for (int j = left; j <= right; j++) {
			if (data[j] <= key) {
				i++;
				Util.swap(data, i, j);
			} 
		}
		return i;
	}

 

完整代码：

package com.longshine.arthmetic.sort;

import com.longshine.arthmetic.Util;

public class QuickSort2 {

	public static void main(String[] args) {
		int[] a = { 5, 8, 1, 20, 15, 13, 7, 6, 30, 45, 3 };
		quickSort(a, 0, a.length - 1);
		Util.printArray(a);
	}

	public static void quickSort(int[] data, int left, int right) {
		if (left < right) {
			// 进行分组
			int q = partition(data, left, right);
			// 对剩下的两组迭代分组
			if (q - 1 >= 0) {
				quickSort(data, left, q - 1);
				quickSort(data, q + 1, right);
			}
		}
	}

	/**
	 * 分区方法，将数组A[p..r]划分为两个可能为空的子数组A[p..q-1]和A[q+1..r]，
	 * 使得A[p..q-1]中的每个元素都小于等于A(q)，而且小于等于A[q+1..r]中的元素
	 * 
	 * @param a
	 *            要划分的数组
	 * @param p
	 *            开始索引
	 * @param r
	 *            结束索引
	 * @return 关键字A(q)的索引值q
	 */
	public static int partition(int[] data, int left, int right) {
		// i为小于等于A[q]数组的最大下标
		int i = left - 1;
		int key = data[right];
		for (int j = left; j <= right; j++) {
			if (data[j] <= key) {
				i++;
				Util.swap(data, i, j);
			} 
		}
		return i;
	}
}