排序算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法总结,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4385字,纯文字阅读大概需要7分钟。
内容图文
![排序算法总结](/upload/InfoBanner/zyjiaocheng/1298/a014f9fd3638429295de820ced599ce3.jpg)
本文将给出六大经典排序的实现。
简单排序算法:冒泡,插入,选择
改进排序算法:快排,归并,堆排
以下排序用到的交换函数:
void swap(int &A, int &B) {
int temp = A; A = B; B = temp;
}
1. 冒泡排序
2个相邻的元素相互比较,不满足顺序则交换;每遍历一次数组,使一个元素处于最终位置。
时间复杂度
void BubbleSort(int nums[], intleft, intright) {
if (nums == NULL || right-left+1 <= 0)
return;
for (int i = left; i < right; i++) {
for (int j = i+1; j <= right-(i-left); j++) {
if (nums[j] < nums[j-1]) {
swap(nums[j], nums[j-1]);
}
}
}
}
2. 插入排序
将一个元素插入到已经有序的数组中,从后向前比较,将大于它的元素后移一步,找到属于它的位置,最后插入。
时间复杂度
void InsertSort(int nums[], intleft, intright) {
if (nums == NULL || right-left+1 <= 0)
return;
for (int i = left; i < right; i++) {
int j = i+1;
int temp = nums[j];
for (; j > left; j--) {
if (temp >= nums[j-1])
break;
nums[j] = nums[j-1];
}
nums[j] = temp;
}
}
3. 选择排序
首先选出现有数组中的最小值,然后交换到现有数组的最前面,完成 1 个元素的排序。对后序数组选出最小值,重复以上操作。
时间复杂度
由于选择排序的交换次数少 O(n) ,因此关键字或者数据量大的数据数组,适用于选择排序。
void SelectSort(int nums[], intleft, intright) {
if (nums == NULL || right-left+1 <= 0)
return;
for (int i = left; i < right; i++) {
int min_value = nums[i];
int min = i;
for (int j = i+1; j <= right; j++) {
if (nums[j] < min_value) {
min_value = nums[j];
min = j;
}
}
swap(nums[i], nums[min]);
}
}
4. 归并排序
将数组平均分为2个部分,分别进行排序,然后将2个数组合并
时间复杂度
void Merge(int nums[], int left, int mid, int right);
void MergeSort(int nums[], int left, int right) {
if (nums == NULL || right <= left)
return;
int mid = (left+right) >> 1;
MergeSort(nums, left, mid);
MergeSort(nums, mid+1, right);
Merge(nums, left, mid, right);
}
void Merge(int nums[], int left, int mid, int right) {
int len = right - left + 1;
int* temp = newint[len];
int i = left, j = mid+1;
int k = 0;
while(i <= mid && j <= right) {
if (nums[i] <= nums[j])
temp[k++] = nums[i++];
else
temp[k++] = nums[j++];
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
// copyfor (k = 0; k < len; k++) {
nums[left+k] = temp[k];
}
delete temp;
}
5. 快速排序
随机在数组中选择一个元素,作为划分元素,将数组中比划分元素小的交换到左侧,比划分元素大的交换到右侧,最后将划分元素交换到左右区间的连接处,则划分元素处于了最终位置;递归地对左右区间进行快速排序。
时间复杂度
int Partation(int nums[], int left, int right) {
int number = nums[left]; // 选择第一个元素作为划分元素int i = left+1, j = right;
while(i < j) {
while (nums[i] < number)
i++;
while (nums[j] > number)
j--;
if (j <= i)
break;
swap(nums[i], nums[j]);
i++, j--;
}
swap(nums[left], nums[j]); //注:只能是j不能是i,举例易看出return j;
}
void QuickSort(int nums[], int left, int right) {
if (nums == NULL || left >= right)
return;
intindex = Partation(nums, left, right); // 划分元素最终处于的位置
QuickSort(nums, left, index-1);
QuickSort(nums, index+1, right);
}
6. 堆排序
将数组进行原位建堆,逐个将堆顶元素(最大值)交换到数组尾部,然后修复堆。
时间复杂度
void FixHeap(int nums[], int i, int n) {
if (nums == NULL || i < 0 || n <= 0)
return;
int temp = nums[i]; // 破坏元素int j = 2*i + 1; // i 节点的左子结点while (j < n) {
if (j+1 < n && nums[j+1] > nums[j]) // 找出较大的那个子节点
j++;
if (temp > nums[j])
break;
nums[i] = nums[j];
i = j; // 向下继续修复
j = 2*i + 1;
}
nums[i] = temp;
}
void HeapSort(int nums[], int left, int right) {
if (nums == NULL || right-left+1 <= 0)
return;
// 为了简单描述,假设数组是从下标0开始排序int n = right-left+1;
// 建堆,从n/2-1 ~ 0修复堆,n/2 ~ n-1 是叶节点for (int i = n >> 1 - 1; i >= 0; i--) {
FixHeap(nums, i, n);
}
for (int i = n-1; i > 0; i--) {
swap(nums[0], nums[i]);
FixHeap(nums, 0, i-1);
}
}
7. 其他排序算法
- 希尔排序: 插入排序的变形,一次可以前进不止一步;点击查看详细
- 线性排序:对于小范围的整数,适合采用O(n)时间复杂度的线性排序。
点击查看详细:线性排序之基数排序,桶排序,计数排序
8. 如何选择排序算法
参考《大话数据结构》:
从算法的简单性将排序算法分为:
- 简单算法:冒泡、插入、选择
- 改进算法:希尔、堆排序、归并排序、快排
- 从时间复杂度来看
- 从平均情况,后三种改进算法要胜过希尔排序,远胜简单算法
- 从最好情况(已经有序),冒泡和插入排序最优,改进算法最差
- 从最差情况(逆序),堆排序和归并排序最优,远胜快排和简单算法
- 从空间复杂度来看
- 简单算法都不占用额外空间。
- 堆排序是在数组上原位建堆,O(1);
- 快排因为递归栈占用,O(lgn)~O(n)递归深度;
- 归并,需要辅助数组O(n);
所以如果要求考虑内存空间,不能选快排和归并
- 从稳定性来看
归并排序最好。当然简单排序中的冒泡和插入也是稳定的,但同时考虑时间,则应选归并。 - 待排序的个数
待排序个数n越小,采用简单算法越合适;反之,n越大,选择改进算法。这也是快排中,对于小数组使用插入排序完成的原因。 - 待排序数据的关键字本身信息量的大小
如果信息量大,则交换的代价大。此时选择排序最优,先大量比较然后一次交换,O(n)次交换。
对于待排序个数不大,而关键字信息量大的情况,简单算法占优。
9. 源码下载
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/quzhongxin/article/details/47106497
内容总结
以上是互联网集市为您收集整理的排序算法总结全部内容,希望文章能够帮你解决排序算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。