冒泡排序:
package com.sort;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;
public class bubble {
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 2, 5, 9, 7, 8, 6 };
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int temp = 0;
for (int i = 0; i <= arr.length - 1; i++) {
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
快速排序:
package com.sort;
import java.util.Arrays;
public class Quick {
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 2, 5, 9, 7, 8, 6 };
int low = 0;
int high = arr.length - 1;
sort(arr, low, high);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int low, int high) {
if (low < high) {
int l = low;
int h = high;
int j = arr[l];
while (l < h) {
while (l < h && arr[h] > j) {
h--;// 从右向左找第一个小于x的数
}
if (l < h) {
arr[l] = arr[h];
l++;
}
while (l < h && arr[l] < j) {
l++;// 从左向右找第一个大于x的数
}
if (l < h) {
arr[h] = arr[l];
h--;
}
}
arr[l] = j;
sort(arr, low, l - 1); /* 递归调用 */
sort(arr, l + 1, high); /* 递归调用 */
}
}
}
归并排序:
package com.sort;
import java.util.Arrays;
import java.util.Objects;
/**
* 空间复杂度:n 最好时间复杂度:nlog2n 最坏时间复杂度:nlog2n 平均时间复杂度:nlog2n 稳定性:稳定
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = { 9, 2, 3, 6, 4, 8, 5, 0, 7, 1};
merge(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
public static void merge(int[] arr, int l, int r) {
// 如果数组还剩一个就弹出
if (l == r) {
return;
}
int mid = (l + r) >> 1;// 获取中点
// 对左半边进行归并:分解
merge(arr, l, mid);
// 对右半边进行归并:分解
merge(arr, mid + 1, r);
// 调用排序方法:合并
sort(arr, l, mid, r);
}
private static void sort(int[] arr, int l, int mid, int r) {
// 创建一个辅助数组
int[] temp = new int[r - l + 1];
int j = 0;
int p = l;
int q = mid + 1;
while (p <= mid && q <= r) {
temp[j++] = arr[p]<arr[q]?arr[p++]:arr[q++];
}
while (p <= mid) {
temp[j++] = arr[p++];
}
while (q <= r) {
temp[j++] = arr[q++];
}
for (int i = 0; i <= temp.length - 1; i++) {
arr[l + i] = temp[i];
}
}
}