[数据结构与算法]排序

基本概念

排序目的：将一组数据无序变有序

数学定义：
排序数学定义：假设含n个数据元素的序列为{ R1, R2, …, Rn} 其相应的关键字序列为{ K1, K2, …, Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ：Kp1≤Kp2≤…≤Kpn；按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …，Rpn}的操作称作排序

稳定性

如果在序列中有两个数据元素r[i]和r[j]，它们的关键字k[i] == k [j]，且在排序之前，对象 r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在r[j]前面，则称这个排序方法是稳定的；否则称这个排序方法是不稳定的。

关键操作

比较和交换
两个数据元素通过比较确定先后次序 交换后得到预期结果

内排序和外排序

内排序：整个排序过程不访问外存
外排序：待排序的数据元素数量大，整个排序过程不可能在内存中完成

排序审判

时间：比较和交换的数量

辅助存储空间：排序操作需要额外的存储空间 --空间换时间

选择法

首先通过n-1次关键字比较 从n个记录中找出关键字最小的记录 将它与第一个记录交换
再通过n-2次比较 从剩余的n-1个记录中找出关键字次小的记录，与第二个记录交换
重复上述操作 进行n-1次 结束

void selectSort(int array[],int len)
{
   int min;
   for(int i=0;i<len;i++)
   {
       min=i;
       for(int j=i+1;j<len;j++)
       if(array[min]>array[j])
       {
       //找到新的最小值 交换
           int temp=array[i];
           array[i]=array[j];
           array[j]=temp;
       }
   }
}

插入排序

基本思想

排序过程：整个排序过程为n-1次插入 首先将第一个记录看做一个有序子序列，依次将后面的n-1个数，分别插入到前面的有序序列中
实质：找到插入位置，执行n-1次插入操作

关键点

拿出一个元素，留出位置 符合条件的元素后移

代码

void InsertSort(int array[],int len)
{
    int i=0;
    int j=0;
    int k=-1;
    int temp=-1;
    for(i=1;i<len;i++)
    {
        k=i;//待插入位置
        temp=array[k];
        for(j=i-1;(j>0)&&(array[j]>temp);j--)
        {
            array[j+1] = array[i];//元素后移
            k=j;//k需要插入的位置
        } 
        array[k]=temp;//元素插入
    }
}

冒泡排序

基本思想

初次n-1次循环，自左至右 相邻两个元素依次比较 大者在后 结果：元素最大的排到最后
对前面n-1个元素进形上述循环，次大元素排到n-1的位置
…
重复n-1次
（相邻元素进行比较）

代码

void BubbleSort(int array[],int len)
{
     int i=0,j=0 ,exchange = 1;//表明数组是否已经排好序 0：排好  1：没有
     for(i=0;(i<len)&&exchange;i++)
     {
         exchange = 0;//认为已经排序完毕
              for(j=len-1;j>i;j--)
              {  
                  if(array[j]<array[j-1])
                  {
                      int temp=arary[j];
                      array[j]=array[i];
                      array[i]=temp;
                      exchange =1;
                  }
               }
     }
}

希尔排序（插入排序优化）

简单插入排序经过改进 也称缩小增量排序 数据分组进行排序

基本思想

把记录按下表的一定增量分组 没组直接插入排序算法排序 随着增量减少 每组包含的关键词越来越多 增量减至1时 整个文件被分为一组 算法终止

跳跃式分组 分组插入排序 缩小增量 直至为1
结果：在初始阶段 从宏观上看基本有序 而后微调 不会涉及过多的数据移动

代码

void ShellSort1(int array[],int len)
{
    int i=0;
    int j=0;
    int k=-1;
    int temp=-1;
    int gap = len;//步长
    do
    {
        gap = gap /3+1;  //步长递减     最优化
        for(i=gap;i<len;i+=gap)
        {
            k =i ;
            temp = array[k];
            for(j=i-gap;(j>=0)&&(array[j]>temp);j-=gap)
            {
                array[j+gap] = array[j];
                k=j;
            }
            array[k]=temp;
        }
    }while(gap>1);
}

void ShellSort2(int *array,int len)
{
    int gap = len;
    while(gap>0)
    {
        gap=gap/3+1;
        for(int i=0;i<gap;i++)
        {
         int tmp;
         int index;
         for(int j=i+gap;j<len;j+=gap)
         {
          tmp=array[j];
          index=j;
          for(int k=j-gap;k>=0;k-=gap)
          {
          if(tmp<arrayk])
              {
                  array[k+gap]=array[k];
                  index=k;
              }
           else break;
          }
         }
         array[index]=tmp;
        }
     }
}

快速排序

基本思想

通过一次排序 将待排序部分分割成独立的两部分 其中一部分记录的关键字均比另一部分记录的关键字小 然后按相同的方法操作两部分的记录 以达到整个序列有序
整个排序可以递归进行

代码

void QSort(int array[],int loe,int high)
{
    if(low<high）
     {
         int pivot = partition(array,low,high);
         QSort(array,low,pivot-1）；
         QSort(array,pivot+1,high);
     }
    
}
void QuickSort(int array[],int len)
{
    QSort(array,0,len-1);
}
int partition(int array[];int low;int high)
{
    int pv=array[low];
     
     while (low<high)
     {
         while((low<high)&&(array[high]>pv))
         {
             high--;
         }
         swap(array,low,high)
         while((low<high)&&(array[low] <= pv))
         {
             low++;
         }
         swap5(array,low,high);
     }
     //返回枢轴的位置
     return low;
}
void swap(int array[];int i;int j)
{
    int temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

归并排序

牺牲空间 达到稳定

基本思想

将两个或两个以上的有序序列合并成一个新的有序序列

2路归并：将2个有序序列归并为一个新的有序序列
3路归并、多路归并

void Merge(int src[],int des[],int low,int mid,int high)
{
    int i = low;
    int j = mid +1;
    int k = low;

     while((i<=mid)&&(j<=high))
     {
         if(src[i] < src[j])
         {
             des[k++] = src[i++];
         }
         else
         {
             des[k++] = src[j++];
         }
     }
     while( i<= mid)
     {
         des[k++] = src[i++];
     }

    while( j<=high)
    {
        des[k++] = src[j++];
    }
    
}

//每次分为两路 只剩下一个元素时 就不用再划分
void MSort(int src[],int des[],int low,int high,int max)
{
    if(low == high)
    {
        des[low] = src[low];
    }
    else
    {
        int mid = (low +high)/2;
        int *space = (int*)malloc(sizeof(int)* max);
        
        if(space!=NULL)
        {
            MSort(src,space,low,mid,max);
            MSort(src,space,mid+1,high,max);
            Merge(space,des,low,mid,high);
        }

        free (space);
    }
}
void mergeSort(int array[],int len)
{
    MSort(array,array,0,len-1,len);
}