16、考研必会的排序算法（上）

🌺博客汇总：🌃Summary And Schedule🌠

🌸考研相关内容汇总：考研Schedule&&Summary

🌼408王道C督学课程目录：《王道C语言督学班目录》

本章需要掌握：

• 1、冒泡排序
• 2、快速排序
• 3、插入排序

有梯子可以看简单动画

1、排序

排序算法分为交换类排序，插入类排序，选择类排序，归并类排序

交换类排序分为冒泡排序，快速排序（后面的408笔记有详细的）

2、冒泡排序

简单来说，每次都会找到剩余元素最小的元素，并将它放到前面。（演示代码是找到最大元素放到最后，主要看算法怎么写，没什么太大区别。）

冒泡排序的基本思想是:从后往前(或从前往后)两两比较相邻元素的值，(若A[j-1]>A[j])，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置。

这么说可能不直观，直接看代码。

void BubbleSort(ElemType *A,int n)
{
    int i,j;
    bool flag;
    for(i=0;i<n-1;i++)//控制的是有序数的数目
    {
        flag= false;
        for(j=n-1;j>i;j--)//内层控制比较和交换
        {
            if(A[j-1]>A[j])
            {
                swap(A[j-1],A[j]);
                flag= true;
            }
        }
        if(false==flag)//如果一趟比较没有发生任何交换，说明数组有序，提前结束排序
        {
            return;
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct{
    ElemType *elem;//存储元素的起始地址
    int TableLen;//元素个数
}SSTable;

void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);//申请一块堆空间，当数组来使用
    int i;
    srand(time(NULL));//随机数生成，每一次执行代码就会得到随机的10个元素
    for(i=0;i<ST.TableLen;i++)
    {
        ST.elem[i]=rand()%100;//生成的是0-99之间
    }
}
//打印数组中的元素
void ST_print(SSTable ST)
{
    for(int i=0;i<ST.TableLen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
//交换两个元素
void swap(int &a,int &b)
{
    int tmp;
    tmp=a;
    a=b;
    b=tmp;
}
//往往都是用两层循环
//优先去写内层循环，再写外层循环
void BubbleSort(ElemType *A,int n)
{
    int i,j;
    bool flag;
    for(i=0;i<n-1;i++)//控制的是有序数的数目
    {
        flag= false;
        for(j=n-1;j>i;j--)//内层控制比较和交换
        {
            if(A[j-1]>A[j])
            {
                swap(A[j-1],A[j]);
                flag= true;
            }
        }
        if(false==flag)//如果一趟比较没有发生任何交换，说明数组有序，提前结束排序
        {
            return;
        }
    }
}

int main() {
    SSTable ST;
    ST_Init(ST,10);
//    ElemType A[10]={ 64, 94, 95, 79, 69, 84, 18, 22, 12 ,78};
    //内存copy接口，当你copy整型数组，或者浮点型时，要用memcpy，不能用strcpy，初试考memcpy概率很低
//    memcpy(ST.elem,A,sizeof(A));//这是为了降低调试难度，每次数组数据固定而设计的
    ST_print(ST);//随机后的结果打印
    BubbleSort(ST.elem, 10);
    ST_print(ST);//排序后再次打印
    return 0;
}

3、快速排序

分治思想。设定一个界定值，遍历所有需要排序元素，将小于该界定值和大于该界定值的放在其两侧，每次结束都能将该界定值放到其最终正确的位置。

一开始可能有点难理解，多看两遍就懂了。

int partition(ElemType *A,int low,int high)
{
    ElemType pivot=A[low];//以low作为界定值
    while(low<high)
    {
      	//high下标值比pivot大就不动，high--
        while(low<high&&A[high]>=pivot)
            high--;
     		//high下标值是小于pivot，high下标元素覆盖low下标元素
        A[low]=A[high];
      	//low下标值是比pivot小就不动，low++
        while(low<high&&A[low]<=pivot)
            low++;
      	//low下标值是大于pivot，low下标元素覆盖high下标元素
        A[high]=A[low];
    }
  	//把pivot放分类后的两个数组到中间，返回中间下标
    A[low]=pivot;
    return low;
}

void QuickSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int pivot_pos=partition(A,low,high);//pivot用来存分割值的位置
        QuickSort(A,low,pivot_pos-1);//前一半继续递归排好
        QuickSort(A,pivot_pos+1,high);
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct{
    ElemType *elem;//存储元素的起始地址
    int TableLen;//元素个数
}SSTable;

void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);//申请一块堆空间，当数组来使用
    int i;
    srand(time(NULL));//随机数生成，每一次执行代码就会得到随机的10个元素
    for(i=0;i<ST.TableLen;i++)
    {
        ST.elem[i]=rand()%100;//生成的是0-99之间
    }
}
//打印数组中的元素
void ST_print(SSTable ST)
{
    for(int i=0;i<ST.TableLen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}

//快排的核心函数
//挖坑法
int partition(ElemType *A,int low,int high)
{
    ElemType pivot=A[low];//拿最左边的作为分割值，并存储下来
    while(low<high)
    {
        while(low<high&&A[high]>=pivot)//从后往前遍历，找到一个比分割值小的
            high--;
        A[low]=A[high];//把比分隔值小的那个元素，放到A[low]
        while(low<high&&A[low]<=pivot)//从前往后遍历，找到一个比分割值大的
            low++;
        A[high]=A[low];//把比分隔值大的那个元素，放到A[high],因为刚才high位置的元素已经放到了low位置
    }
    A[low]=pivot;//把分割值放到中间位置，因为左边刚好都比它小，右边都比它大
    return low;//返回分隔值所在的下标
}

void QuickSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int pivot_pos=partition(A,low,high);//pivot用来存分割值的位置
        QuickSort(A,low,pivot_pos-1);//前一半继续递归排好
        QuickSort(A,pivot_pos+1,high);
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);//初始化
//    ElemType A[10]={ 64, 94, 95, 79, 69, 84, 18, 22, 12 ,78};
    //内存copy接口，当你copy整型数组，或者浮点型时，要用memcpy，不能用strcpy，初试考memcpy概率很低
//    memcpy(ST.elem,A,sizeof(A));//这是为了降低调试难度，每次数组数据固定而设计的
    ST_print(ST);
    QuickSort(ST.elem,0,9);//注意这个位置是n-1,也就是9，因为函数里取了high位置的值
    ST_print(ST);
    return 0;
}

