数据结构复习1126排序

综述

  • 插入排序：直接插入，折半插入，希尔排序；
  • 交换排序：冒泡排序，快速排序；
  • 选择排序：简单选择，堆排序；
  • 2路归并
  • 基数排序
  • 外部排序
  • 算法分析

1.插入排序

1.1直接插入：
思想
  • 插入a，向前寻找比自己大的结点；
  • 将a保存在哨兵位置；
  • 边找边向后移动；
  • 将哨兵元素赋值给找到的结点
代码
void InsertSort(ElemType A[],int n)
{
int i,j;
for(i=2;i<=n;i++)
{
    A[0]=A[i];
    for(j=i-1;A[j]>A[0];j--) { A[j+1]=A[j]; }
    A[j+1]=A[0];
    注意最后一次循环，A[j+1]=A[j]执行结束后，再次执行j--；
    所以需要A[J+1];
}
}
复杂度：

S：O（1）；
T：O（n^2）;

1.2 折半插入：
思想：查找时用折半
代码：
void InsertSort(ElemType A[],int n)
{
int i,j,left,right,mid;
for(i=2;i<=n;i++)
{
  A[0]=A[i];
  left=1,right=i-1;
  while(left<=right)
 // 这里写成left<right则不稳定。等号是为了left和right相等时，继续向右搜索是否有相等元素，保持稳定性。
  {
    mid= (left+right )/2;
    if(A[mid]>A[0])right=mid-1;
    else left=mid+1;
    //A[mid]==A[0]为了保证稳定性，继续右移；
  }
出循环：则必有left>right。
  for(j=i-1;j>=left;--j) { A[j+1]=A[j] ;}
A[left]=A[0];
}  
}

复杂度：
S:O(1);
T:O(n^2), 查找为(nlog(2,n));移动为(O(n^2))取最大

1.3希尔排序

思想：
按dk分组，组内采用直接插入排序


image.png

代码：

void ShellSort(ElemType A[],int n)
{
int i,j,dk;
for(dk=n/w;dk>=1;dk=dk/2)
{
  for(i=dk+1;i<=n;i++)
    {
        if(A[i]<A[i-dk])
            {
                A[0]=A[i];
                for(j=i-dk;j>0&&A[i]<[j];j=j-dk) { A[j+dk]=[j] ;}
                A[j+dk]=A[0];
            }
    }
}
}
分析
  • 复杂度： S：1，T：n^2;
  • 稳定性：不稳定；
  • 适用性：直接插入（链表和顺序表都可以），希尔和折半（只可顺序）

2.交换排序

2.1冒泡排序

void BubbleSort(ElemType A[],int n)
{
  int flag;
  ElemType temp;
  for(int i=0;i<n;i++)
  {
    flag=0;
    for(int j=n-1;j>i;j--)
      {
          if(A[j]<A[j-1]])
          {
              temp=A[j];
              A[j]=A[j-1];
              A[j-1]=temp;
              flag=1;
          }
      }
      if(!flag) return;
  }
}

2.2快速排序

思想：
  • 根据二叉插入法，不难看出，即便搜索合适位置需要时间为Nlog(N),移动元素也需要N^2，因此想要优化时间复杂度，必须从移动元素和查询合适位置两方面双管齐下。
  • 快排基于分治法实现。
步骤：
  • partion函数：找到pivot，将当前序列分成两部分。
  • 递归分治。
  • partition函数思想：一遍二分查位置一遍移动。两个指针，若在后方出现小元素，复制到前指针；若前方出现大元素，复制到后指针。
代码：
void QuickSort(ElemType A[],int int left,int right )
{
int pivot=Partition(A,left,right);
QuickSort(A,left,pivot-1);
 QuickSort(A,pivot+1,right);
}

ElemType Partition(ElemType A[],int left,int right)
{
int pivot=A[left];
while(left<right)
  {
      while(left<right&&A[right]>pivot) right--;
      A[left]=A[right];
      while(left<right&&A[left]<pivot) left++;
      A[right]=A[left];  
  }
  A[left]=pivot;
  return left;
}
性能分析：
  • 时间复杂度：平均(nlog(n)),最坏(n^2)；
    若序列基本有序，快排将会较慢。
  • 稳定性：不稳定。

王道习题

1.双向冒泡

  • 循环判定条件写的比较巧妙: !flag&&left<right
