通俗易懂十大排序算法算法复杂度十大排序算法

69 阅读 0 评论 46 点赞

我是靠谱客的博主个性歌曲，这篇文章主要介绍通俗易懂十大排序算法算法复杂度十大排序算法，现在分享给大家，希望可以做个参考。

算法复杂度

什么是算法的复杂度？

算法复杂度可分为时间复杂度和空间复杂度
- 时间复杂度：对应的是这个算法所需要的计算工作量所消耗的时间
  - 一个算法中语句执行次数称之为 语句频度或 时间频度
  - 为了描述时间频度变化引起的变化规律，引入时间复杂度
- 空间复杂度：对应的是这个算法所需要的内存空间大小
空间复杂度可以通过钱解决加内存，所以我们学习算法复杂度时，重点要倾向于时间复杂度上，但是有些特殊情况下，空间复杂度会比时间复杂度更为重要。

时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就越多，花费时间少的算法越值钱
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
为了描述时间频度变化引起的变化规律，引入时间复杂度概念。记为O(…)
时间频度不同，但时间复杂度可能相同
- 时间复杂度计算规则只需要遵循如下守则：
  - 用常数1来取代运行时间中所有加法常数
  - 只要高阶项，不要低阶项
  - 不要高阶项系数

常见的时间复杂度场景
复制代码O(1)—常数阶 Systemctl.out.println("1");
```
1
2
3
O(1)—常数阶
Systemctl.out.println("1");
```
复制代码O(N)—线性阶 for(int i = 0;i < n;i++){ Systemctl.out.println("1"); }
```
1
2
3
4
5
O(N)—线性阶
for(int i = 0;i < n;i++){
Systemctl.out.println("1");
}
```
复制代码O(logN)—对数阶 for(int i = 0;i < n;i*=2){ Systemctl.out.println("1"); }
```
1
2
3
4
5
O(logN)—对数阶
for(int i = 0;i < n;i*=2){
Systemctl.out.println("1");
}
```
复制代码O(n^2)—平方阶 for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ Systemctl.out.println("1"); } }
```
1
2
3
4
5
6
7
O(n^2)—平方阶
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
Systemctl.out.println("1");
}
}
```
复制代码O(nlogn)—线性对数阶 for(int i = 0;i < n;i++){ for(int j = 0;j < n;j*=2){ Systemctl.out.println("1"); } }
```
1
2
3
4
5
6
7
O(nlogn)—线性对数阶
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j*=2){
Systemctl.out.println("1");
}
}
```
时间复杂度估算算法优劣的时候注重的是算法的潜力
- 有100条数据的时候算法A比算法B快
- 有1000条数据的时候算法B比算法A快
- 算法b的时间复杂度更优

十大排序算法

冒泡：
- 从第一位开始，当前位置数字和后面的数字进行比较
- 如果当前数字大于后面则交换数据及位置
- 时间复杂度O=n^2
  复制代码//冒泡排序 int arr[] = {1,2,4,6,7,3,5,8,0,9}; for (int i = 0; i < arr.length; i++) { for(int j = i;j < arr.length;j++) { if(arr[i]>arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } System.out.println(Arrays.toString(arr));