5、插入排序

不难，前面序列有序，后面序列无序，把后面序列依次插入前面序列，整个序列就有序了。

void InsertSort(ElemType *A,int n)
{
    int i,j,insertVal;
    for(i=1;i<n;i++)//外层控制要插入的数
    {
        insertVal=A[i];//保存要插入的数
        //内层控制比较,j要大于等于0，同时arr[j]大于insertval时，arr[j]位置元素往后覆盖
        for(j=i-1;j>=0&&A[j]>insertVal;j--)
        {
            A[j+1]=A[j]; //从后向前依次比较找到合适插入位置
        }
        A[j+1]=insertVal;//把要插入的元素放到对应的位置
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct{
    ElemType *elem;//整型指针
    int TableLen;
}SSTable;

void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;//申请10个元素的空间
    ST.elem=(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));
    for(i=0;i<ST.TableLen;i++)
    {
        ST.elem[i]=rand()%100;//随机了10个数
    }
}
void ST_print(SSTable ST)
{
    for(int i=0;i<ST.TableLen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}

void InsertSort(ElemType *A,int n)
{
    int i,j,insertVal;
    for(i=1;i<n;i++)//外层控制要插入的数
    {
        insertVal=A[i];//保存要插入的数
        //内层控制比较,j要大于等于0，同时arr[j]大于insertval时，arr[j]位置元素往后覆盖
        for(j=i-1;j>=0&&A[j]>insertVal;j--)
        {
            A[j+1]=A[j];
        }
        A[j+1]=insertVal;//把要插入的元素放到对应的位置
    }

}
int main() {
    SSTable ST;
    ST_Init(ST,10);//申请10个元素空间
    ST_print(ST);//排序前打印
    InsertSort(ST.elem,10);
    ST_print(ST);//排序后再次打印
    return 0;
}