首页 / 算法 / 八大经典算法之冒泡算法、快速算法
八大经典算法之冒泡算法、快速算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了八大经典算法之冒泡算法、快速算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1596字，纯文字阅读大概需要3分钟。
内容图文
03 冒泡排序(Bubble Sort)
每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来。
void bubbleSort(int arr[],int n)
{
bool swapp = true;
while(swapp){
swapp = false;
for (int i = 0; i < n; i++) {
if (arr[i] > a[i+1] ){
a[i] += a[i+1];
a[i+1] = a[i] - a[i+1];
a[i] -=a[i+1];
swapp = true;
}
}
}
}
空间效率：O(1)
时间效率：最好情况：O(n) 平均情况：O(N^2) 最坏情况：O(N^2)
稳定性（相同元素相对位置变化情况）：稳定
04 快速排序（Quick Sort）
快排是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。
根据实现算法的不同，元素的选择一般有如下几种：
1. 永远选择第一个元素
2. 永远选择最后一个元素
3. 随机选择元素
4. 取中间值
int partition(int arr[], int low, int high){
int tmp = arr[low];
while (low < high) {
while (low < high && arr[high] >= tmp) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= tmp) {
low++;
}
arr[high] = arr[low];
}
arr[low] = tmp;
return low;
}
void quick_sort(int arr[], int low, int high){
if(low < high){
int pivotpos = partition(arr,low,high);
quick_sort(arr,low,pivotpos-1);
quick_sort(arr,pivotpos+1,high);
}
}
算法导论中提供了另一种 partition 的思路
int partition(int arr[], int low, int high){
int pivot = arr[high];
int i = low - 1;
for(int j = low; j <= high - 1; j++){
if(arr[j] <= pivot){
i++;
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i+1);
}
空间效率：最好情况: O(log2(N+1)) 平均情况 : O(log2N) 最坏情况 ： O(log2N)
时间效率：最好情况：O(Nlog2N) 平均情况：O(Nlog2N) 最坏情况：O(N2)
稳定性（相同元素相对位置变化情况）：稳定
原文：https://www.cnblogs.com/wanghao-boke/p/10421133.html
内容总结
以上是互联网集市为您收集整理的八大经典算法之冒泡算法、快速算法全部内容，希望文章能够帮你解决八大经典算法之冒泡算法、快速算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。