```
1
2
3
4
5
6
7
8
9
10
11
12
13
//冒泡排序
int arr[] = {1,2,4,6,7,3,5,8,0,9};
for (int i = 0; i < arr.length; i++) {
for(int j = i;j < arr.length;j++) {
if(arr[i]>arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
```
选择：
- 假设第一位数就是数组中最小的数据，记录他的索引
- 依次与之后的数字相比较，如果出现比最小数组小的数字，重新记录索引
- 时间复杂度 O=n^2
  复制代码//快速排序 int arr[] = {1,2,4,6,7,3,5,8,0,9}; for (int i = 0; i < arr.length; i++) { System.out.println(Arrays.toString(arr)); int temp = i; for(int j = i+1;j< arr.length;j++) { if(arr[j]<arr[temp]) { temp = j; } } if(temp!=i) { int t = arr[temp]; arr[temp] = arr[i]; arr[i] = t; } }
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//快速排序
int arr[] = {1,2,4,6,7,3,5,8,0,9};
for (int i = 0; i < arr.length; i++) {
System.out.println(Arrays.toString(arr));
int temp = i;
for(int j = i+1;j< arr.length;j++) {
if(arr[j]<arr[temp]) {
temp = j;
}
}
if(temp!=i) {
int t = arr[temp];
arr[temp] = arr[i];
arr[i] = t;
}
}
```
插入：
- 先将要插入的数字提取出来
- 每次向数列中提出一个数字，从当前位置开始向左比较
- 如果比其值小则索引位置向右移动，原来位置不做填充，作为一个“坑”，直到找到合适位置
- 最后如果将之前取出的数据填入坑中
  复制代码//插入排序 int arr[] = {1,2,4,6,7,3,5,8,0,9}; for(int i = 1; i < arr.length; i++) { int key = arr[i]; int j ; for (j = i; j > 0&&key<arr[j-1]; j--) { arr[j] = arr[j-1]; } arr[j] = key; System.out.println(Arrays.toString(arr)); } System.out.println(Arrays.toString(arr));
```
1
2
3
4
5
6
7
8
9
10
11
12
13
//插入排序
int arr[] = {1,2,4,6,7,3,5,8,0,9};
for(int i = 1; i < arr.length; i++) {
int key = arr[i];
int j ;
for (j = i; j > 0&&key<arr[j-1]; j--) {
arr[j] = arr[j-1];
}
arr[j] = key;
System.out.println(Arrays.toString(arr));
}
System.out.println(Arrays.toString(arr));
```
希尔：
- 将数据递归分组，首先分为长度/2组
- 然后将第一个数字与第1+（组数）进行插入排序，经过第一次整体排序后，小的数字很快被移动到前面
- 重新将数据分组，原来组/2
- 小的数字很快就被移动到前面
- 时间复杂度o^1.3
复制代码// 希尔排序 int arr[] = {1,2,4,6,7,3,5,8,0,9}; //步数 for(int step = arr.length/2; step > 0;step/=2) { //遍历每个步数 for (int i = step; i < arr.length; i++) { int temp = arr[i]; int k; //插入排序 for (k = i-step;k>=0 && temp < arr[k]; k-=step) { arr[k+step] = arr[k]; } arr[k+step] = temp; } } System.out.println(Arrays.toString(arr));
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 希尔排序
int arr[] = {1,2,4,6,7,3,5,8,0,9};
//步数
for(int step = arr.length/2; step > 0;step/=2) {
//遍历每个步数
for (int i = step; i < arr.length; i++) {
int temp = arr[i];
int k;
//插入排序
for (k = i-step;k>=0 && temp < arr[k]; k-=step) {
arr[k+step] = arr[k];
}
arr[k+step] = temp;
}
}
System.out.println(Arrays.toString(arr));
```
快速：
- 将一个数作为参照数
- 左边遍历超过参照数交换，右边遍历小于参照物也交换
- 将小于参照数的一律放左边，大于参照数的一律放右边
- 左边的数组再次找出参照数继续拆分
  复制代码public static void main(String[] args) { //快速排序 int arr[] = {4,2,9,6,7,3,5,8,0,1}; quick(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quick(int[] arr, int i, int length) { if(i>length) { return; } //哨兵 int temp = arr[i]; int left = i; int right = length; while(left<right) { while(right>left&&arr[right]>=temp) { right--; } while(left<right&&arr[left]<=temp) { left++; } if(right>left) { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; } } arr[i] = arr[left]; arr[left] = temp; quick(arr,0,left-1); quick(arr,left+1,length); }
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
//快速排序
int arr[] = {4,2,9,6,7,3,5,8,0,1};
quick(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void quick(int[] arr, int i, int length) {
if(i>length) {
return;
}
//哨兵
int temp = arr[i];
int left = i;
int right = length;
while(left<right) {
while(right>left&&arr[right]>=temp) {
right--;
}
while(left<right&&arr[left]<=temp) {
left++;
}
if(right>left) {
int t = arr[left];
arr[left] = arr[right];
arr[right] = t;
}
}
arr[i] = arr[left];
arr[left] = temp;
quick(arr,0,left-1);
quick(arr,left+1,length);
}
```