十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数

简介: 十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数

1. 排序算法

1.1 算法的之间的比较

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定
插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(n*log2n) O(n2) O(log2n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定
归并排序 O(n*log2n) O(n*log2n) O(n) 稳定
希尔排序 O(n*log2n) O(n2) O(1) 不稳定
计数排序 O(n+m) O(n+m) O(n+m) 稳定
桶排序 O(n) O(n) O(m) 稳定
基数排序 O(k*n) O(n2) O(k+n) 稳定

1.2 冒泡排序

算法思想

  1. 比较相邻的元素,如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从第一对开始,一直到最后一对,做完后,最后的元素会是最大的元素。
  3. 针对所有的元素重复上面的步骤,除排序好的。
  4. 持续对越来越少的元素重复上述步骤,直到哪次没有任何一对数字需要比较或者是交换。


图解


代码

void bubbleSort(int a[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (a[j] > a[j + 1])
{
swap(a[j], a[j + 1]);
}
}
}
}

1.3 选择排序

算法思想

  1. 在未排序的序列中找到最小(大)元素,存放到排序序列的起始位置。
  2. 从剩下未排序元素中继续寻找最小(大)元素,然后放到自己已排序的序列的末尾。
  3. 以此类推,直到所有元素排序完毕。


图解


代码

void selectionSort(int a[], int len)
{
int min;
for (int i = 0; i < len - 1; i++)
{
min = i;
for (int j = i + 1; j < len; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
swap(a[i], a[min]);
}
}

1.4 插入排序

算法思想

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,该元素移到下一个位置。
  4. 重复步骤3,直到找到已排序的元素小于或者等于新的元素的位置。
  5. 将元素插入到对应位置。
  6. 重复2~5。


图解


代码

void InsertSort(int a[], int n)
{
for (int i = 1; i < n; i++)
{
if (a[i] < a[i - 1])
{
int val = a[i];
int j = i - 1;
a[j + 1] = a[j];
while (j > 0 && val < a[j - 1])
{
a[j] = a[j - 1];
j--;
}
a[j] = val;
}
}
}

1.5 快速排序

算法思想

  1. 选第一个数为标准。
  2. 将比基准小的数据交换到前面,比基准大的交换到后面
  3. 对左边的空间和右边的空间重复,直到各区间只有一个数字

图解

代码

void QuickSort(int a[], int left, int right)
{
if (left >= right)
return;
int begin = left;
int end = right;
//keyi定在右边,需要从左边开始找
int keyi = end;
int key = a[keyi];
 
while (begin < end)
{
//因为我们从小往大排 
//从左边开始找 找大
while (begin < end && a[begin] <= key)
begin++;
a[end] = a[begin];
 
//从右边开始找 找小
while (begin < end && a[end] >= key)
end--;
a[begin] = a[end];
}
a[end] = key;
 
QuickSort(a, left, end - 1);
QuickSort(a, end + 1, right);
}

1.6 堆排序

算法思想

  1. 如果要从小到大排序,建立大堆,根节点大于左右子树。
  2. 将根结和最后一个元素交换,并且树的元素个数减1。
  3. 重复1~2,直到只剩一个元素。


图解


代码

void AdjustDown(int* a, int n, int root)//n是大小,root是根节点的下标
{
int parent = root;
int child = parent * 2 + 1;
 
while (child < n)
{
//child指向左右孩子中最小的那个
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
 
void HeapPop(Heap* php)
{
assert(php);
assert(php->size > 0);
 
swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
 
AdjustDown(php->a, php->size, 0);
}

1.7 计数排序

算法思想

  1. 找出待排序的数组最大和最小的元素
  2. 统计数组中每个值为i的元素出现的个数,存入数组c的第i-min项
  3. 将下标+min的值根据在数组c中的个数存到原数组中。

图解


代码

void CountSort(int a[], int len)
{
int max = a[0];
int min = a[0];
for (int i = 0; i < len; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int l = max - min;//计算数组最大最小值的差
int* count_a = new int[l + 1];
for (int i = 0; i < l + 1; i++)
{
count_a[i] = 0;
}
 
for (int i = 0; i < len; i++)
{
count_a[a[i] - min]++;//统计元素个数
}
 
int j = 0;
for (int i = 0; i < len; i)
{
while (j <= l && count_a[j])
{
count_a[j]--;
a[i] = j + min;
i++;
}
j++;
}
}

1.8 桶排序

算法思想

  1. 设置一个定量的数组当作空桶;
  2. 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  3. 对每个不是空的桶进行排序;
  4. 从不是空的桶里把排好序的数据拼接起来。

图解


1.9 基数排序

算法思想

  1. 取得数组中的最大数,并取得位数。
  2. arr为原始数组,从最低位开始取每个位组成radix数组。
  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点)。


图解



1.10 希尔排序

算法思想

  1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk = 1。
  2. 按照增量序列个数k,对序列进行k趟排序
  3. 每趟排序根据对应的增量ti,将待排序的序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。

图解


代码

void ShellSort(int* a, int n)
{
printf("原数组->", gap);
PrintArray(a, n);
 
int gap = n;//间隔
while (gap > 1)
{
gap = gap / 3 + 1;//保证最后一趟一定为1
for (int i = 0; i < n - gap; i++)
{
int end = 0;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
 
a[end + gap] = tmp;
}
printf("gap:%d->", gap);
PrintArray(a, n);
}
}

1.11 归并排序

算法思想

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序;
  3. 将两个排序好的子序列合并成一个最终的排序序列。

图解


代码

void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left == right)
return;
 
//int mid = (left + right) >> 1;//有溢出风险
int mid = left + ((right - left) >> 1);
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
 
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int i = begin1;
 
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
 
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
 
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
 
//拷回原数组
int j = left;
while (j <= right)
{
a[j] = tmp[j];
j++;
}
}
 
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
相关文章
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
17 0
|
2月前
|
搜索推荐 算法
排序算法---冒泡&选择&插入总结
排序算法---冒泡&选择&插入总结
18 0
|
4月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
46 0
|
5月前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
39 5
|
6月前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
6月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
6月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
6月前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
32 0
|
7天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
4天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。