快速排序算法

快速排序算法

原理

1. 先从数组中取出一个数作为基准i
2. 以i为参照，比i大的数据放在左边，比i小的数据放在右边
3. 依次类推，把第2步划分出来的两个区域，内部再以此方法递归，最终获取排序
4. 时间复杂度实际为n + nlogn ，由于n >= 2时，nlogn > =n ,因此取为 O(n*logn) logn取值公示： n = 2^m ====>> m = logn

实现

package com.liuj.art;

/**
 */
public class Quick {


	public static void main(String[] args) {
		int[] arr = new int[]{3, 4, 1, 21, 10, 6, 0};
		int[] arr2 = new int[]{21, 10, 6, 4, 3, 1, 0};
		int[] arr3 = new int[]{0, 1, 3, 4, 6, 10, 21};
		sort(arr, 0, arr.length - 1);
		printlnArr(arr);
	}

	/**
	 * 从小到大排序
	 *
	 * @param arr
	 */
	public static void sort(int[] arr, int left, int right) {
		if (left < right) {
			int findx = arr[left];
			int i = left;
			int j = right;
			while (i < j) {
				System.out.println("new");

				//从右向左找到第一个比findx小的元素
				while (i < j && findx <= arr[j]) {
					j--;

				}

				//如果没有找到比findx小的元素，则j--会一直减少，最终变为与i相同
				//将j的值覆盖i的值
				if (i < j) {
					arr[i] = arr[j];
					printlnArr(arr);
					i++;
				}

				while (i < j && findx > arr[i]) {
					//从左向右找第一个比findx大的节点
					//移动到右边
					i++;
				}

				//如果没有找到比findx大的元素，i++会一直增加，直到与j相同
				if (i < j) {
					arr[j] = arr[i];
//                    swap(arr, i, j);
					printlnArr(arr);
					j--;
				}
			}

			System.out.println("out while i:" + i + " findx:" + findx);
			arr[i] = findx;
			printlnArr(arr);
			System.out.println("a lun hui ,left:" + left + " i:" + i + " right:" + right);

			sort(arr, left, i - 1);
			sort(arr, i + 1, right);
		}
	}

	private static void swap(int[] arr, int i, int j) {
		int t = arr[j];
		arr[j] = arr[i];
		arr[i] = t;
		printlnArr(arr);
	}

	public static void printlnArr(int[] arr) {
		String str = "";
		for (int i : arr) {
			str += i + " ";
		}
		System.out.println(str);
	}
}

代码结果

new
0 4 1 21 10 6 0 
0 4 1 21 10 6 4 
new
0 1 1 21 10 6 4 
out while i:2 findx:3
0 1 3 21 10 6 4 
a lun hui ,left:0 i:2 right:6
new
out while i:0 findx:0
0 1 3 21 10 6 4 
a lun hui ,left:0 i:0 right:1
new
0 1 3 4 10 6 4 
out while i:6 findx:21
0 1 3 4 10 6 21 
a lun hui ,left:3 i:6 right:6
new
out while i:3 findx:4
0 1 3 4 10 6 21 
a lun hui ,left:3 i:3 right:5
new
0 1 3 4 6 6 21 
out while i:5 findx:10
0 1 3 4 6 10 21 
a lun hui ,left:4 i:5 right:5
0 1 3 4 6 10 21