1.java代码
public class SortUtil {
//冒泡排序
public static void bubble(int[] a) {
int len = a.length;
int flag = len;
while (flag > 0) {
flag = 0;
for (int i = 1; i < len; i++) {
if (a[i] < a[i - 1]) {
int temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
flag = i;
}
}
len = flag;
}
}
//简单选择排序
public static void select(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
//插入排序
public static void insert(int[] a) {
for (int i = 1; i < a.length; i++) {
int j = i;
int temp = a[i];
while (j > 0 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
//快速排序
public static void quick(int[] a, int start, int end) {
if (start > end) return;
int left = start;
int right = end;
int partition = a[start];
while (left < right) {
while (left < right && a[right] >= partition) {
right--;
}
while (left < right && a[left] <= partition) {
left++;
}
if (left < right) {
int temp = a[right];
a[right] = a[left];
a[left] = temp;
}
}
a[start] = a[left];
a[left] = partition;
quick(a, start, left - 1);
quick(a, right + 1, end);
}
//希尔排序
public static void shell(int[] arr) {
// i表示希尔排序中的第n/2+1个元素(或者n/4+1)
// j表示希尔排序中从0到n/2的元素(n/4)
// r表示希尔排序中n/2+1或者n/4+1的值
// 划组排序
for (int r = arr.length / 2; r >= 1; r = r / 2) {
for (int i = r; i < arr.length; i++) {
int tmp = arr[i];
int j = i - r;
// 一轮排序
while (j >= 0 && tmp < arr[j]) {
arr[j + r] = arr[j];
j -= r;
}
arr[j + r] = tmp;
}
}
}
//构建大根堆
public static void buildMaxHeap(int[] a, int lastIndex) {
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
int k = i;
int bigIndex = 2 * k + 1;
if (bigIndex + 1 <= lastIndex && a[bigIndex] < a[bigIndex + 1]) {
bigIndex++;
}
if (a[k] < a[bigIndex]) {
int temp = a[bigIndex];
a[bigIndex] = a[k];
a[k] = temp;
}
}
}
//堆排序
public static void heap(int[] a) {
for (int i = 0; i < a.length-1; i++) {
buildMaxHeap(a, a.length - 1 - i);
int temp = a[0];
a[0] = a[a.length - 1 - i];
a[a.length - 1 - i] = temp;
}
}
//合并
public static void merge(int[] a, int start, int mid, int end) {
int[] temp = new int[a.length];
int i = start;
int j = mid + 1;
int k = start;
while (i <= mid && j <= end) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= end) {
temp[k++] = a[j++];
}
for (int n = start; n <= end; n++) {
a[n] = temp[n];
}
}
//归并排序
public static void merge(int[] a, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
merge(a, start, mid);
merge(a, mid + 1, end);
merge(a, start, mid, end);
}
}
//基数排序
public static void radix(int[] a) {
int disisor = 1;
int[][] bucket = new int[10][a.length];
int[] count = new int[10];
int digit;
for (int i = 1; i <= 3; i++) {
for (int temp : a) {
digit = (temp / disisor) % 10;
bucket[digit][count[digit]++] = temp;
}
int k = 0;
for (int m = 0; m < 10; m++) {
if (count[m] == 0) {
continue;
}
for (int n = 0; n < count[m]; n++) {
a[k++] = bucket[m][n];
}
count[m] = 0;
}
disisor *= 10;
}
}
//二分插入排序
public static void advanceInsertSortWithBinarySearch(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int low = 0, high = i - 1;
int mid = -1;
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] > temp) {
high = mid - 1;
} else { // 元素相同时,也插入在后面的位置
low = mid + 1;
}
}
for(int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp;
}
}
//计数排序
public static void count(int[] a,int maxNum){
int[] b=new int[maxNum+1];//maxNum为数组a中最大的数,+1是因为有0这个数
for (int i=0;i<a.length;i++){
b[a[i]]++;
}
int k=0;
for (int j=0;j<b.length;j++){
while (b[j]>0){
a[k++]=j;
b[j]--;
}
}
}
}