无C不行-废物一个-算法导论：C语言

1047521767

                                            无C不行，废物一个，算法导论：C语言
4 K8 l, g$ R0 k

直接插入排序法

原理：从无序数列向左遍历，从有序数组向左比较

3 b3 l) J/ {) _; P" z/ m//插入排序法
( I$ h4 V+ ]& c* _0 H% P8 J2 r2 Xvoid straightsort(int*arr,int len)
& P8 ~+ r/ h/ }8 d9 K3 O+ \$ g/ G6 J{
/ D2 x3 E* _$ N: t7 e3 C1 U        int temp,i,j;
        for(i=1;i<len;i++)//将首元素看成有序数组，i=1表示从第二个元素开始排序
6 L" A1 Z5 C- @        {
                temp=arr;//temp存放待插入元素
$ x6 ?- [7 d" H8 K% d                for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较，arr[j]代表已经排序的有序数组，满足j>=0,且arr[j]>temp
. }/ {! I2 `# B+ I( k/ w( L( p" K                {
                        arr[j+1]=arr[j];//若条件成立，则将已排序数组向右移位，arr[j]最大可达arr处，即temp处
( N: g. q! v/ c  b0 r                }
                arr[j+1]=temp;//当循环不成立或循环终止，此时arr[j]<=temp（或j=-1，所有有序数组都大于待排元素,）temp应位于arr[j+1]处，j随temp左移而发生变化（减小）
        }
}

# `* y9 g  @( r) f5 `$ e3 i

归并排序法

将一个数组从中间分为两部分，再分别对两部分进行排序（递归），最后将排好序的两部分对比合并

0 a4 b6 M$ o9 L! g//归并排序法
( y' M) X- G/ O: C. N5 uvoid merge_sort(float data[],int left,int right,float sorted_data[])
% X4 c4 N$ j; p{
+ b, K* T' g6 |) \6 V* @8 w        if(left<right)//排除原数组出现只有一个数据的情况(left=right)
" R' g: R7 Y0 m5 D+ F. q        {
5 ~$ K# v4 g7 \0 u" g* B0 W3 ~  n* K                int mid=(left+right)/2;
6 B& v( }# A) U' J( @5 r                merge_sort(data,left,mid,sorted_data);
                merge_sort(data,min+1,right,sorted_data);
                merge_array(data,left,mid,right,sorted_data);
/ @; P5 V: d7 o* d! k1 ?- r        }
}
void merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序，但将子数组分为两部分，temp[]即临时数组
{
1 p) U) W. o" S* X        int i=left,j=mid+1;
2 e& W; P/ P+ w5 T" n        int k=0;
        while(i<=mid&&j<=right)//循环条件，将较小数组放入临时数组temp[]中，同时i变为data[i+1]或j变为data[j+1]
1 T. c, s! E. r& w( N2 H        {
                if(data<=data[j])
# K; _9 F  G' u6 S$ @, o) U                {
0 p% ]9 O9 Q1 z5 x. B1 _                        temp[k++]=data[i++];
9 a$ X6 W! y2 d% r                }
# \( @" H; a2 y$ B4 W* g5 }: h                else
                        temp[k++]=data[j++];
        }
        while(i<=mid)//以下两个while代表可能出现的特殊情况：i/j所在数组已经全部完成排序，但另一数组仍有>=1的元素未放入临时数组中
) K8 S! s* Y$ \7 K                temp[k++]=data[i++];
        while(j<=right)
                temp[k++]=data[j++];
7 q$ s2 s, v/ o        for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中，k=right-left,k代表了数组长度
! N$ i5 a0 ~4 j3 M4 S                data[left+i]=temp;
}
void merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化
{
; K3 t3 Y% j, ^5 x6 D. S* L& A3 F        int max_num=INT_MAX;
3 k$ e  s6 {/ l        int len=right-left+1;
) q# {9 \( h$ l9 D: f& F. U        int data_left=new int [mid-left+2];
* T0 p+ E( [; u5 h8 n: d        int data_right=new int [right-mid+1];
        int i=0,j=0,k=0;
        for(int k=left;k<=mid;k++)
                data_left[k-left]=data[k];
        data_left[k-left]=max_num;
% n0 z: p. a3 ~" w, F, v' m$ _        for(int k=mid+i;k<=right;k++)
! J: x( v8 }! ^: ^& g7 p                data_right[k-mid-1]=data[k];
        data_right[k-mid-1]=max_num;
  S0 o& j% X) g4 Z) f        for(int k=0;k<len;k++)
        {
                if(data_left<=data_right[j])
                        data[k+left]=data_left[i++];
* v( r$ Y0 Z* P1 w                else
                        data[k+left]=data_right[j++];
        }
) C6 t. V3 x: Q+ c, A4 n}
+ A; c7 Q4 r7 M; b' B
( N8 a1 @4 ~2 K. R5 ~2 R
  a- T  g* E4 ]! N* ]

涂真锦

收藏，必须收藏啊
& K" i- x, j4 \3 O& Z. P+ R

1047521767

涂真锦 发表于 2021-11-29 17:54
/ x6 Z- j# {- `9 M+ [收藏，必须收藏啊

0 m9 d3 j5 D: Y点赞
6 R+ t* q. n! O( `! `' t