排序

排序用到的数据结构：

#define MAXSIZE 10
typedef struct
{
int r[MAXSIZE+1];//用于存储要排序数组，r[0]用作临时变量
int length;//用于记录顺序表的长度
}SqList;

void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}

冒泡排序一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。

void BubbleSort0(SqList *L)
{
int i,j;
for(i=1;i<L->length;j++)
{
   for(j=i+1;j<L->length;j++)
    {
       if(L->r[i]>L->r[j])
{
        swap(L,i,j);//交换L->r[i]和L->r[j]的值
}
}
}
}

这个算是简单的交换排序，算法效率非常低。正宗的冒泡排序：

void BubbleSort(SqList *L){
int i,j;
for(i=1;i<L->length;i++)
{
for(j=L->length-1;j>=i;j--)
  {
      if(L->r[i]>L->r[j+1])//若前者大于后者注意跟上一个算法的差异
      {swap(L,j,j+1;)}
}
}
}

冒泡排序优化：主要是由一些序列不需要全部都比较

void BubbleSort2(SqList *L)
{
int i,j;
Status flag=TRUE;
for(i=1;i<L->length && flag;i++)//若flag为true则推出循环
{
flag=FALSE;
for(j=L->length-1;j>=i;j--)
{
  if(L->r[j]>L->r[j+1])
   {
    swap(L,j,j+1);
    flag=TRUE;//如果有数据交换则flag为true
}
}
}
}

冒泡排序法最坏情况下时间复杂度O(n的平方)

 

简单选择排序法就是通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，冰河第i（1《i《n）个记录交换之。

void SelectSort(SqList *L)
{
int i,j,min;
for(i=1;i<L->length-1;i++)
{
  min=i;
  for(j=i+1;j<L->length-1;j++)
{
   if(L->r[min]>L->r[j])//如果由小于当前最小值的关键字
      min=j;//将此关键字的下标赋值给min
}
if(i!=min) //若min不等于找到最小值进行交换
swap(L,i,min);
}
}

简单选择交换与交换完全雷同，简单交换是下标进行交换，所用的时间复杂度为O(n的平方)。在性能上要略优于冒泡排序。

 

直接插入排序的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录数增1的有序表。

void InsertSort(SqList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if(L->r[i]<L->r[i-1])
{
L->r[0]=L->r[i];//设置哨兵
for(j=i-1;L->r[j]>L->r[0];j--)
  L->r[j+1]=L->r[j];//记录后移
L->r[j+1]=L->r[0];//插入到正确位置
}
}
}

直接插入排序复杂度分析最坏的情况：n*n/4   复杂度：O(n的平方)

 

 

希尔排序法：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结构是基本有序而不是局部有序。

//对顺序表L作希尔排序
void ShellSort(SqList *L)
{
int i,j;
int increment=L->length;
do{
  increament=increament/3+1;
  for(i=increment+1;i<=L->length;i++)
{
  if(L->r[i]<L->r[i-increment])
{
  L->r[0]=L->r[i];
for(j=i-increment;j>0&&L->r[0]<L->r[j];j-=increment)
L->r[j+increment]=L->r[j];//记录后移，查找插入位置
L->r[j+increment]=L->r[0;]
}
}
}
while(increment>1);
}

当增量序列为dlta[k]=2t-k+1-1(02(n+1))可以获得不错的效果，时间复杂度为O(n的3/2方)

 

 堆排序的时间复杂度为O(nlogn)。由于堆排序堆原始记录的排序的状态不敏感，因此无论最好、最坏和平均时间复杂度均为O(nlogn)

归并排序复杂度的总的时间复杂度为O(nlogn)，空间复杂度O(n+logn)

快速排序基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别肚带这两部分记录继续进行排序，已达到整个序列有序的目的。

void QuickSort(SqList *L)
{
QSort(L,1,L->length);
}

void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high){
pivot=Partition(L,low,high);、、将L->r[low..high]一份为二
QSort(L,low,pivot-1);//对低子表递归排序
QSort(L,pivot+1,high);//对高子表递归排序
}
}