【BigHereo 49】---DataStructure---排序算法(七)

小灰灰 2022-06-05 20:08 160阅读 0赞

DataStructure---排序算法(七)

##    一,【前言】 ##

排序算法是所有AI, 人工智能等在IT行业中要成为大师的必修之功.排序算法简单的说就是多数据结构的一个操作,可以说出一种函数或者就说是一种解决问的方法.

1,常用的排序算法有哪些?

2,插入排序分为哪些?

3,选择排序稳定吗?

4,shell排序和归并排序有什么关联吗?

5, 这些排序算法都怎么进行选择?

## 二,【详情】 ##

**1,常用的排序算法有哪些?**

解答: 常用的有七种,可以分为四类, 插入(直接插入, shell排序), 选择(直接选择,堆排序), 交换(冒泡, 快速)和归并排序.

**  2,插入排序分为哪些?**

解答: 插入排序可以分为四种, 直接插入,shell排序, 二分(折半)排序和表插入排序; 常用的是直接插入和shell排序.

**3,选择排序稳定吗?**

解答: 不稳定. 什么是稳定? 如果有两个相同数字在排序之后,他们的排序前后位置不变成为该种排序是稳定的.

不稳定的有: 快速选择shell.---一共就四种: 快速排序, 选择(直接选,堆排序)和shell.

**  4,shell排序和归并排序有什么关联吗?**

解答: shell 和归并都是先两个两个进行 对比,如果是要从小到大, 他们顺序不对就交换.

Shell是中间空几个的两个比较; 而 归并是相邻的两个进行比较, 之后进行四个比较一致归并.

**5, 这些排序算法都怎么进行选择?**

解答: 怎么选择?

(1)序列基本有序时,插入和交换比较好

(2)待排记录数量较大, 选择排序比较好

**  6,直接插入的代码怎么写?**

**      ![Center][]**

voidStraightInsertSort(List R, int n)
    {
       int i,j;
       for(i=2;i<=n; i++)
      {
        R[0]=R[i]; j=i-1;  //第i个记录复制为岗哨
        while(R[0].key < R[j].key){ R[j+1]=R[j];j--;  }
         R[j+1]=R[0];
       }
    }

**  7,什么是直接选择?**

解答: 是什么?

(1)从未排序数中选择一个小的往前放

(2)选出同时,还要进行交换

**8,直接选择代码怎么写?**

**![Center 1][]**

voidSelectSort(ListR,intn)
    {
      int min i, j;
      for(i=1; i<= n-1; i++)
       { min=i;
          for(j=i+1;j<n; j++)
            if(R[j].key< R[min].key)  min=j;
            if(min!=i) swap(R[min], R[i]);
       }
    }

**9,堆排序有哪两种?**

解答:

(1)最大堆

最大的在最前面

(2)最小堆

最小的在最前面

**10,用代码怎么建立初始堆?**

**![Center 2][]**

代码怎写?

void HeapSort(List R)
    {
      int i;
      for (i=n/2; i>= 1;i--) sift( R, i, n);
      for (i=n; i>=2;i--) { swap(R[1], R[i]);sift(R,1,i-1);}
    }

void sift(List R, int k ,int m)
    {
      int i,j,x; List t;  i=k;  j=2*j; x=R[k].key;  t=R[k];
      while(j<=m) {
         if(j<m)&& (R[j].key>R[j+1].key)  j++;
         if(x<R[j].key) break;
         else{R[i]=R[j]; i=j; j=2*i;}
       }
      R[i]=t;
    }

**11,什么是冒泡排序?**

解答: 概念

从小到大:相邻相关进行比较,大的就往右交换,

一直重复这样到最后,  一次选择最大的

**12,冒泡排序怎么用代码表示?**

voidBubbleSort(List R, int n)
    {
       int, j , temp, endsort;
       for(i=1; i<=n-1; i++)
      {
       endsort=0;
       for(j=1; j<=n-i-1; j++)
          {
         if(R[j].key >R[j+1].key)
           {
             temp= R[j];R[j]=R[j+1]; R[j+1]=temp; endsort=1;
            }
          }
       if(endsort==0) break;
      }
    }

** 13, 什么是快速排序?**

解答: 是什么?

选一个记录值作为基准(一般第一个),小的放左边,大的放右边

怎么排?

拿基准和最右边 i 比较,小于基准进行交换,否则进行i-- 比较; 直至最后

** 14,快速排序怎么用代码写出来?**

**![Center 3][]**

//递归快速
             void QuickSort(List r, int lovw , inthigh
      if(low< high){
       temp=QuickPartition(R,low,high);
       QuickSort(r,low, temp-1);
       QuickSort(R, temp+1, high);}
    }

一趟排序
             int QuickPartition(List R, int Low,inthigh){
      x=R[low];
      while(low <high){
         while((low< hig)&&(R[high].key>=x.key))  high--;  R[low]=R[high];     
         while ((low<high)&&(R{[ow].key<=x.key))  low++; R[high]=R[low];
      }
       R[low]=x; return low;
    }

**15,归并排序用代码怎么表示?**

![Center 4][]

## 三,【小结】                                           ##

![Center 5][]

[Center]: /images/20220606/d9cefd8ee7c247ec95ff467d5df7e3eb.png
[Center 1]: /images/20220606/602338950b0f4c1cbaa55e24b72c9631.png
[Center 2]: /images/20220606/147ecd486c664f548794ca03855a84b5.png
[Center 3]: /images/20220606/3f28c262e5784c6f8bd5ab0c226edcf5.png
[Center 4]: /images/20220606/ee786433854542ac936d14e83d0c13fd.png
[Center 5]: /images/20220606/9175f38e34e94187aacee43e112d32d9.png