时间复杂度和空间复杂度
-
O(1) 常数
-
O(n) 线性
-
O(n^2) 平方
-
O(n^3)立方
-
O（n!）阶乘
-
O(logn) 对数
-
O(nlogn)
-
O(2^) 指数
-
时间复杂度顺序从小到大的顺序O(1)<O(log n) < O(n )< O(nlogn) < O(n^2) <O(n^3) < O(2^n) <O(n!) < O(n^n)
对比.png
排序分类以及时间复杂度
| 类型 | 排序方法 | 时间复杂度-平均情况 | 时间复杂度-最好情况 | 时间复杂度-最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 直接插入 | O(n^2) | O(N) | O(n^2) | O(1) | 稳定 |
| 插入排序 | shell(希尔)排序 | O(n^2) | O(N) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | 直接选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 交换排序 | 冒泡排序 | O(n^2) | O(N) | O(n^2) | O(1) | 稳定 |
| 交换排序 | 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn) | 不稳定 |
| 归并排序 | 快速排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 稳定 |
快速排序（挖坑埋数 + 分治法）
-
初始化 i= i， j =r，x = a[i]，取数组第一个数作为基准数
-
j--,找出小与基准数的数据，挖出来，放到默认的第一个坑中；
-
i++找出大于等于基准数的值，放到刚才的坑中；
-
重复2，3操作，当i==j中的话，把基准数放入其中
-
求出第一个基准数后，然后递归基准数的左边，基准数的右边
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) {// 从右向左找第一个小于x的数
j--;
}
if(i < j) {
s[i++] = s[j];
}
while(i < j && s[i] < x) {// 从左向右找第一个大于等于x的数
i++;
}
if(i < j) {
s[j--] = s[i];
}
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
冒泡排序
void bubbleSort(int arr[]){
if(arr==null || arr.length < 2 ){
return;
}
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 temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
网友评论