简单插入排序
public class QuickSort {
private static void quickSort(int [] a, int low, int high){
if (low >= high){
return;
}
int i = low;
int j = high;
int temp = a[i];
while (i < j){
while (i <j && a[j] >= temp){
j--;
}
if (i < j){
a[i++] = a[j];
}
while (i < j && a[i] < temp){
i++;
}
if (i < j){
a[j--] = a[i];
}
}
a[i] = temp;
quickSort(a, low, i -1);
quickSort(a, i + 1, high);
}
public static void main(String [] args){
int [] a = {9,2,5,3,1,4,8,0,7,6};
quickSort(a, 0, a.length-1);
for (int anA : a) {
System.out.print(anA + " ");
}
}
}
选择排序
public class SelectSort {
private static void sortSelect(int [] a ){
int i;
int j;
int temp = 0;
int flag = 0;
for (i = 0; i < a.length; i++){
temp = a[i];
flag = i;
for (j = i +1; j <a.length; j++){
if (a[j] < temp){
temp = a[j];
flag = j;
}
}
if (flag != i){
a[flag] = a[i];
a[i] = temp;
}
}
}
public static void main(String [] args){
int [] a = {3,1,5,4,2,7,8,6,0,9};
sortSelect(a);
for (int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
}
}
冒泡排序
public class BubbleSort {
private static void bubbleSort(int [] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++){
for (int j = n -1; j > i; j--){
if (a[j-1] > a[j]){
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
public static void main(String [] args){
int [] a = {9,2,5,3,1,4,8,0,7,6};
bubbleSort(a);
for (int anA : a) {
System.out.print(anA + " ");
}
}
}
快速排序
public class QuickSort {
private static void quickSort(int [] a, int low, int high){
if (low >= high){
return;
}
int i = low;
int j = high;
int temp = a[i];
while (i < j){
while (i <j && a[j] >= temp){
j--;
}
if (i < j){
a[i++] = a[j];
}
while (i < j && a[i] < temp){
i++;
}
if (i < j){
a[j--] = a[i];
}
}
a[i] = temp;
quickSort(a, low, i -1);
quickSort(a, i + 1, high);
}
public static void main(String [] args){
int [] a = {9,2,5,3,1,4,8,0,7,6};
quickSort(a, 0, a.length-1);
for (int anA : a) {
System.out.print(anA + " ");
}
}
}
希尔排序
public class ShellSort {
public static void shellSort(int[] a){
int length = a.length;
for (int gap = length/2; gap > 0; gap /= 2){
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < length; j += gap){ //每个子序列都从第二个开始
if (a[j] < a[j - gap]){
int temp = a[j];
int k = j;
while ( k >= gap && a[k-gap] > temp){
a[k] = a[k-gap];
k -= gap;
}
a[k] = temp;
}
}
}
}
}
public static void main(String[] args){
int [] a = {9,2,5,3,10,1,4,8,0,7,6};
shellSort(a);
for (int anA : a) {
System.out.print(anA + " ");
}
}
}
归并排序
public class MergeSort {
public static void merge(int [] a, int start, int median, int end){
int i;
int j;
int k;
int n1 = median - start + 1;
int n2 = end - median;
int[] L = new int[n1];
int[] R = new int[n2];
for (i = 0, k = start; i < n1; i++, k++){
L[i] = a[k];
}
for (i = 0, k = median + 1; i < n2; i++, k++){
R[i] = a[k];
}
for (k = start, i = 0, j = 0; i < n1 && j < n2; k++){
if (L[i] < R[j]) {
a[k] = L[i];
i++;
} else {
a[k] = R[j];
j++;
}
}
while (i < n1){
a[k] = L[i];
i++;
k++;
}
while (j < n2){
a[k] = R[j];
j++;
k++;
}
}
public static void mergeSort(int[] a, int start, int end){
if (start < end){
int median = (start + end) / 2;
mergeSort(a, start, median);
mergeSort(a, median + 1, end);
merge(a, start, median, end);
}
}
public static void main(String[] args){
int [] a = {9,2,5,3,10,1,4,8,0,7,6};
mergeSort(a, 0, a.length-1);
for (int anA : a) {
System.out.print(anA + " ");
}
}
}
堆排序
public class HeapSort {
private static void maxHeapDown(int[] a, int start, int end){
int father = start;
int child = 2 * father + 1; // 左孩子
while (child <= end){
if (child < end && a[child] < a[child + 1]){
child++; // 如果右孩子大，将左孩子变为右孩子
}
if (a[father] >= a[child]){
break;
}else {
int tmp = a[father];
a[father] = a[child];
a[child] = tmp;
}
father = child;
child = 2 * father + 1;
}
}
private static void heapSortAsc(int[] a){
int i;
int n = a.length;
for (i = n / 2 -1; i >= 0; i--){ // 从最后一个非终端节点开始，逐个向上遍历
maxHeapDown(a, i, n-1);
}
for (i = n - 1; i > 0; i--){
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
maxHeapDown(a, 0, i-1);
}
}
public static void main(String[] args){
int[] a = {9,2,5,4,7,3,8,0,1,6};
heapSortAsc(a);
for (int i :a){
System.out.print(i + " ");
}
}
}
基数排序
public class RadixSort {
private static int getMax(int[] a ){
int max = a[0];
for (int i : a){
if (i > max){
max = i;
}
}
return max;
}
private static void countSort(int[] a, int exp){
int[] output = new int[a.length];
int[] buckets = new int[10];
for (int anA : a) {
buckets[(anA / exp) % 10]++;
}
for (int i : buckets)
System.out.print(i + " ");
System.out.println();
for (int i = 1; i < 10; i++){
buckets[i] += buckets[i - 1];
}
for (int i : buckets)
System.out.print(i + " ");
System.out.println();
for (int i = a.length - 1; i >= 0; i--){
output[buckets[(a[i] / exp) % 10] - 1] = a[i];
buckets[(a[i] / exp) % 10]--;
}
for (int i = 0; i < a.length; i++){
a[i] = output[i];
}
output = null;
buckets = null;
}
private static void radixSort(int[] a){
int max = getMax(a);
for (int exp = 1; max / exp > 0; exp *= 10){
countSort(a, exp);
}
}
public static void main(String[] args){
int[] a = {53, 3, 542, 748, 14, 214, 154, 63, 616};
radixSort(a);
for (int i : a){
System.out.print(i + " ");
}
}
}