首先是几个简单排序：选择、冒泡、插入、希尔，重点关注希尔排序，这个复杂度有时间再看吧。。。
四个简单排序
/**
* 选择排序O(n^2)
*
* @param 待排序数组
*/
public static void selectionSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int min = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[min]) {
min = j;
}
}
swap(nums, i, min);
}
}
/**
* 冒泡排序O(n^2)
*
* @param 待排序数组
*/
public static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j + 1 < nums.length - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j + 1, j);
}
}
}
}
/**
* 插入排序（交换）
*
* @param 待排序数组
*/
public static void insertionSortI(int[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
swap(nums, j - 1, j);
}
}
}
/**
* 插入排序（移动)
*
* @param nums
*/
public static void insertionSortII(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int a = nums[i];
int j = i - 1;
while (j >= 0 && nums[j] > a) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = a;// 空位是J+1处
}
}
/**
* 希尔排序（递增序列1/2(3^k - 1)
*
* @param 待排序数组
*/
public static void shellSort(int[] nums) {
int N = nums.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && nums[j - h] > nums[j]; j -= h) {
swap(nums, j - h, j);
}
}
h = h / 3;
}
}
快速排序
提供三种切分方法。
public static class QuickSort {
public static void qSort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
// int m = partitionI(nums,l,r);
int m = partitionII(nums, l, r);
qSort(nums, l, m - 1);
qSort(nums, m + 1, r);
}
public static int partitionI(int[] nums, int l, int r) {
Random random = new Random();
int m = random.nextInt(r - l + 1) + l;
swap(nums, l, m);
int pivot = nums[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (nums[i] < pivot) {
swap(nums, i, j + 1);
j++;
}
}
swap(nums, l, j);
return j;
}
public static int partitionII(int[] nums, int l, int r) {
Random random = new Random();
int m = random.nextInt(r - l + 1) + l;
swap(nums, l, m);
int pivot = nums[l];
int i = l + 1;
int j = r;
while (true) {
while (i <= r && nums[i] < pivot)
i++;
while (j >= l + 1 && nums[j] > pivot)
j--;
if (i >= j) {
break;
}
swap(nums, i, j);
i++;
j--;
}
swap(nums, l, j);
return j;
}
public static void qSortThreeWays(int[] nums, int l, int r) {
if (l >= r) {
return;
}
Random random = new Random();
int m = random.nextInt(r - l + 1) + l;
swap(nums, l, m);
int pivot = nums[l];
int lt = l;// [l+1....lt]
int gt = r + 1;// [gt....r]
int j = l + 1;
while (j < gt) {
if (nums[j] < pivot) {
swap(nums, lt + 1, j);
lt++;
j++;
} else if (nums[j] == pivot) {
j++;
} else {
swap(nums, gt - 1, j);
gt--;
}
}
swap(nums, l, lt);
lt--;
qSortThreeWays(nums, l, lt);
qSortThreeWays(nums, gt, r);
}
}
归并排序
以前总是一次一次在merge函数里面去创建aux，算法第四版上直接在构造函数里面一次性分配空间，后面的下标转换就没有那么麻烦了，代码如下：
public static class MergeSort {
private static int[] aux;
private static void merge(int[] nums, int l, int mid, int r) {
int i = l;
int j = mid + 1;
for (int k = l; k <= r; k++) {
aux[k] = nums[k];
}
for (int k = l; k <= r; k++) {
if (i > mid) {
nums[k] = aux[j++];
} else if (j > r) {
nums[k] = aux[i++];
} else if (aux[j] < aux[i]) {
nums[k] = aux[j++];
} else {
nums[k] = aux[i++];
}
}
}
public static void mSort(int[] nums) {
aux = new int[nums.length];
mSort(nums, 0, nums.length - 1);
}
private static void mSort(int[] nums, int l, int r) {
if (r <= l) {
return;
}
int mid = l + (r - l) / 2;
mSort(nums, l, mid);
mSort(nums, mid + 1, r);
merge(nums, l, mid, r);
}
}
下面的是由底向上非递归
几个说明：
- sz就是分割的数组长度
- i + sz -1 就是分割的子数组的最后一个元素下标
- sz从1开始，每次扩大一倍
- 第二层循环i + sz < nums.length是确保第二段分割的数组存在
- [i,.....,i + sz -1] [i + sz,......,i + 2sz -1]， [i +2sz......
private static void mSortBottomToUp(int[] nums) {
for(int sz = 1; sz <= nums.length; sz = sz+sz) {
for(int i = 0; i+sz < nums.length; i += sz + sz) {
merge(nums, i, i+sz-1, Math.min(i+sz+sz-1, nums.length - 1));
}
}
}
堆排序
堆排序就是对传进来的数组先Heapify，这个复杂度是O（n），然后再进行堆排序。即先建堆，再排序。整个过程只涉及了shiftDown操作，这个函数要能熟练书写。
public static void heapSort(int[] nums) {
for (int i = parent(nums.length - 1); i >= 0; i--) {
shiftDown(nums, i, nums.length - 1);
}
int i = nums.length - 1;
while(i > 0) {
swap(nums, 0, i--);
shiftDown(nums, 0, i);
}
/*for(int i = nums.length - 1; i >0; i--) {
swap(nums, 0, i);
shiftDown(nums, 0, i-1);
}*/
}
public static void shiftUp(int[] nums, int index) {
while(index >= 0 && nums[index] > nums[parent(index)]) {
swap(nums, index, parent(index));
index = parent(index);
}
}
public static void shiftDown(int[] nums, int start, int end) {
while (leftChild(start) <= end) {
int j = leftChild(start);
if (j+1 <= end && nums[j] < nums[rightChild(start)]) {
j = rightChild(start);
}
if(nums[start] > nums[j]) {
break;
} else {
swap(nums, start, j);
start = j;
}
}
}
public static int parent(int index) {
return (index - 1) / 2;
}
public static int leftChild(int index) {
return index * 2 + 1;
}
public static int rightChild(int index) {
return index * 2 + 2;
}
