一、3种简单排序
3种排序方法时间复杂度都是n2
3种简单排序对 数组排序速度： 插入排序 > 选择排序 > 冒泡法
5w大小数组排序运行时间
public static void main(String[] args) {
int len = 50000;
int[] arr = new int[len];
int[] arr2 = new int[len];
int[] arr3 = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * len + 1);
arr2[i] = arr[i];
arr3[i] = arr[i];
}
bubbleSort(arr);
selectSort(arr2);
insertSort(arr3);
}
/**
* 冒泡法
*/
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int num = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = num;
}
}
}
}
/**
* 选择排序
*/
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
int num = arr[i];
arr[i] = arr[min];
arr[min] = num;
}
}
/**
* 插入排序
*/
private static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 1]) {
int num = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = num;
j--;
}
}
}
当然还有很多的3种方法改进方法这里就不介绍了。
二、复杂排序
希尔排序
当然是不可能的
真香
希尔排序就是插入排序的改进
时间复杂度n~n2这个真不知道怎么得出来的
不过这个运行时间的确是波动的，不过也远好于插入排序
5w大小数组排序运行时间
/**
* 希尔排序
*/
private static void shellSort(int[] arr) {
int n = arr.length;
int step = n / 2;
while (step > 0) {
for (int j = step; j < n; j++) {
int i = j;
while (i >= step && arr[i - step] > arr[i]) {
int num = arr[i];
arr[i] = arr[i - step];
arr[i - step] = num;
i -= step;
}
}
step = step / 2;
}
}
归并排序
时间复杂度nlog2n
空间复杂度为n 以上那些为1
消耗内存，以空间换时间
5w大小数组排序运行时间
/**
* 归并排序
*/
private static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= high) {
temp[k++] = arr[j++];
}
for (int x = 0; x < temp.length; x++) {
arr[x + low] = temp[x];
}
}
基数排序
真的看不懂这个额
时间复杂度k*n
空间复杂度为k+n
/**
* 归并排序
*/
private static void radixSort(int[] arr) {
radixSort1(arr, getMaxWeishu(arr));
}
private static void radixSort(int[] a, int d) {
int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;
}
}
}
private static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
private static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else {
break;
}
}
return d;
}
数据比较多的时候能体现出差距：
5w大小数组排序运行时间
50w大小数组排序运行时间
完毕！
