文章目录
【冒泡排序】【选择排序】【插入排序】【快排】【归并排序】【堆排序】【希尔排序】【计数排序】【基數排序（桶排序）】
【冒泡排序】
import java.util.*;
//冒泡排序
public class BubbleSort {
public int[] bubbleSort(int[] A, int n) {
for(int i=0;i<n;++i) {
for(int j=1;j<n-i;++j) {
if(A[j]<A[j-1]) {
swap(A,j,j-1);
}
}
}
return A;
}
private void swap(int[] a, int j, int i) {
int tmp = a[j];
a[j] = a[i];
a[i] = tmp;
}
}
【选择排序】
import java.util.*;
//選擇排序
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
for(int i=0;i<n;++i) {
int min = Integer.MAX_VALUE;
int pos = -1; //記錄最小值的位置
for(int j=i;j<n;++j) {
//從A[j..n-1]中選出一個最小值
if(min>A[j]) {
min = A[j];
pos = j;
}
}
A[pos] = A[i];
A[i] = min;
}
return A;
}
}
【插入排序】
import java.util.*;
//插入排序
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
for(int i = 0;i<n;++i) {
int tmp = A[i];
int tail = i-1; //有序區間的tail
while(tail>=0) {
if(tmp<A[tail]) {
A[tail+1] = A[tail];
}else {
break;
}
tail--;
}
A[tail+1] = tmp;
}
return A;
}
}
【快排】
import java.util.*;
//快排
public class QuickSort {
public int[] quickSort(int[] A, int n) {
qs(A,0,n-1);
return A;
}
private void qs(int[] a, int start, int end) {
if(start>=end)
return ;
//以最后一个元素为枢纽
int tmp = a[end];
int pos = start; //pos指向 小于枢纽区 外 的 第一个位置
for(int i = start;i<end;++i) {
if(a[i]<tmp) {
//a[i]放入小于枢纽区
swap(a,pos,i);
pos++;
}
}
swap(a,pos,end);
qs(a,start,pos-1);
qs(a,pos+1,end);
}
private void swap(int[] a, int pos, int end) {
int tmp = a[pos];
a[pos] = a[end];
a[end] = tmp;
}
}
【归并排序】
import java.util.*;
//歸并排序
public class MergeSort {
public int[] mergeSort(int[] A, int n) {
merge(A,0,n-1);
return A;
}
private void merge(int[] A, int start, int end) {
if(start>=end) {
return;
}
int mid = (start+end)/2;
merge(A,start,mid);
merge(A,mid+1,end);
sort(A,start,mid,end);
}
private void sort(int[] a, int start, int mid, int end) {
int[] A = new int[mid-start+1];
int[] B = new int[end-mid];
for(int i=start;i<=end;++i) {
if(i<=mid)
A[i-start] = a[i];
else
B[i-mid-1] = a[i];
}
int i = 0;
int j = 0;
int pos = start;
while(i<A.length&&j<B.length) {
if(A[i]<B[j]) {
a[pos++] = A[i++];
}else {
a[pos++] = B[j++];
}
}
while(i<A.length) {
a[pos++] = A[i++];
}
while(j<B.length) {
a[pos++] = B[j++];
}
}
}
【堆排序】
//堆排序:實現原地排序
public class HeapSort {
public int[] heapSort(int[] A, int n) {
//建大頂堆
creatheap(A);
//进行堆排序
sort(A);
return A;
}
private void sort(int[] A) {
//拿走頭 然後將最後一個數據放在頭部 調整堆 把頭放在堆外的第一個位置
//頭始終是A[0]
int tail = A.length;
while(tail>0) {
int tmp = A[0];
A[0] = A[--tail];
adjustheap(A, 0, tail);
A[tail] = tmp;
}
}
private void creatheap(int[] A) {
//從後往前處理數據 以采用自上而下的調整策略
//即:堆化 0-A.length/2 位置的數據 而A.length/2位置的節點是葉子節點 不需要自上而下堆化
for(int i =A.length/2 ;i>=0;--i) {
inserttoA(A,i,A.length);
}
}
//將data插入堆中的最後一個位置的后一個位置 ，並進行堆化調整(自上而下)
private void inserttoA(int[] heap, int top, int capcity) {
adjustheap(heap,top,capcity);
}
//top表示將要堆化的位置，capcity表示堆的容量 指向堆的最後一個元素的 後一個位置
private void adjustheap(int[] heap, int top, int capcity) {
int fpos = top;
int lpos = 2*fpos+1;
int rpos = 2*fpos+2;
while(lpos<capcity) {
if(rpos<capcity) {
int max = heap[lpos]>heap[rpos]?lpos:rpos;
if(heap[fpos]<heap[max]) {
swap(heap,fpos,max);
fpos = max;
lpos = fpos*2+1;
rpos = fpos*2+2;
}else {
return;
}
}else {
if(heap[fpos]<heap[lpos])
swap(heap,fpos,lpos);
return;
}
}
}
private void swap(int[] heap, int fpos, int max) {
int tmp = heap[fpos];
heap[fpos] = heap[max];
heap[max] = tmp;
}
}
【希尔排序】
import java.util.*;
//希尔排序 : 希尔排序是改进版的插入排序,其时间复杂度依赖于步长的选择
public class ShellSort {
int step = 3; //设定步长为3
public int[] shellSort(int[] A, int n) {
for(int st = step;st>0;st--) {
for(int pos = st;pos<A.length;++pos) {
int tmp = A[pos];
int pre = pos-st;
for(;pre>=0;pre-=st) {
if(A[pre]>tmp) {
//将pre位置的数据往后挪
A[pre+st] = A[pre];
}else {
//找到了插入位置
break;
}
}
A[pre+st] = tmp;
}
}
return A;
}
}
【计数排序】
import java.util.*;
//计数排序
public class CountingSort {
public int[] countingSort(int[] A, int n) {
//首先需要获取 计数的最大值和最小值
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i=0;i<n;++i){
max = max>A[i]?max:A[i];
min = min<A[i]?min:A[i];
}
int[] count = new int[max-min+1]; //count中的值代表 A[i]-min 在count中的个数
for(int i=0;i<A.length;++i){
count[A[i]-min] ++;
}
int j = 0;
for(int i=0;i<count.length;++i){
while(count[i]!=0) {
A[j++] = i+min;
count[i]--;
}
}
return A;
}
}
【基數排序（桶排序）】
import java.util.*;
//基數排序:给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000
public class RadixSort {
//四位數的基數 數字在0-9之間
public int[] radixSort(int[] A, int n) {
int[][] bucket = new int[10][n]; //0-9 號桶 每號桶的容量設置為n
int[] count = new int[10]; //每號桶中的 數據個數
//先確定數據最大是幾位數
int max = Integer.MIN_VALUE;
for(int i=0;i<n;++i) {
max = max>A[i]?max:A[i];
}
int cnt = 0;
while(max!=0) {
cnt++;
max /= 10;
}
for(int i=0;i<cnt;++i) {
for(int j = 0;j<n;++j) {
int pos = getpos(A[j],i);
bucket[pos][count[pos]++] = A[j];
}
//出桶排序
int k = 0;
for(int j = 0;j<bucket.length;++j) {
int tail = count[j];
for(int t=0;t<tail;++t) {
A[k++] = bucket[j][t];
count[j]--;
}
}
}
return A;
}
//根據a位數 確定data在桶中的位置
private int getpos(int data, int a) {
while(a>0) {
data /= 10;
a--;
}
return data;
}
}
