排序（二）

快速排序：

 // 以最后一个元素为比较对象 左边是小于它的元素 右边是大于它的元素
	public static int[] partition(int[] arr, int l, int r) {
		int less = l - 1;
		int more = r;
		int cur = l;
		while (cur < more) {
			if (arr[cur] < arr[r]) {
				swap(arr, cur++, ++less);
			} else if (arr[cur] > arr[r]) {
				swap(arr, --more, cur);
			} else {
				cur++;
			}
		}
		swap(arr, more, r);// 将数组的最后一个元素放到它应在的位置
		return new int[] { less + 1, more };
	}


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


	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			//随机快速排序
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
			// 经典快速排序
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
	}

时间复杂度：O(n*log(n))    空间复杂度：O(log(n))，不稳定排序(01 stable sort除外)

堆排序：

public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			heapInsert(arr, i);
		}
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
	}

	
	public static void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	public static void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;
		while (left < size) {
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
			largest = arr[largest] > arr[index] ? largest : index;
			if (largest == index) {
				break;
			}
			swap(arr, largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}

时间复杂度：O(n*log(n))    空间复杂度：O(1)，不稳定排序，重点：堆结构的heapInsert与heapify，堆结构的增大和减少，如果只是建立堆的过程，时间复杂度为O(N)，优先级队列结构，就是堆结构。

桶排序(计数排序)：

public static void bucketSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		int[] bucket = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]]++;
		}
		int i = 0;
		for (int j = 0; j < bucket.length; j++) {
			while (bucket[j]-- > 0) {
				arr[i++] = j;
			}
		}
	}

特点：

1. 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
2. 时间复杂度O(N)，额外空间复杂度O(N)
3. 稳定的排序

工程中的综合排序算法：

数组中是基础类型：快排（基础类型不要求稳定性）

自定义类型：归并排序

若数组很短（长度小于60）：插入排序（常数项极低）