当前位置： java冒泡排序和复杂度-冒泡 排序
时间复杂度是度量算法执行的时间长短，而空间复杂度是度量算法所需存储空间的大小。
算法的时间复杂度记做：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 {
for(j=0;i {
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 {
min_index=i;
for(j=i+1;j if(arr[j] if(min_index!=i)//找到最小项交换java冒泡排序和复杂度，将这一项移到列表中的正确位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
三、快速排序
快速排序（Quicksort）是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小java冒泡排序和复杂度，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度为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 {
++low ;
}
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分
}
return low ;//返回枢纽元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low {
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
上一篇 
