TOC
排序算法
排序是将一组数据按照某种逻辑重新排列的过程。相对比较常用,在考虑排序算法时,我们往往要考虑以下几个方面:
注意点:
import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
public class SortExample {
public static void sort(Comparable[] a) {
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
/**
* 测试元素是否有序
*
* @param a
*/
public static boolean isSorted(Comparable[] a) {
if (a == null || a.length == 1) {
return true;
}
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
/**
* 判断两个对象的大小
*
* @param v
* @param w
* @return
*/
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
/**
* 交换数组中的两个对象
*
* @param a
* @param i
* @param j
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
public static void main(String[] args) {
//此时为需要用线程安全的随机数生成器
int N = ThreadLocalRandom.current().nextInt(10, 10000);
Integer a[] = new Integer[N];
for (int i = 0; i < N; i++) {
a[i] = Integer.valueOf(ThreadLocalRandom.current().nextInt(1000000));
}
System.out.println("Array size: "+N+", Array isSorted: "+isSorted(a));
Arrays.sort(a);
System.out.println("Array size: "+N+", Array isSorted: "+isSorted(a));
}
}
[startPos,curPos,endPos)
[startPos,curPos) 是已排好序的列表,[curPos,endPos)是待排序的列表,依次从待排序的列表中选择最小的放到已排好序的列表中。
private static void selection(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int minIdx = i;
for (int j = i; j < N; j++) {
if (less(a[j], a[minIdx])) {
minIdx = j;
}
}
exch(a, i, minIdx);
}
}
[startPos,curPos,endPos)
[startPos,curPos) 是已排好序的列表,[curPos,endPos)是待排序的列表,依次从待排序的列表中取出的元素x的插入已排好序的列表seq中。
在seq从后往前在比较,判断是否在当前位置插入的时候,要同时兼顾移动元素。因为当前取出的元素x一定要插入到有序表seq中的,如果当前位置不比x小,那当前位置的元素往后移动一位,x则继续与再前的元素比较。
类比每学期的第一次体育课排除时,先跟前面靠近你的比,如果前面靠近你的比你高,那你们交换一上位置,然后你再跟前面的比
/**
* 插入排序
* @param a
*/
private static void insertion(Comparable[] a) {
int N = a.length;
for (int i = 1; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
[startPos,curPos,endPos)
[startPos,curPos) 是待排序的列表,[curPos,endPos)是已排好序的列表,依次从待排序的列表中取出的元素x的放到已排好序的列表seq首部。
类比班主任抽考去乡里参加比赛,每次从剩余的中挑出一个最好的
/**
* 冒泡排序
*/
private static void bubbleSort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N - 1 - i; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
插入排序的改进,虽然说是改进,但相比插入排序有优有劣:
分组: 将i,i+h,i+2_h,i+3h...,i+k_h 分成一组,组内使用插入排序,当递减到1的时候,就是插入排序
算法性能取决于h,还取决于h之间的数学性质,比如它们的公因子等。 下列算法使用了递增(减)序列 1/2({3}^{k}-1) ,从N/3开始减至1。关于递增(减)序列(这里翻译有点问题,可以看英文原版),目前无法证明哪个递增(减)序列是最好的 Property. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is bounded by a small multiple of N times the number of increments used. Proposition. The number of compares used by shellsort with the increments 1, 4, 13, 40, 121, 364, ... is O(N3/2). algorithm4th
private static void shell(Comparable[] a) {
int N = a.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 && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
归并排序
分自下向上的归并排序和自上向上的归并排序,二者时间和空间复杂度一样,只是自下向上的归并排序同时适用于数组和链表这两种方式存储线性表,面自上向下的归并排序只适用于数组这种方式存储的线性表。
同时归并排序有一种优化,当组内元素个数小于7时(这个是经验值),使用插入排序对组内元素进行排序。
import java.util.concurrent.ThreadLocalRandom;
public class Merge {
private Merge() {
}
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
/**
* 自顶向下
* @param a
* @param aux
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
/**
* 测试元素是否有序
*
* @param a
* @param lo
* @param hi
* @return
*/
public static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
/**
* 判断两个对象的大小
*
* @param v
* @param w
* @return
*/
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
/**
* 交换数组中的两个对象
*
* @param a
* @param i
* @param j
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
}
public static void main(String[] args) {
//此时为需要用线程安全的随机数生成器
int N = 100;
Integer a[] = new Integer[N];
for (int i = 0; i < N; i++) {
a[i] = Integer.valueOf(ThreadLocalRandom.current().nextInt(1000));
}
System.out.println("Array size: " + N + ", Array isSorted: " + isSorted(a, 0, a.length - 1));
sort(a);
System.out.println("Array size: " + N + ", Array isSorted: " + isSorted(a, 0, a.length - 1));
}
}
public class Merge {
//...
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
/**
* 自顶向下
* @param a
* @param aux
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
//...
}
public class MergeBU {
//...
/**
* 自下向上
*
* @param a
*/
public static void sort(Comparable[] a) {
int n = a.length;
Comparable[] aux = new Comparable[n];
for (int step = 1; step < n; step +=step) {
for (int lo = 0; lo < n - step; lo += step + step) {
int mid = lo + step - 1;
int hi = Math.min(lo + step + step - 1, n - 1);
merge(a, aux, lo, mid, hi);
}
}
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
//...
}
当分组内的元素个数小于7时,使用插入排序或者冒泡排序进行优化
public class Merge {
private static final int CUTOFF = 7;
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
/**
* 自顶向下
* @param a
* @param aux
* @param lo
* @param hi
*/
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo + CUTOFF) {
insertionSort(a, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
if (!less(a[mid + 1], a[mid])) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
} else {
merge(a, aux, lo, mid, hi);
}
}
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
/**
* 插入排序
* @param a
*/
private static void insertionSort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
//...
}
未完待续...
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。