void BubbleSort(ElemType A[],int n)
{
int left=0,right=n-1;
int flag;
while(!flag&&left<right)
{
  flag=0;
  for(int i=right;i>left;i--) 
  {
    if(A[i]<A[i-1]) { swap(A[i],A[j]); flag=1; }
  }
  left++;
  for(int j=left;j<right;j++)
  {
    if(A[j]>A[j+1]) { swap(A[j],A[j+1]; flag=1;) }
  }
  right--;
}
}
  1. 把所有奇数移动到偶数前面
  • 将序列分成偶数奇数并隔开，很容易想到快排；
  • 代码：
ElemType Partition(ElemType A[],int left,int right)
{
int pivot=A[left];
while(left<right)
  {
      while(left<right&&!(A[right]%2)) right--;
      A[left]=A[right];
      while(left<right&&A[left]%2) left++;
      A[right]=A[left];  
  }
  A[left]=pivot;
  return left;
}
  1. 随机快排
    思路
  • 取随机index j，swap(A[j],A[left])，再执行正常快排；
void RQSort(ElemType A[],int left,int right)
{
  int pivot=Partition(A,left,right);
  RQSort(A,left,pivot-1);
  RQSort(pivot+1,right);
}
int Partition(ElemType A[],int left,int right)
{
  int Rindex=rand(left-right)+left;
  swap(A[Rindex],A[left]);
  ELemType pivot=A[left];
  while(left<right)
  {
    while(left<right&&A[right]>pivot]) rigth--;
    A[left]=A[right];
    while(left<right&&A[left]<pivot) left++;
    A[right]=A[left];
  }
  A[left]=pivot;
  return left;
}
  1. 找到第k小的元素
  • 快排修改版，若左边的元素个数为k-1即pivot为所寻找的值
  • 代码
ElemType GetKth(ElemType A[],int left,int right)
{  
  Elem pivot=A[left];
  int low_temp=low,right_temp=right;
  while(left<right)
  {
    while(left<right&&A[right]>pivot]) rigth--;
    A[left]=A[right];
    while(left<right&&A[left]<pivot) left++;
    A[right]=A[left];
  }
  if(==k-1)return pivot;
  return pivot>k-1 ? GetKth(A,left_temp,left-1) : GetKth(A,left+1,right_temp);
}
  1. 将一个原序列划分为两个，数量差最小，类和差最大的子序列：
思想：
  • 快排中的partition的改变，让pivot接近n/2.ground；
代码:
void setPartition(int A[],int n)
{
  int pivot=A[0],left=0,right=n-1;
  int p=left;
  while(p!=n/2)
  {
    left=0,right=n-1;
    while(left<right&&A[right]>pivot) right--;
    A[left]=A[right];
    while(left<right&&A[left<pivot]) right++;
    A[right]=A[left];
    p=left;
  }
}

