作者:wyyxit | 来源:互联网 | 2023-05-17 18:46
面试中难免会问到一些排序算法,最常见的无非是冒泡排序,选择排序,快速排序,今天先来学习这三个算法,大家应该都会,我只是作为总结,记录下随机数组如下int[]sortArraynewint[]
面试中难免会问到一些排序算法,最常见的无非是冒泡排序,选择排序,快速排序,今天先来学习这三个算法,大家应该都会,我只是作为总结,记录下
随机数组如下
int[] sortArray = new int[]{2, 1, 2, 7, 4, 6, 8, 10};
一 冒泡排序
一列数组从小到大进行冒泡排序,两层for循环,时间复杂度为O(n2)
//冒泡排序
private void BubbleSort(int[] sortArray) {
if ((sortArray == null) || (sortArray.length == 0))
return;
int temp;
for (int i = 0; i length - 1; i++) {
for (int j = i + 1; j length; j++) {
if (sortArray[i] > sortArray[j]) {
temp = sortArray[i];
sortArray[i] = sortArray[j];
sortArray[j] = temp;
}
}
}
for (int i = 0; i length; i++) {
Log.e(getClass().getSimpleName() + "bubbleSort ", String.valueOf(sortArray[i]));
}
}
冒泡log输出如下
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 1
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 2
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 2
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 4
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 6
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 7
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 8
11:57:45.870 12101-12101/com.asiatravel.asiatravel E/MainActivitybubbleSort: 10
二 选择排序
选择排序是冒泡的升级版,时间复杂度为O(n2)
//选择排序
private void selectSort(int[] a) {
int minIndex = 0;
int temp = 0;
if ((a == null) || (a.length == 0))
return;
for (int i = 0; i length - 1; i++) {
minIndex = i;//无序区的最小数据数组下标
for (int j = i + 1; j length; j++) {
//在无序区中找到最小数据并保存其数组下标
if (a[j] minIndex = j;
}
}
if (minIndex != i) {
//如果不是无序区的最小值位置不是默认的第一个数据,则交换之。
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
for (int i = 0; i length; i++) {
Log.e(getClass().getSimpleName() + "selectSort ", String.valueOf(a[i]));
}
}
输出log如下
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 1
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 2
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 2
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 4
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 6
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 7
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 8
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityselectSort: 10
三 快速排序
快速排序也是冒泡的升级版,时间复杂度为O(n2)
//快速排序
private void quickSort(int[] arr, int low, int high) {
int l = low;
int h = high;
int povit = arr[low];
while (l while (l = povit)
h--;
if (l int temp = arr[h];
arr[h] = arr[l];
arr[l] = temp;
l++;
}
while (l l++;
if (l int temp = arr[h];
arr[h] = arr[l];
arr[l] = temp;
h--;
}
}
System.out.print("quickSort " + "l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
if (l > low) quickSort(arr, low, l - 1);
if (h , l + 1, high);
}
for (int i = 0; i length; i++) {
Log.e(getClass().getSimpleName() + "quickSort ", String.valueOf(arr[i]));
}
}
输出 log如下
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 1
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 2
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 2
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 4
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 6
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 7
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 8
11:59:24.910 12858-12858/com.asiatravel.asiatravel E/MainActivityquickSort: 10
关于时间复杂度,请移步这篇博客,针对性的对比算法复杂度,总结的挺好
http://blog.csdn.net/wuxinyicomeon/article/details/5996675/
还有不明白的,百度百科介绍的很详细,我也是做个笔记记录下,与君共勉!