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

75 阅读 0 评论 50 点赞

我是靠谱客的博主个性歌曲，最近开发中收集的这篇文章主要介绍通俗易懂十大排序算法算法复杂度十大排序算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法复杂度

什么是算法的复杂度？

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

时间复杂度

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

常见的时间复杂度场景

O(1)—常数阶
Systemctl.out.println("1");

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");
}

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");
}
}

时间复杂度估算算法优劣的时候注重的是算法的潜力
- 有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));

选择：

假设第一位数就是数组中最小的数据，记录他的索引
依次与之后的数字相比较，如果出现比最小数组小的数字，重新记录索引

时间复杂度 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;
}
}

插入：

先将要插入的数字提取出来
每次向数列中提出一个数字，从当前位置开始向左比较
如果比其值小则索引位置向右移动，原来位置不做填充，作为一个“坑”，直到找到合适位置

最后如果将之前取出的数据填入坑中

插入排序

//插入排序
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));

快速：

将一个数作为参照数
左边遍历超过参照数交换，右边遍历小于参照物也交换
将小于参照数的一律放左边，大于参照数的一律放右边

左边的数组再次找出参照数继续拆分

快速排序

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);
}