空间复杂度：O(1)
时间复杂度：O(n）

7. 荷兰国旗

题干：将乱序多个的红色，白色，蓝色条块排序成：红-白-蓝的荷兰国旗。（即红色的排在一起，白色的排在一起）
要求：时间复杂度为O(N)
思想：partition变体。
代码：

typedef enum color {red,blue,white}color;
void Flag_arrange(color a[],int n)
{
  int i=0,j=0,k=n-1;
  while(j<=k)
  {
    switch(a[j])
    {
      case(red): swap(a[i],a[j];i++;j++);break;
      case(white):j++;break;
      case(blue)  swap(a[j],a[k]);k--;break;
    }
  }
}

3.选择排序：简单选择排序+堆排序

3.1简单选择排序：
  • 思想 ：从子序列中找最小值（n），放入子序列最前端。子序列长度为1时停止。
  • 代码：
void SelectSort(ElemType A[],int n)
{
 int min=0,i=0,j=0;
 for(;i<n-1;i++)
    for(int j=i;j<n-1;j++)
        {
            if(A[j]<A[min])min=j;
        }
    if(j!=i) {swap(A[i],A[min]);}
}
3.2堆排序：
  • 思想：
    以大根堆为例，要建立一个根节点大于所有结点的树，T为O（n）；
    对堆排序的T为nlogn
  • 步骤：

对非叶节点(i<=len/2.ground)进行“下坠”操作，即HeadAdjust。
每次HeadAdjust比较次树不会超过2(h-i),即小于2log(2,n);
将顶点元素和末尾元素换位，重新排序（树结点数量减一）。
A[0]暂存最大值
重复上述步骤，直到得到一棵先序遍历结果为递增序列的树。

  • 建堆
Void BuildHeap(Elemtype A[],int len)
{
  for(int i=len/2;i>0;i--){HeadAdjust(A,i,len);}
}
void HeapSort(int A[],int len)
{
  BuildHeap(A,len);
  for(int i=len;i>1;i--)
  {
    swap(A[i],A[1]);
    HeadAdjust(A,1,i-1);
  }
}

下坠操作：

void HeadAdjust(int A[],int k,int len)
{
  A[0]=A[k];
  for(int i=2*k;i<=len;i=i*2)
  {
    if(i<len&&A[i]<A[i]+1)i++; //找到最大孩子；
    if(A[0]>A[k])break;  //若比最大孩子大，则k可以作为A[0]的存入点
    // else
    A[k]=A[i]; 否则，继续向下寻找存入点。// 同时将最大孩子上浮。
    k=i;
  }
  A[k]=A[0];
}

下坠操作的简图：


image.png

时间复杂度：4n（建堆）+nlog(2,n)（排序）

王道习题：
  1. 算法分析，取出第k个最小元素之前的部分有序序列，采用什么方法：
    简单选择排序：每次选择最小，时间复杂度为kn。（每趟选出一个最小，每趟为n）
    冒泡排序：每次选择最小，时间复杂度为kn
    堆排序：建堆的时间为4n，取k个最小的时间为klog2n，总时间为4n+log(2,n)。
    k和n很小时用简单排序/冒泡排序，k和n很大时，用堆排序。
  2. 单链表实现简单选择排序：
    思路：头插。
    代码:
void SelectSort(LinkList L)
{
Lnode* pre,*p,*tail,*s;
pre=L;
int flag;
while(pre!=null)
  {
    p=pre - > next,tail=p - > next;
    flag=0;
    while(tail!=null)
    {
      if(tail - > data<p  - > data) {p=tail;s=p;tail=tail - > next; flag=1; }
      else {tail=tail - > next;}
    }
      if(flag) break;
      s - > next=p - > next;
      p - > next=pre - > next;
      pre=p;
  }
}
  1. 判断小根堆
    思路：
  • A[0]为temp。关键字的范围是[1,n]
  • 对所有分支结点，判断其与子节点的关键字。

代码：

bool IsMinHeap(ElemType A[],int len)
{
  if(len%0==0)//偶数长度，则节点有奇数个。有一个但分支结点。
  {
    if(A[len]<A[len/2])return false;
    for(int i=len/2-1;i>=1;i--)
    {
      if(A[i]<A[i/2])return false;
    }
  }
 else
  {
      for(int i=len/2-1;i>=1;i--)
      {
        if(A[i]<A[i/2])return false;
      }  
  }
  return true;
}

4.归并排序和基数排序

4.1 归并排序
  • 思想
    分治
  • 代码：
void MergeSort(ElemType A[],int left,int right)
{
   if(left<right)
  {
    int mid=(left+right)/2;
    MergeSort(A,left,mid-1);
    MerseSort(A,mid,right);
    Merge(A,low,right,mid);
  }
}

ElemType *B=(ElemType*)malloc(sizeof((n+1)*ElemType));
void Merge(ElemType A[],int left,right,mid)
{
  for(int i=left;i<right;i++) { B[i]=A[i]; }
  int i,j,k;
  for( i=low,j=mid,k=i;j<=right;k++)
  {
    if(B[i]<B[j]){A[k]=B[i++];}
    if(B[i>=B[j]]){A[k=B[j++];}
  }
  while(i<=mid) { A[k++]=B[i++]; }
  while(j<=right) {  A[K++]=b[j++]; } //元素相等，覆盖后也相等，这里保证了排序的稳定性
}

C++：

vector<int> B(A.size(),0);
void MergeSort(vector<int>& A,int left,int right){
    int mid=(left+right)/2;
    MergeSort(A,left,mid);
    MergeSort(A,mid+1,right);
    Merge(A,left,right,mid);
}
void Merge(vector<int>& A,int left,int right,int mid){
    for(int i=left;i<right;i++) { B[i]=A[i]; }
    int i,j,k;
    for(i=left,j=mid,k=i;i<=right;k++){
        if(B[i]>B[j]){A[k]=B[i++];}
        else {A[k]=B[j++];}
    }
    while(i<=mid){A[k++]=B[left++];}
    while(j<=right){A[k++]=B[j++];}
}
4.2 基数排序

思想：

  • 不基于比较
  • 关键字位数相同（若不同，高位补零）
  • 高位优先：MSD
  • 低位优先：LSD

效率
空间O(R)
时间O(d(n+r))

5.算法分析

    1. 时空复杂度和稳定性：


      image.png
  • 2.阶段结果：（第n躺的结果）
    冒泡排序，堆排序，选择排序每趟可以产生最大值/最小值；
    快排每趟可以确定一个元素的最终位置。（即一次partition可以确定pivot的最终位置）
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容