排序算法(下)

排序算法(下)

预览
本文涉及到 插入排序 快速排序 堆排序


插入排序

玩扑克牌一样的插入排序法:

栗题

输入一个数,插入一个各元素已经按照升序排列的数组中,插入后使数组中元素仍然是按照升序排列的。

思想

把欲插入的数与数组中各数逐个比较, 当找到第一个比插入数大的元素i时,该元素之前即为插入位置。然后从数组最后一个元素开始到该元素为止,逐个后移一个单元。最后把插入数赋予元素a[i]即可。如果被插入数比所有的元素值都小则插入最前位置。

实现

#include <iostream>
using namespace std;
void main()
{
    int    m, i, j;
    int    a[11] = { 2, 6, 7, 9, 13, 16, 19, 21, 25, 29 }; 
 
    cin>>m;
    for ( i = 0; i < 10; i++ )
    if ( m < a[i] ) break;
        for ( j = 9; j >= i; j-- )
            a[j + 1] = a[j];
    a[i] = m;
    for ( i = 0; i < 11; i++ )
        cout<<a[i]<<' ';
}

通用的插入排序代码

把这个题推广到数组,把数组后面的元素插入到有序区中即是插入排序法

#include<stdio.h>  
  void InsertionSort(int *num,int n)   
  {  
    int i = 0;  
    int j = 0;  
    int tmp = 0;  
    for(i = 1;i<n;i++)  
    {  
      tmp = num[i];//从待插入组取出第一个元素。   
      j = i-1; //i-1即为有序组最后一个元素(与待插入元素相邻)的下标   
      while(j>=0&&tmp<num[j])  //注意判断条件为两个,j>=0对其进行边界限制。第二个为插入判断条件   
      {  
        num[j+1] = num[j];//若不是合适位置,有序组元素向后移动   
        j--;   
      }  
      num[j+1] = tmp;//找到合适位置,将元素插入。   
    }  
  }  
  int main()   
  {  
    int i = 0;  
    int num[8]={9,3,4,2,6,7,5,1};  
    InsertionSort(num,8);   
    /*这个函数必须知道元素的个数,所以将元素个数传入。 
    有心者可以在函数内部用sizeof求出元素个数 */  
    for(i=0;i<8;i++)  
    {  
        printf("%d ",num[i]);  
    }  
    return 0;  
  }

快速排序

快速排序(Quicksort)是对冒泡排序算法的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。(百度百科)

思想:

1.选定一个基准值(一般使用数组第一个值或者最后值,我们取第一个值)

2.基于这个值,将数组分为两部分,比它小的分在左边,比它大的分在右边。

3.可以肯定,如此一轮下来,这个基准值的位置一定在最终位置上,而左右只需要在内部进行排序即可

4.对两个子数组运用递归方法重复分割排序,直到每个数组只有一个元素。

5.排序完成。

图解:

图片资源(维基百科)

快速排序的实现

#include <iostream>  
using namespace std;  
void quick_sort(int s[],int l, int r){  
    int i = l,j = r, x = s[l];  
    while(i < j){  
        while(i < j && s[j] > x) j--;  
        if(i < j)  
            s[i++] = s[j];  
        while(i < j && s[i] < x) i++;  
        if(i < j)  
            s[j--] = s[i];   
    }  
    //此时i==j,下面s[i]或者s[j]都可以,j-1,j+1也ok  
    s[j] = x;  
    if (l<i) quick_sort(s,l, i - 1);  //重点是这里对更小区间的处理
    if (r>i) quick_sort(s,i + 1, r);  
};  
int main()  
{  
 int test[] = {34,5,4,5,3,2,6,90,5};  
    quick_sort(test,0,8);  
    for(int i=0;i<9;i++){  
        cout<<test[i]<<"  ";  
    }  
    cout<<endl;  
 return 0;  
}

归并排序

想起来了上学期的一个练习题,两个升序数组合并要求新数组也升序

#include<iostream>
using namespace std;
int main()
{
  int shuzu1[5]={5,10,15,20,25},shuzu2[5]={3,13,17,33,43};
  int outshuzu[10]={0};
  int i=0,j=0,k=0;
  //i为数组1的控制变量,j为数组2的控制变量,k为输出数组的控制变量
  while(i<5&&j<5)
  {
    if(shuzu1[i]<shuzu2[j])
    {
      outshuzu[k]=shuzu1[i];
      k++,i++;
    }else
    {
      outshuzu[k]=shuzu2[j];
      k++,j++;
    }
  }
  if(i==5)
    while(j<5) outshuzu[k]=shuzu2[j],j++,k++;
  else if(j==5)
    while(i<5) outshuzu[k]=shuzu2[i],i++,k++;
  for(int k=0;k<10;k++)
    cout<<outshuzu[k]<<'\t';
}
 
