数据结构学习小记9排序2
冒泡排序
由此过程可以看出冒泡排序是稳定排序，每次交换相邻的两个逆序元素
【算法描述】
版本一：
void BubbleSort(SqList &L)
{
m=length-1;flag=1;
while((m>0)&&(flag==1))
{
flag=0;
for(j=1;j<=m;j++)
if(L.r[j].key>L.r[j+1].key)
{ flag=1;//flag置为1，说明本趟排序发生了交换
t=L.r[j];
L.r[j]=L.r[j+1];
L.r[j+1]=t;
}
--m;
}
}
版本二：
n个元素使用冒泡排序法排序
存储数据的数组为nums[n]
//优化算法：最多进行 n-1 轮比较
for(i=0; i<n-1; i++){
for(j=0; j<n-1-i; j++){
if(nums[j] > nums[j+1]){
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
时间复杂度：O(n^2); 空间复杂度：O(1)
链式结构和顺序结构都适用，当数据较多且无序时此法不适用
冒泡排序改良为快速排序，快速排序通过两个不相邻的元素消除逆序，一次交换消除多个逆序，分而治之的方法
其中，一趟快速排序的过程如下:
【算法描述】
int Partition(SqList &L, int low, int high)
{//仅仅只是一趟快速排序，不是全过程
L.r[0]=L.r[low];
pivotkey=L..r[low].key;//用第一个记录做枢纽记录
while(low<high)
{while(low<high&&L.r[high].key>=pivotkey)
--high;
L.r[low]=L.r[high]//比枢纽记录小的移到低端
while(low<high&&L.r[low].key<=pivotkey)
++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort(SqList &L, int low,int high)
{low=1;high=L.length;
if(low<high)
{pivotloc=Partition(L,low,high);//将序列一分为二，pivotloc是枢纽位置
QSort(L,low,pivotloc-1);//对左子表进行递归排序
QSort(L,pivotloc+1,high);//对右子表进行递归排序
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
【算法分析】
时间复杂度：平均情况下，为O(nlog2n);
空间复杂度：最好情况下为O(log2n),最坏情况下为O(n).
【算法特点】
1适合用于顺序结构，很难用于链式结构
2.适合初始记录无序，N较大的情况
简单选择排序
（）中为排好序的序列，在（）外的序列中选择最小的一个插入()中
【算法描述】
void SelectSort(SqList &L)
{
for(i=1;i<L.length;++i)
{k=i;
for(j=i+1;j<=L.length;++j)
if(L.r[j].key<L.r[k].key) k=j;//k指向最小的记录
if(k!=i)
{t=L.r[i];
L.r[i]=L.r[k];
L.r[k]=t;
}
}
}
【算法分析】
时间复杂度：O(n^2) 空间复杂度：O(1)
本身为稳定排序，可用于链式结构，当每一记录占用的空间较多的时候，该方法比直接插入法快。
堆排序：
（1）调整堆
void HeapAdjust(SqList &L,int s,int m)
{
rc=L.r[s];
for(j=2*S;j<=m;j*=2)
{if(j<m&&L.r[j].key<L.r[j+1].key) ++j;
if(rc.key>=L.r[j].key) break;
L.r[s]=L.r[j];s=j;
}
L.r[s]=rc;
}
（2）建初堆
void CreateHeap(SqList &L)
{
n=L.length;
for(i=n/2;i>0;--i)
HeapAdjust(L.i,n);
}
（3）堆排序
void HeapSort(SqList &L)
{CreateHeap(L);
for(i=L.length;i>1;--i)
{x=L.r[1];
L.r[1]=L.r[i];
L.r[i]=x;
HeadAdjust(L,1,i-1);
}
}
时间复杂度：O(nlog2n)平均复杂度和最坏情况下接近
空间复杂度：O(1)
是不稳定排序，只能用于顺序结构，记录数较少时不宜采用
归并排序：
将当前序列一分为二，将两个子序列分别递归再进行归并排序，再将排序好的两个子序列归并为一个有序的序列
【算法描述】
void MSort(RedType R[],RedType T[],int low,int high)
{if(low==high) T[low]=T[high];
else
{mid=(low+high)/2;
MSort(R,S,low,mid);
MSort(S,T,low,mid,high);
}
}
void Merge(SqList &L)
{MSort(L.r,L.r,1,L.length)
}
时间复杂度：O(nlog2n)
空间复杂度：O(n)
随着专栏日结束我的随笔小记也就告一段落了，数据结构的其他部分我就自己看书做题摸索了，下次希望能给看官带来更好的作品
