序言：
算法系列文章会以《算法导论》 为参考，使用Java语言实现算法相关的知识，算法全篇文章主要涉及的是代码，而不是分析内容，推导过程可参考算法导论书籍或者网上寻找。
快速排序
public class QuickSortHelper {
public static void quickSort(int[] a, int p, int r) {
if (p >= r) {
return;
}
int q = partition(a, p, r);
quickSort(a, p, q - 1);
quickSort(a, q + 1, r);
}
public static int partition(int[] a, int p, int r) {
int x = a[r];
int i = p - 1;
for (int j = p; j < r; j ++) {
if (a[j] <= x) {
i += 1;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int temp = a[i + 1];
a[i + 1] = a[r];
a[r] = temp;
return i + 1;
}
public static int randomPartition(int[] a, int p, int r) {
int i = p + (int)(Math.random() * (r - p));
int temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(a, p, r);
}
public static void randomQuickSort(int[] a, int p, int r) {
if (p >= r) {
return;
}
int q = randomPartition(a, p, r);
randomQuickSort(a, p, q - 1);
randomQuickSort(a, q + 1, r);
}
public static void main(String args[]) {
int[] a = {3, 4, 2, 1, 6, 29, 56, 23, 43};
int p = 0;
int r = a.length - 1;
System.out.println("quickSort before:" + Arrays.toString(a));
randomQuickSort(a, p, r);
System.out.println("quickSort after:" + Arrays.toString(a));
}
}
计数排序
public class CountSortHelper {
public static void countingSort(int[] a, int[] b, int k) {
int[] c = new int[k];
for(int i = 0; i< k; i ++) {
c[i] = 0;
}
for(int j = 0; j < a.length; j ++) {
c[a[j]] = c[a[j]] + 1;
}
for(int m = 1; m < k; m++) {
c[m] = c[m] + c[m - 1];
}
for(int n = 0; n < a.length; n ++) {
c[a[n]] = c[a[n]] - 1;
b[c[a[n]]] = a[n];
}
}
public static int[] getAToArray(int n, int k) {
int[] a = new int[n];
for(int i = 0; i< n; i ++) {
a[i] = (int)(Math.random() * k);
}
return a;
}
public static void main(String[] args) {
int n = 44;
int k = 721;
int[] a = getAToArray(n, k);
int[] b = new int[n];
System.out.println("countingSort before b:" +Arrays.toString(b));
countingSort(a, b, k);
System.out.println("countingSort after b:" +Arrays.toString(b));
}
}
基数排序
/**
* 基数排序
*/
public class BaseNumSortHelper {
public static void baseNumSort(int[] a, int k) {
int[][] b = new int[10][a.length];
for(int j = 0; j < k; j ++) {
int[] count = new int[a.length];
for(int i = 0;i < a.length; i++) {
int num = a[i];
int index = (num / ((int) Math.pow(10, j))) % 10;
int c = count[index];
b[index][c] = num;
count[index] = count[index] + 1;
}
int index = 0;
for(int m = 0; m < b.length; m++) {
for(int n= 0; n < b[m].length; n++) {
if(b[m][n] != 0) {
a[index] = b[m][n];
index ++;
b[m][n] = 0;
}
}
}
}
}
public static int[] getCollections(int n, int k) {
int[] a = new int[n];
for (int i = 0; i< n; i++) {
int num = (int)(Math.random() * Math.pow(10, k));
a[i] = num;
}
return a;
}
public static void main(String[] args) {
int n = 20;
int k = 3;
int[] a = getCollections(n, k);
System.out.println("Sort before:" + Arrays.toString(a));
baseNumSort(a, k);
System.out.println("Sort after:" + Arrays.toString(a));
}
}
网友评论