Sort
todo
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
/**
* 复习排序算法
*/
public class Sort {
//比较类排序-------------------------------------------------------------
//交换类----------------------
/**
* 冒泡排序(稳定)：每次走完一趟，最大的值就会到最后
*
* @param arr 数组
*/
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean flag;
for (int i = 0; i < n - 1; i++) {
flag = true;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = false;
swap(arr, j, j + 1);
}
}
if (flag) break;
}
}
/**
* 快速排序(不稳定)
*
* @param arr 数组
*/
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int index = left + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < pivot) {
swap(arr, i, index);
++index;
}
}
swap(arr, left, index - 1);
return index - 1;
}
//插入类---------------------
/**
* 插入排序
*
* @param arr 数组
*/
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0) return;
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
j--;
}
}
}
/**
* 希尔排序
*
* @param arr 数组
*/
public static void shellSort(int[] arr) {
int len = arr.length;
for (int gap = len / 2; gap > 0; gap = gap / 2) {
for (int i = gap; i < len; i++) {
int j = i;
int cur = arr[i];
while (j >= gap && cur < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = cur;
}
}
}
//选择类---------------------
//选择排序
public static void selectSort(int[] arr) {
int len = arr.length;
int minIndex;
for (int i = 0; i < len - 1; i++) {
minIndex = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) minIndex = j;
}
swap(arr, i, minIndex);
}
}
// 堆排序
public static void heapify(int[] tree, int n, int i) {
if (i >= n) return;
int max = i;
int c1 = 2 * i + 1, c2 = 2 * i + 2;
if (c1 < n && tree[c1] > tree[max]) max = c1;
if (c2 < n && tree[c2] > tree[max]) max = c2;
if (max != i) {
swap(tree, max, i);
heapify(tree, n, max);
}
}
public static void buildHeap(int[] arr) {
int len = arr.length;
int last_parent = (len) / 2;
for (int i = last_parent; i >= 0; --i) {
heapify(arr, len, i);
}
}
public static void heapSort(int[] arr) {
int len = arr.length;
buildHeap(arr);
for (int i = len - 1; i >= 0; --i) {
swap(arr,0,i);
heapify(arr,i,0);
}
}
//归并类---------------------
//归并
public static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
int[] tmp = new int[right - left + 1];
int index = 0, index1 = left, index2 = mid + 1;
while (index1 <= mid && index2 <= right) {
if (arr[index1] < arr[index2]) {
tmp[index++] = arr[index1++];
} else tmp[index++] = arr[index2++];
}
while (index1 <= mid) tmp[index++] = arr[index1++];
while (index2 <= right) tmp[index++] = arr[index2++];
System.arraycopy(tmp, 0, arr, left, tmp.length);
}
//非比较排序--------------------------------------------------------------
//计数排序
public static void countingSort(int[] arr, int maxValue) {
int[] counts = new int[maxValue + 1];
for (int i : arr) {
counts[i]++;
}
int index = 0;
for (int i = 0; i < maxValue + 1; i++) {
int count = counts[i];
while (count > 0) {
count--;
arr[index++] = i;
}
}
}
//TODO 桶排序
public static void bucketSort(int[] arr, int bucketSize) {
int maxValue = arr[0], minValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxValue) maxValue = arr[i];
else if (arr[i] < minValue) minValue = arr[i];
}
int bucketCount = (maxValue - minValue) / bucketSize + 1;
}
//基数排序
public static void radixSort(int[] arr, int maxDigit) {
Map<Integer, Queue<Integer>> map = new HashMap<>();
int mod = 10, dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (int value : arr) {
int bucket = (value % mod) / dev;
if (!map.containsKey(bucket)) {
map.put(bucket, new LinkedList<>());
}
map.get(bucket).add(value);
}
int pos = 0;
for (int j = 0; j < 10; j++) {
if (map.containsKey(j)) {
int len = map.get(j).size();
for (int k = 0; k < len; k++) {
arr[pos++] = map.get(j).poll();
}
}
}
}
}
/**
* 交换数组的值
*
* @param arr 数组
* @param i 下标
* @param j 另一个下标
*/
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = new int[]{3, 1, 4, 5, 11, 2};
// Sort.radixSort(arr, 2);
heapSort(arr);
for (int i : arr) {
System.out.printf("%d ", i);
}
}
}
