排序算法

c/c++

浏览数:87

2019-9-13

AD:资源代下载服务

1. 插入类排序

  • 插入类排序核心:在已经有序的序列中插入新的关键字。
  • 默认都为升序排序

1.1 直接插入排序

  1. 假定数组 arr 首位元素 arr[0] 为有序序列;
  2. 把从2号元素 i=2 开始,逐一作为新的待插入关键字 temp,将 temp 与有序序列 从后往前 逐一比较,将大于 temp 的元素后移,最后找到合适位置后即插入 temp 元素,有序序列长度增加;
  3. 对所有元素进行这种比较、移动,最终实现排序。
for(i = 1;i < n;i++)
{
    temp = arr[i];
    j = i-1;
    
    while(j>=0 && temp<arr[j])
    {
        arr[j+1] = arr[j];
        --j;
    }
    arr[j+1] = temp;
}

1.2 折半插入排序

  1. 已知一个有序序列,例如 {1,4,8,10,15,20},设左右端值 low 和 high ,待插入的关键字为 arr[i] ;
  2. 每次选取一个中间值 m=(low+high)/2 ,与关键字进行比较,若 arr[m]>arr[i] 说明关键字小于 m 的右半部分,那么修改右端值 high=m-1 (同理小于则修改low=m+1);
  3. 重复选取中间值比较的过程,直至 low>high ,待插入位置即为 high+1 ;
  4. 经过对所有元素的比较、归位,最终实现排序。
for(i=1;i<n;i++)
{
    x = arr[i];
    low = 0;
    high = i-1;     //已排序列 [0~i-1]

    while(low<=high)
    {
        m = (low+high)/2;   //折半

        if(x>arr[m])        //修改左或右端值
            low = m+1;
        else
            high = m-1;
    }
    for(j=i-1;j>high;j--)   //移动数组留出待插位置
        arr[j+1] = arr[j];
    arr[j+1] = x;
}

1.3 希尔排序

参考:lchad – 希尔排序C语言实现

  1. 将序列按照 步长gap (增量,初始 gap=length/2,后续 gap=gap/2) 分割为多个子序列,例如本例中的{49,38,65,97,76,13,27,49,55,04} 按照 gap=5 分割为:
子序列1:49             13
子序列2:   38             27
子序列3:      65             49
子序列4:         97             55
子序列5:             76             04
  1. 对这5个子序列进行直接插入排序,结果为:
子序列1:13             49
子序列2:   27             38
子序列3:      49             65
子序列4:         55             97
子序列5:             04             76
  1. 同理按照 gap=gap/2 再次分割序列,再次对子序列进行直接插入排序;
  2. 最终唯一必须进行 gap=1 的分割,进行一趟直接插入排序完成操作。
for(gap=n/2;gap>0;gap=gap/2)      //分割序列
    for(i=0;i<n;i++)
        for(j=i+gap;j<n;j=j+gap)
            if(arr[j]<arr[j-gap])     //若同组内序列非有序,则需插入
            {
                temp = arr[j];
                k = j-gap;
                while(k>=0 && arr[k]>temp)  //移动至合适位置插入过程
                {
                    arr[k+gap] = arr[k];
                    k = k-gap;
                }
                arr[k+gap] = temp;
            }

2. 交换类排序

  • 核心:对原序列进行元素交换移动实现排序。
  • 默认都为升序排序

2.1 冒泡排序

已知一个序列,例如 arr[5]={9,7,5,3,1};

  1. 从左往右,对每对相邻元素比较 (arr[0]-arr[1],arr[1]-arr[2],…,arr[n-2]-arr[n-1]) ,比较后将较大的元素后移,经过一趟循环,会将当前序列内最大元素移动至末尾,即末尾元素有序;
  2. 重复这种相互比较、后移的过程,使得有序序列长度持续增加,无序序列长度持续减短;
  3. 最终当循环过程 不发生任何元素交换移动时 ,标志冒泡排序结束。
for(i=n-1;i>=1;i--)         //每趟排序把最大元素移至后面
{
    flag = 0;
    for(j=1;j<=i;j++)       //从左往右,相邻元素比较
        if(arr[j-1]>arr[j]) //交换移动
        {
            temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            flag = 1;
        }
    if(flag==0)         //若某趟排序中没有发生交换,标志排序完毕
        return;
    }

2.2 快速排序

基本思路在于设定一个枢轴值,将序列小于、大于它的元素分别 置于其两侧 ,再对2子序列重复该过程:
已知序列 arr[8]={49,38,65,97,76,13,27,49},序列左右标记为 i,j;

  1. 默认选取最左边值 arr[low] 为 枢轴先右边标记 j 左移,直到找到小于枢轴的元素 27;
  2. 将小元素 27 赋给 arr[i],后左标记 i 右移,直到找到大于枢轴的元素 65;
  3. 将大元素 65 赋给 arr[j],后右标记j左移,重复过程;
  4. 最终 i,j 相遇,该序列循环结束,本位置即为枢轴最终位置,枢轴将序列分割为2个子序列;
  5. 再分别对2个子序列重复这种找枢轴,移动标记,分割序列的过程,最终实现排序。
    int temp;       //枢轴
    int i = low,j = high;       //左右标记

    if(low<high)    //左右标记未相遇,可再进行排序时
    {
        temp = arr[low];    //取得枢轴

        while(i<j)
        {
            while(j>i && arr[j]>=temp)  //先右标左移,直到小于枢轴的数
                --j;
            if(i<j)
            {
                arr[i] = arr[j];    //小元素前赋值
                ++i;
            }

            while(i<j && arr[i]<temp)   //再左标右移,直到大于枢轴的数
                ++i;
            if(i<j)
            {
                arr[j] = arr[i];    //大元素后赋值
                --j;
            }
        }

        arr[i] = temp;      //枢轴归位
        QuickSort(arr,low,i-1);     //排左序列
        QuickSort(arr,i+1,high);    //排右序列
    }

3. 选择类排序

  • 核心:“选择”,即每趟排序选出最小关键字与序列首元素进行交换
  • 默认升序

3.1 快速排序

将原序列看作有序序列与无序序列组成(初始全为无序序列):

  1. 对无序序列进行扫描,找出序列内最小值
  2. 将其与无序序列首元素交换
  3. 由此有序序列增长,无序序列缩短;
  4. 重复每次找最小值放于前列的过程,实现排序。
  for(i=0;i<n;i++)    //默认无需序列首元素为待交换值
  {
      k = i;          //无序序列内最小值标记  
      for(j=i+1;j<n;j++)      //扫描无序序列
          if(arr[k]>arr[j])   //更新 k
              k = j;

      temp = arr[i];      //最小值与首元素交换
      arr[i] = arr[k];
      arr[k] = temp;
  }

作者:SouthBegonia