冒泡排序

初级版冒泡排序

冒泡排序算法为一种比较排序算法(还有快速排序),较小的数字如同气泡般慢慢浮到上面,所以称为冒泡排序。为就地排序,稳定。
算法思想:两两比较相邻记录的关键字,如果反序则交换,知道没有反序的记录为止。

C++实现

/**********冒泡排序1--升序************/
void swap(ElemType a[],int i,int j)
{
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}

void BubbleSort1(ElemType a[],int n)
{
	int i,j;
	for (i = 0;i < n;i++)
		for(j = n-1;j > i;j--)
		{
			if(a[j-1] > a[j])
				swap(a,j-1,j);
		}
}
/**********冒泡排序3--降序************/
void BubbleSort3(ElemType a[],int n)
{
    int i,j;
    for (i = 0;i < n;i++)
        for(j = 0;j <n-i;j++)
        {
            if(a[j] < a[j+1])
                swap(a,j,j+1);
        }
}

优化版冒泡排序1–添加标记位

算法思想:设置一个标志,如果这一趟发生了交换,则为true,否则为false。如果有一趟没有发生交换,说明排序已经完成。

/**********冒泡排序2--升序************/
void BubbleSort2(ElemType a[],int n)
{
	int i,j;
	bool flag = true;
	while(flag)
	{
		flag = false;
		for (i = 0;i < n;i++)
			for(j = n-1;j > i;j--)
			{
				if(a[j-1] > a[j])
				{
					swap(a,j-1,j);
					flag = true;
				}
			}
	}
}
/**********冒泡排序4--降序************/
void BubbleSort4(ElemType a[],int n)
{
    int i,j;
    bool flag = true;
    while(flag)
    {
        flag = false;
        for (i = 0;i < n;i++)
            for(j = 0;j < n-i;j++)
            {
                if(a[j] < a[j+1])
                {
                    swap(a,j,j+1);
                    flag = true;
                }
            }
    }
}

优化版冒泡排序2–添加标记位并记录位置

算法思想:记录未排序最后位置的冒泡排序。在优化方法1的基础上再次进行改进,每次循环记录最后一次发生交换的元素的位置,这说明这之后的元素已经有序,下一次循环不用比较这些元素。

/**********冒泡排序5优化法二--升序************/
void BubbleSort5(ElemType a[],int n)
{
	int i,j;
	int flag;
	flag = n;
	while(flag > 0)
	{
		for (j = i = 0;j < flag && j+1 < n;j++)
		{
			if(a[j] > a[j+1])
			{
				swap(a,j,j+1);
				i = j;
			}
		}
		flag = i;
	}
}

优化版冒泡排序3–双向冒泡

算法思想:在优化方法2的基础上继续改进,每次循环不仅从前向后扫描记录最后一次发生交换的元素的位置up,而且从后向前扫描记录再次扫描记录最前面发生交换的元素的位置low,这样两侧的元素已经有序,当low>=up的时候证明整个数组有序。

/**********冒泡排序6优化法三--升序************/
void BubbleSort6(ElemType a[],int n)
{
	int low,high,i,index;
	low = index = 0;
	high = n;
	while(high > low)
	{
		for(i = low;i < high;i++)
			if(a[i] >a[i+1])
			{
				swap(a,j,j+1);
				index = i;
			}
		high = index;
		for(i = high;i > low;i--)
			if(a[i]<a[i-1])
			{
				swap(a,i,i-1);
				index = i;
			}
		low = index;
	}
}

优化的冒泡排序算法的时间复杂度:
最好的情况下,时间复杂度为O(n)。
最坏的情况下,时间复杂度为O(n^2)。

python实现

#----------------#
#--Bubble sort1--#
#----------------#
def swap(arr,i,j):
		tmp = arr[i]
		arr[i] = arr[j]
		arr[j] = tmp

def bubble_sort1(arr):
		arrlen = len(arr)
		for i in range(arrlen):
				for j in range(arrlen-1):
						if arr[j] > arr[j+1]:
								swap(arr,j,j+1)

#----------------#
#--Bubble sort2--#
#----------------#
def bubble_sort2(arr):
		flag = True
		arrlen = len(arr)
		while flag:
				flag = False
				for i in range(arrlen):
						t = arrlen - i -1
						if t >=0 and t-1 >=0 and arr[t]<arr[t-1]:
								swap(arr,t,t-1)
								flag = True

Leave a Reply

Your email address will not be published. Required fields are marked *