文章目录
- 选择排序
- 插入排序
- 冒泡排序
- 快速排序
- 二分查找
- 交换两个位置的元素
- 总结
各种排序算法复杂度总结如下:
选择排序
分析:
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
for (int i = 0; i < N - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < N; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
复杂度分析:
插入排序
分析:
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
for (int i = 1; i < N; i++) {
int index = i;
while (index - 1 >= 0 && arr[index - 1] > arr[index]) {
swap(arr, index - 1, index);
index--;
}
}
}
冒泡排序
分析:相邻元素比较,左边大于右边就交换,然后循环
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
swap(arr, i, j);
}
}
}
}
快速排序
分析:快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!
快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
int arr[] = {3, 4, 1, 5, 6, 3, 8, 2, 7};
printArr(quickSort(arr,0,arr.length-1));
public int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
二分查找
该算法要求:1、 必须采用顺序存储结构。 2、 必须按关键字大小有序排列。
该算法时间复杂度最坏为:O(logn), 注意点有mid、low、high。可以使用递归或迭代方式
public static int binary_Search(int[] arr, int low, int high, int key) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) {
return mid;
}
if (arr[mid] > key) {
return binary_Search(arr, low, mid - 1, key);
} else {
return binary_Search(arr, mid + 1, high, key);
}
}
return -1;
}
public static int binary_Search_iterator(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
交换两个位置的元素
public static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public static void printArr(int[] arr) {
int N = arr.length;
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void swap2(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
总结
未完待续… 2021年4月17日 周六
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)