- 冒泡
俩俩交换，将最值依次放到最后
public class BubbleSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
BubbleSort bs = new BubbleSort();
bs.bubble(array);
}
private void bubble(int[] array) {
int temp = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j + 1] < array[j]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
- 选择
每次选择一个最值，与前面交换
public class SelectionSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
SelectionSort ss = new SelectionSort();
ss.selectionSort(array);
}
private void selectionSort(int[] array) {
int min, temp;
for (int i = 0; i < array.length; i++) {
min = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
- 插入排序
以一个数为初始比较直，后面的无序数组依次与有序数组比较，插入到对应位置
public class InsertionSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
InsertionSort is = new InsertionSort();
is.insertionSort(array);
}
private void insertionSort(int[] array) {
int temp = 0;
for (int i = 0; i < array.length - 1; i++) {
int cur = array[i + 1];
int perIndex = i;
while (perIndex >= 0 && cur > array[perIndex]) {
array[perIndex + 1] = array[perIndex];
perIndex--;
}
array[perIndex + 1] = cur;
}
Arrays.stream(array).forEach(System.out::println);
}
}
- 希尔排序
插入排序升级版，将逐步减小步长，获得局部有序，其中每次步长局部比较使用插入排序
public class ShellSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
ShellSort ss = new ShellSort();
ss.shellSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public void shellSort(int[] array) {
int step = array.length / 2;
while (step > 0) {
for (int i = step; i < array.length; i++) {
int temp = array[i];
int preIndex = i - step;
while (preIndex >= 0 && temp < array[preIndex]) {
array[preIndex + step] = array[preIndex];
preIndex -= step;
}
array[preIndex + step] = temp;
}
step = step / 2;
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
- 快速排序
随机取值，作为基准值，比较，分为前后俩部分，同理递归，最后获得有序数组
public class QuickSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
QuickSort qs = new QuickSort();
qs.quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public void quickSort(int[] array, int start, int end) {
if (end <= start) {
return;
}
int base = array[start];
int i = start;
int j = end;
while (i < j) {
while (j > i && array[j] > base) {
j--;
}
if (j > i) {
array[i] = array[j];
i++;
}
while (j > i && array[i] < base) {
i++;
}
if (j > i) {
array[j] = array[i];
j--;
}
}
array[i] = base;
quickSort(array, start, i - 1);
quickSort(array, i + 1, end);
}
}
- 归并排序
递归将数组逐步分为最小单位，然后局部排序，然后再一层一层归并结果，最后得到有序数组
public class MergeSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
MergeSort ms = new MergeSort();
ms.mergeSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
private void mergeSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
private void merge(int[] array, int start, int mid, int end) {
int rj = mid + 1;
int li = start;
int tIndex = 0;
int[] temp = new int[array.length];
while (li <= mid || rj <= end) {
if (li > mid) {
while (rj <= end) {
temp[tIndex] = array[rj];
tIndex++;
rj++;
}
} else if (rj > end) {
while (li <= mid) {
temp[tIndex] = array[li];
tIndex++;
li++;
}
} else {
if (array[li] <= array[rj]) {
temp[tIndex] = array[li];
li++;
} else {
temp[tIndex] = array[rj];
rj++;
}
}
tIndex++;
}
int curIndex = start;
while (curIndex <= end) {
array[curIndex] = temp[curIndex - start];
curIndex++;
}
}
}
- 基数排序
依次根据个位、十位.... 根据每个位置上的数值进行分组，最后的到的就是有序结果
public class RadixSort {
public static void main(String[] args) {
int[] array = {
23, 57, 21, 68, 3, 67, 12, 7, 1, 30
};
RadixSort rs = new RadixSort();
rs.radixSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
private void radixSort(int[] array) {
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int maxDigit = 0;
while (max != 0) {
max = max / 10;
maxDigit++;
}
for (int i = 1; i <= maxDigit; i++) {
List<Integer> temp = new ArrayList();
List<List<Integer>> bucket = new ArrayList<>();
for (int k = 0; k < 10; k++) {
List list = new ArrayList();
bucket.add(list);
}
for (int j = 0; j < array.length; j++) {
int endNum = (array[j] / ((int) Math.pow(10, i - 1))) % 10;
bucket.get(endNum).add(array[j]);
}
bucket.forEach(list -> {
for (int j = 0; j < list.size(); j++) {
temp.add(list.get(j));
}
});
for (int j = 0; j < temp.size(); j++) {
array[j] = temp.get(j);
}
}
}
}
- 堆排序
首先通过最后一个非叶子节点开始，自底向上调整成为大顶堆（或小顶堆），然后交换顶端节点与最后一个元素，调整堆，继续获取，直到结束
public class HeapSort {
public static void main(String[] args) {
int[] array = {
4, 6, 8, 5, 9
};
HeapSort hs = new HeapSort();
hs.heapSort(array);
hs.show(array);
}
private void heapSort(int[] array) {
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
for (int i = array.length - 1; i > 0; i--) {
swap(array, 0, i);
adjustHeap(array, 0, i);
}
}
public void show(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
private void adjustHeap(int[] array, int i, int length) {
int temp = array[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k < length - 1 && array[k] < array[k + 1]) {
k++;
}
if (array[k] > temp) {
array[i] = array[k];
i = k;
} else {
break;
}
}
array[i] = temp;
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
