排序中经常用到比较和交换，所以写入一个Utils
less(n1,n2) n1>n2?true:false;
exch(a,index1,index2);交换a[index1]、a[index2]的值
github
冒泡排序
相邻两个比较，第一趟最大沉底 一般不用这个排序。
class BubbleSort {
public int[] sort(int[] a) {
int tag;
for (int j = 0; j < a.length; j++) {
for (int i = 1; i < a.length - j; i++) {
if (a[i] < a[i - 1]) {
tag = a[i - 1];
a[i - 1] = a[i];
a[i] = tag;
}
}
}
return a;
}
}
快速排序
选择基数为base，小于base的数放在左边，大于base的数放在右边。
平均复杂度 O(nlog2n)
class QuickSort {
public int[] sort(int[] a, int l, int h) {
if (l >= h)
return a;
int j = partition(a, l, h);
sort(a, l, j - 1);
sort(a, j + 1, h);
return a;
}
private int partition(int[] a, int l, int h) {
int base = a[l];
int i = l;
int j = h + 1;
while (true) {
while (a[++i] < base) {
if (i == h)
break;
}
while (a[--j] > base) {
if (j == l)
break;
}
if (i >= j)
break;
SortUtils.exch(a, i, j);// 交换大于/小于base的值
}
SortUtils.exch(a, l, j); // 将base = a[j] 即切分值一直留在a[j]中
return j;
}
}
即 a[j]已排定 a[l..j-1]都不大于a[j] a[j+1..h]都不小于a[j]。
快速排序优化
1.定义M：5~15，小分组时采取插入排序
2.大量重复数据时，可以采用熵最优：根据重复数据（大于、小于、等于基准数据）分组
简单选择排序
遍历整个序列，将最小的数放在最前面。遍历剩下的序列，将最小的数放至当前序列最前面。
class SimpleSelectionSort {
public int[] sort(int[] a) {
for (int i = 0; i < a.length; i++) {
int temp = a[i];
int index = i;
for (int j = i; j < a.length; j++) {
if (a[j] < temp) {
temp = a[j];
index = j;
}
}
if (index != i) {
a[index] = a[i];
a[i] = temp;
}
}
return a;
}
}
归并排序
将两个顺序序列合并成一个顺序序列的方法:一个无序序列分成两部分（每部分继续递归），合并
class MergeSort {
public int[] sort(int[] a) {
doMerge(a, 0, a.length - 1);
return a;
}
private void doMerge(int[] a, int s1, int end) {
if (s1 < end) {
int mid = (s1 + end) / 2;
doMerge(a, s1, mid);
doMerge(a, mid + 1, end);
mergeArray(a, s1, mid, end);
}
}
private void mergeArray(int[] a, int s1, int s2, int end) {
int[] temp = new int[end - s1 + 1];
int s = s1, mid = s2;
int n = s2 + 1;
int k = 0;
// 合并a[s .. m] a[n..e] 至temp中
while (s <= mid && n <= end) {
if (a[s] < a[n])
temp[k++] = a[s++];
else
temp[k++] = a[n++];
}
while (s <= mid) {
temp[k++] = a[s++];
}
while (n <= end)
temp[k++] = a[n++];
for (int i = 0; i < k; i++) {
a[s1 + i] = temp[i];// 注意是起始位置哦
}
}
}
堆排序：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
class HeapSort {
public int[] sort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {// 执行n-1次大顶堆排序
bigHeap(a, a.length - 1 - i);
a = SortUtils.exch(a, 0, a.length - 1 - i);
}
return a;
}
void bigHeap(int[] a, int n) {// 建造大顶堆
for (int i = n; (i - 1) >= 0; i--) {
if (a[(i - 1) / 2] < a[i]) {
SortUtils.exch(a, i, (i - 1) / 2);
}
}
}
}
直接插入排序
少量数据可以，中等数量集可以采用希尔排序
class DirectInsertSort {
static public int[] sortResult(int[] a) {
if (a.length <= 1) {
return a;
}
if (a[0] > a[1]) {
int temp = a[0];
a[0] = a[1];
a[1] = temp;
}
for (int i = 2; i < a.length; i++) {
for (int j = i; j > 0; j--) {
if (a[j] < a[j - 1]) {
int t = a[j - 1];
a[j - 1] = a[j];
a[j] = t;
}
}
}
return a;
}
}
希尔排序(缩小增量排序)
1.确定增量序列 2.根据增量形成的子数组排序
class ShellSort {
static public int[] sort(int[] a) {
if (a.length <= 1) {
return a;
}
int n = a.length;
int h = 1;
while (h < n)
h = h * 3 + 1;
while (h >= 1) {
// h = ... 40,13,4,1 分别根据增量进行排序，最后的1增量排序，为最后一次调整
for (int i = h; i < n; i++) {
// n-h+1个分组进行排序
for (int j = i; j >= h && SortUtils.less(a[j], a[j - h]); j -= h) {
// 对j, j-2h, j-3h ... 排序
SortUtils.exch(a, j, j - h);
}
}
h = h / 3;
}
return a;
}
}
