交换排序
一、冒泡排序
二、快速排序
冒泡排序：
（一）简单冒泡排序
void BubbleSort0(SqList &L)
{
for(int i=1;i<L.len;i++)
for(int j=i+1;j<=L.len;j++)
if (L.elem[i].key > L.elem[j].key)
swap(L.elem,i,j);
}
存在的问题：
不符合“两两比较相邻记录”思想，不是标准冒泡排序。
每轮只将最小记录移到合适位置，但对下轮排序无帮助。
标准冒泡排序：
void BubbleSort0(SqList &L)
{
for(int i=1;i<L.len;i++)
for(int j=L.len-1;j>=i;j--)
if (L.elem[j].key > L.elem[j+1].key)
swap(L.elem,j,j+1);
}
标准冒泡优化：
增加flag避免无效排序
void BubbleSort0(SqList &L)
{
flag =1;
for(int i=1;i<L.len && flag;i++)
{
flag = 0;
for(int j=L.len-1;j>=i;j--)
if (L.elem[j].key > L.elem[j+1].key)
{ swap(L.elem,j,j+1);
flag = 1;}
}
性能分析：
时间复杂度 最好情况O(n)
本身有序： n-1 次数据比较、无数据移动。
最坏情况
比较次数： （n-1）+（n-2）+...+1 = 1/2 n² - 1/2n
移动次数：每次交换需要3次数据移动，但与比较次数相同数量级。
时间复杂度 O(n²)
假设最好最坏等情况都是等概率出现，则
比较次数：O(n²)
移动次数：O(n²)
空间复杂度
数据交换时：只需1个周转空间O(1)
算法稳定性
关键字交换：顺序进行 稳定
快速排序
交替震荡逼近法
划分思路
选取枢轴关键字，一般选择第一个数据。
从高位向前搜索第一个关键字小于枢轴的记录，移到低空位。
从低位向后搜索第一个关键字大于枢轴的记录，移到高空位。
算法实现 快速划分算法
int Partition(SqList & L, int low,int high)
{
L.elem[0] = L.elem[low];
while(low < high){
while(low < high && L.elem[high].key >= L.elem[0].key)
high--;
swap(L.elem,low,high)
while(low < high && L.elem[low].key <= L.elem[0].key)
low++;
swap(L.elem,low,high)
}
Lelem[low] = L.elem[0];
return low;
}
递归排序算法
void QuickSort(SqList &L,int low,int high)
{
if(low<high)
{
pivot = Partition(L,low,high);
QuickSort(L,low,pivot-1);
QuickSort(L,pivot+1,high);
}
}
算法性能分析
时间复杂度
最好情况：定性分析 nlogn
可以看作是完全二叉树logn
应为每一层有n个数据
所以n*logn
最差情况：定性分析
O(n²）
空间复杂度：
最好情况：log2n层调用，O(logn)
最坏情况：n-1层调用，O(n)
平均性能O(logn)
排序稳定性
关键字比较和交换：跳跃进行 不稳定
快速算法优化
枢轴改进：随机位置法、三数取中法
其他改进：小数组时优化 引入插入排序
递归过程优化 尾递归：迭代替代递归
void Qsort(SqList &L,int low,int high){
if((high - low) > MAX_INSERT_SORT_LEN){
while(low<high){
pivot = Partition(L,Low,high);
Qsort(L,Low,pivot-1);
low = pivot +1;
}
}else InsertSort(L,low,high);
}
总结
基本思想：两两数据比较，逆序则交换，直到无逆序为止。
冒泡排序：交换策略：两两比较相邻记录。
优化策略：若某轮无交换，则全局有序。
时间复杂度：O(n2)，空间复杂度：O(1)
稳定性：稳定
快速排序：
交换策略：枢轴关键字分治数据集
优化策略：枢轴选取优化+小数据集优化+尾递归优化。
时间复杂度：O(n* logn)，空间复杂度：O(logn)
稳定性：不稳定