0、我先把交换2个整型变量的代码单独拿出来，这样使排序的逻辑更简洁清晰。
#define SWAP_INT(a,b) {a = a ^ b; b = a ^ b; a = a ^ b;}
但是a和b必须要是不同的变量，如果a和b是同一块空间就GG了。
1、冒泡排序（Bubble Sort）
（1）描述
比较两个相邻的元素，将最大的元素交换至最右端。
也可以换一个方向冒泡，将最小的元素交换至最左端。
（2）实现
void bubble(int data[], int length)
{
int i, k;
for (i = 0; i < length-1; ++i)
for (k = 0; k < length-i-1; ++k)
if (data[k] > data[k+1])
SWAP_INT(data[k], data[k+1])
}
冒泡排序是一种比较简单的，最不容易写错的排序，主要是2层循环和1个判断，写代码的时候几乎不会出错。
唯一需要注意的是循环的边界。外层循环控制排序的轮数，一共需要n-1轮，因为当n-1轮完成之后，已经全部有序，不需要第n轮了。 内层循环控制每一轮需要比较的次数，因为有序的部分已经不用比较了，需要比较(n-1)-i次。
但是代码光这样还不行，最好最坏的时间复杂度相同，都是 O(n2) ，都说冒泡排序的最好时间复杂度是 O(n)，要达到这个效果，还需要加一个标记，如果本轮排序没有交换元素，说明数据已经全部有序，不用再继续下一轮。
void bubble2(int data[], int length)
{
int i, k;
int complete;
for(i = 0; i < length-1; ++i)
{
complete = 1;
for(k = 0; k < length-i-1; ++k)
{
if(data[k] > data[k+1])
{
SWAP_INT(data[k], data[k+1])
complete = 0;
}
}
if(complete)
break;
}
}
代码链接.
另外，如果待排序的数据不是保存在数组中，而是链表中，实现见代码链接。
(3)时间复杂度
时间复杂度有最坏时间复杂度、平均时间复杂度、最好时间复杂度。
最好的情况通常意义不大，即使说该算法至少运行1秒，也无法保证他不会运行到1年，除非确定数据在排序之前已经存在某种规律；而最坏的情况，意味着对用户的承诺，不会有更坏的情况了。
第1层循环有 n-1 次；第2层循环的第1轮是 n-1次，第2轮是 n-2次，直到第n-1轮是1次。根据等差数列求和公式：
所以
去掉低阶项、以及最高阶前面的系数，时间复杂度是O(n2) 。
因为时间复杂度关注的是时间的增长，而不是实际运行时间。
当 n 趋向于无穷大，O(n2) 一定会战胜 O(n3)，无论其他项是什么，都不能改变这个结果。
- 最好时间复杂度 O(n)
- 最坏时间复杂、平均时间复杂度 O(n2)
(4)空间复杂度 O(1)
因为运行时所耗费的存储空间，不是问题规模 n 的函数，而是一个常数。
(5)稳定性：稳定
如果相等的数据经过排序后的相对顺序保持不变，则表示该排序算法是稳定的。
冒泡排序的交换发生在相邻的两个元素之间。如果两个元素次序相反才会交换，相等的元素不会交换，所以相同元素的前后顺序并没有改变。
2、快速排序（Quicksort）
(1)描述
将待排序数据分成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后对两边的数据分别快速排序。
(2)实现
先从待排序数据中随便找（比如第1个）一个哨兵元素median，
从右至左，找到一个小于median的数 data[j]，
再从左至右,找到一个大于median的数 data[i]，
交换两个数，再继续进行，直到 i==j。
此时 i 左边的数都<=median，i 右边的数都>=median，
此时的 data[i] 是<= median的， 所以交换 data[i] 与 median，
再分别对左边和右边进行快速排序。
当 left >= right 时，说明这个区间的数据已经有序。
void quick(int data[], int left, int right)
{
int i = left;
int j = right;
int median = data[left];
if (left >= right)
return;
while (j > i)
{
while (j > i && data[j] >= median)
{
--j;
}
while (j > i && data[i] <= median)
{
++i;
}
if (i != j) // 千万别异或自己
{
SWAP_INT(data[i], data[j])
}
}
data[left] = data[i];
data[i] = median;
quick(data, left, i-1);
quick(data, i+1, right);
}
代码链接.
递归的代码简洁清晰，但是递归的次数受栈大小的限制。
通常当循环的结束条件不易表达时，我们使用递归；
如果循环写起来并不难，可以考虑使用循环。
为了使代码更简洁，这里不自定义栈结构，直接使用STL的stack，和递归没有本质的区别，只是把栈空间换成堆空间防止栈溢出：
void quick(int data[], int left, int right)
{
stack<int> leftstack;
stack<int> rightstack;
leftstack.push(left);
rightstack.push(right);
while (leftstack.size() > 0)
{
left = leftstack.top();
leftstack.pop();
right = rightstack.top();
rightstack.pop();
int i = left;
int j = right;
int median = data[left];
if (left >= right)
{
continue;
}
while (j > i)
{
while (j > i && data[j] >= median)
{
--j;
}
while (j > i && data[i] <= median)
{
++i;
}
if (i != j) // 千万别异或自己
{
SWAP_INT(data[i], data[j])
}
}
data[left] = data[i];
data[i] = median;
leftstack.push(left);
rightstack.push(i-1);
leftstack.push(i+1);
rightstack.push(right);
}
}
代码链接.
如果用C语言的话，可以考虑用链表.或数组.来模拟栈，如果使用链表可以用的时候再分配空间，如果使用数组就需要一开始malloc一个足够大的最坏情况的空间。
待排序数据保存在链表的代码。
(3) 时间复杂度
代码大致分为1个while循环以及2个递归。 循环部分的时间复杂度是 O(n) 。
递归部分看2个极端情况：
- 假设每次把数据划分两半都是均匀的，一共需要 x 次，形状就像是一颗平衡二叉树， 2x = n，x = log2n ，
根据对数的换底公式：
以及底数与真数互换公式
得出：
而 log210是一个常数，可以去掉，所以在复杂度计算中 log2n 与 log10n 是等效的，只是系数不同，影响并不大。
所以这里的时间复杂度是 O(logn) 。 - 假设每次把数据划分两半都是极端不均匀的：一边只有
1个数据，另一边有n-1个数据，比如待排序的数是逆序或者顺序，则运行时间是线性的，复杂度是 O(n) ，退化为冒泡排序。
- 最好时间复杂度、平均时间复杂度： O(nlogn) ；
- 最坏时间复杂度： O(n2) 。
(4)空间复杂度 O(logn)
每次递归需要分配空间来保存一些数据。
- 最好、平均空间复杂度为 O(logn) ；
- 最坏空间复杂度为 O(n) 。
(5)稳定性：不稳定
在哨兵元素和第i个元素交换的时候，很可能把前面的元素的稳定性打乱。
网友评论