冒泡排序的、选择排序和快速排序的最坏算法复杂度分别是什么?
(n*n),(n*n),nlog2n
时间复杂度是度量算法执行的时间长短,而空间复杂度是度量算法所需存储空间的大小。
算法的时间复杂度记做:T(n)=O(f(n))
在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1、Log2n、n、nLog2n、n的平方、n的三次方、2的n次方、n!),找出后,f(n)=该数量级,如冒泡排序的时间复杂度为T(n)=O(n*n)。
一、冒泡(Bubble)排序
冒泡排序(BubbleSort)的基本思想是:依次比较相邻的两个数,将小数放在前面,大数放在后面。如此重复下去,直至最终完成排序。
时间复杂度为O(n*n),适用于排序小列表。
void BubbleSortArray()
{
int i,j,temp;
for(i=1;i<n;i++)
{
for(j=0;i<n-i;j++)
{
if(a[j]>a[j+1]) //比较交换相邻元素
{
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
二、选择排序
选择排序的基本思想是:每一趟从待排序的数据元素中选出最小的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
时间复杂度为O(n*n),适用于排序小列表。
void SelectSortArray()
{
int i,j,min_index;
for(i=0;i<n-1;i++)
{
min_index=i;
for(j=i+1;j<n;j++) //每次扫描选择最小项
if(arr[j]<arr[min_index]) min_index=j;
if(min_index!=i) //找到最小项交换,将这一项移到列表中的正确位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
三、快速排序
快速排序(Quicksort)是对冒泡排序的一种改进,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
时间复杂度为O(nlog2n),适用于排序大列表。
void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low]; //采用子序列的第一个元素作为枢纽元素
while (low < high)
{
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素
while (low < high && arr[high] >= pivot)
{
--high;
}
swap(arr[low], arr[high]);//将这个比枢纽元素小的元素交换到前半部分
//从前往后在前半部分中寻找第一个大于枢纽元素的元素
while (low <high &&arr [low ]<=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分
}
return low ; //返回枢纽元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low <high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
分享到:
相关推荐
NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1871731
* 冒泡排序: * 每次在无序队列里将相邻两个数一次进行比较, * 将小数调到前面,逐次比较,直至将最大的数移到 * 最后。将剩下的N-1个数继续比较,将次大数移至 * 倒数第二位。
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
算法设计——排序代码——冒泡排序代码
冒泡排序相邻元素两两进行比较,每次比较结束都得到数组中最大的元素#冒泡排序def bubblesort(bubbleList): #外层循环,整个数组的长度 flag = True n = len(bubbleList) while(n): #内层循环,相邻两个数之间进行...
本文介绍了学习各种语言时,经典的几种算法的详细说明,对我们初学者应该有很大的帮助! 本资源为转载,版权属原作者!
常用排序算法总结——数据结构
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
Python排序算法详解 Python排序算法——冒泡排序 Python排序算法——插入排序 Python排序算法——选择排序 Python排序算法——快速排序 Python排序算法——归并排序
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
NULL 博文链接:https://yuyongjia.iteye.com/blog/1646657