1.冒泡排序

1.1代码实现

//插入排序  O(N)~O(N^2)
//冒泡排序  O(N)~O(N^2)
//当数据有序 二者均为O(N)
//当数据接近有序或局部有序 插排更优
void BubbleSort(int* a, int n)
{
	assert(a);
	int flag = 1;
	for (int i = 0; flag && i < n - 1; ++i)
	{
		flag = 0;
		for (int j = 0; j < n - 1 - i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j - 1], &a[j]);
				flag = 1;
			}
		}
	}
}

1.2复杂度

1. 最坏：
   比较n-1轮
   每一轮比较次数：n n-1 n-2 n-3 … 1 ≈ N^2
2. 最优：
   比较n-1轮
   数据有序–每一轮只判断不比较 – N

2.快速排序

2.1人物及思想介绍【源于百度】

2.2hoare【霍尔】版本

1.初识代码

//快速排序   O(N * logN)
void QuickSort(int* a, int b, int e)    
{
	//b--begin：左区间左边界下标 
	//e--end  ：右区间右边界下标
	//b==e:数据量=1 无需排序 直接返回
	//b>e :无效区间 无需排序 直接返回
	if (b >= e)
		return;

	int left = b, right = e, x = left;
	while (left < right)
	{
		//右找小
		while (left < right && a[right] >= a[x])
			--right;

		//左找大
		while (left < right && a[left] <= a[x])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[x], &a[left]);
	x = left;

	// [b, x - 1] x [x + 1, e]
	QuickSort(a, b, x - 1);
	QuickSort(a, x+1, e);
}

2.代码分析

3.思其因果

Q：为什么a[x]【作为基准值key】置于左侧 – 右边先移动？
A：目的是为了保证相遇位置的值<=key 从而把key与相遇值交换 不打乱“左放小，右放大”的思想

3.相关博客

点击 qsort与bubble之间不为人知的关系 查看博主之前关于分析这两个排序的博客。