//runtime result
3       5       10      13      15      17      20      25      33      43
请按任意键继续. .

经过了学习,明白了这其实就是归并排序法

定义:

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

思路:

基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序?

可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

void Merge(int A[],int p,int q,int r)  
{  
    int i,j,k;  
    int n1=q-p+1;  
    int n2=r-q;  
    int *L=new int[n1+1]; //开辟临时存储空间  
    int *R=new int[n2+1];  
    for(i=0;i<n1;i++)  
        L[i]=A[i+p];      //数组下标从0开始时,这里为i+p  
    for(j=0;j<n2;j++)  
        R[j]=A[j+q+1];    //数组下标从0开始时,这里为就j+q+1  
    L[n1]=INT_MAX;        //"哨兵"设置为整数的最大值,INT_MAX包含在limits.h头文件中  
    R[n2]=INT_MAX;  
    i=0;  
    j=0;  
    for(k=p;k<=r;k++)     //开始合并  
    {  
        if(L[i]<=R[j])  
            A[k]=L[i++];  
        else  
            A[k]=R[j++];  
    }  
}  
  
void MergeSort(int A[],int p,int r)   
{  
    if(p<r)  
    {  
        int q=(p+r)/2;  
        MergeSort(A,p,q);  
        MergeSort(A,q+1,r);  
        Merge(A,p,q,r);  
    } 
}

和快速排序有点像,都是把大问题分割到很小的问题再解决。

这种思维方式叫分治法:

分治法

分治法可以通俗的解释为:把一片领土分解,分解为若干块小部分,然后一块块地占领征服,被分解的可以是不同的政治派别或是其他什么,然后让他们彼此异化。

分治法的精髓:

  • 分–将问题分解为规模更小的子问题;
  • 治–将这些规模更小的子问题逐个击破;
  • 合–将已解决的子问题合并,最终得出”母”问题的解;

堆排序

堆排序是一种利用数据结构的排序算法,核心思想是首先将待排序序列构造成大顶堆,然后移走堆顶,将剩余元素再调整为大顶堆,再取堆顶直到序列中只有一个元素。

 堆调整

void sift ( int r[ ], int k, int m )
{//要筛选结点的编号为k,堆中最后一个结点的编号为m 
    i=k;  j=2*i;  temp=r[i];  //将筛选记录暂存
    while (j<=m ) {          //筛选还没有进行到叶子
       if (j<m && r[j]<r[j+1]) j++;  //左右孩子中取较大者
        if (temp>r[j]) break; 
        else {
             r[i]=r[j];   i=j;   j=2*i;
        }
     }
     r[i]=temp;   //将筛选记录移到正确位置
}

堆排序算法

void  HeapSort ( int  r[], int n)
{
    for (i=n/2; i>=1; i--)      //初建堆
       sift(r, i, n) ;     
    for (i=1; i<n; i++ )
    {
       r[1]←→r[n-i+1];        //移走堆顶
       sift(r, 1, n-i);               //重建堆
    }
}

测试

#include<bits/stdc++.h>
using namespace std;
int a[1000];
void sift ( int r[ ], int k, int m )///此处依然是大顶堆
{//要筛选结点的编号为k,堆中最后一个结点的编号为m
    int i=k;
    int j=2*i,temp=r[i];  //将筛选记录暂存
    while (j<=m ) {          //筛选还没有进行到叶子
       if (j<m && r[j]<r[j+1]) j++;  //左右孩子中取较大者
        if (temp>r[j]) break;
        else {
             r[i]=r[j];   i=j;   j=2*i;
        }
     }
     r[i]=temp;   //将筛选记录移到正确位置
}
void  HeapSort ( int  r[], int n)
{
    for (int i=n/2; i>=1; i--)      //初建堆
       sift(r, i, n) ;
    for (int i=1; i<n; i++ )
    {
       swap(r[1],r[n-i+1]);        //移走堆顶,放在序列的后面
       sift(r, 1, n-i);               //重建堆
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    HeapSort(a,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

13 − 4 =