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

1047521767

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

直接插入排序法

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

//插入排序法
) N# F9 T$ s6 C5 r0 ^3 j6 Svoid straightsort(int*arr,int len)
{
6 k* U; `% `6 R5 ~2 }7 h- R        int temp,i,j;
2 y, w* k& k0 C! G; X& M7 t        for(i=1;i<len;i++)//将首元素看成有序数组，i=1表示从第二个元素开始排序
1 o: a) w9 i6 Y        {
                temp=arr;//temp存放待插入元素
) w6 p' r$ b$ y+ L                for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较，arr[j]代表已经排序的有序数组，满足j>=0,且arr[j]>temp
$ z# o% k* [3 S0 `/ n2 o                {
$ j# U  i& w  `- |* H: W5 B                        arr[j+1]=arr[j];//若条件成立，则将已排序数组向右移位，arr[j]最大可达arr处，即temp处
% S6 J' ]* H& U% D' C                }
) B  u1 c6 e( P/ g                arr[j+1]=temp;//当循环不成立或循环终止，此时arr[j]<=temp（或j=-1，所有有序数组都大于待排元素,）temp应位于arr[j+1]处，j随temp左移而发生变化（减小）
( D9 m2 W7 q0 U" {" R' A        }
}
  c5 c& x0 k* S
$ f% Y0 V* z, P% x0 r# @

归并排序法

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

//归并排序法
void merge_sort(float data[],int left,int right,float sorted_data[])
{
        if(left<right)//排除原数组出现只有一个数据的情况(left=right)
        {
* \6 ]8 s7 |" e" |6 v                int mid=(left+right)/2;
                merge_sort(data,left,mid,sorted_data);
                merge_sort(data,min+1,right,sorted_data);
                merge_array(data,left,mid,right,sorted_data);
        }
8 v/ p3 u3 {5 ?  Z0 c% X}
* I+ ?# ?6 }, u+ a' H) avoid merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序，但将子数组分为两部分，temp[]即临时数组
! d7 q+ S9 N1 d& i! ~+ _5 E' O{
" x: _# V: b0 X, U        int i=left,j=mid+1;
        int k=0;
- c+ [/ x0 B& q3 `' `        while(i<=mid&&j<=right)//循环条件，将较小数组放入临时数组temp[]中，同时i变为data[i+1]或j变为data[j+1]
        {
                if(data<=data[j])
# x! Y# H- S2 O: A2 z" M" S                {
6 m' @9 p9 }% f$ E                        temp[k++]=data[i++];
% P7 P/ E6 P: g9 {4 g                }
4 Y! p! I1 C( q4 c0 {7 {7 x+ L                else
! I2 f! b/ e+ l( C0 s0 ^* X9 I                        temp[k++]=data[j++];
2 n; n8 t+ ]  \$ N/ X' Z+ v. z) Z        }
( G4 r' M! A( ]+ o& e        while(i<=mid)//以下两个while代表可能出现的特殊情况：i/j所在数组已经全部完成排序，但另一数组仍有>=1的元素未放入临时数组中
1 \% C2 Q5 q# r! Q5 e/ S% ?                temp[k++]=data[i++];
& |' @6 `! N- O. f        while(j<=right)
0 b4 Q7 X/ D2 ~) _7 W, V                temp[k++]=data[j++];
2 L. w& A) i8 d2 F; ~; f) v! O        for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中，k=right-left,k代表了数组长度
                data[left+i]=temp;
}
7 F# e0 w  T( o0 \# ^2 vvoid merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化
$ q  @9 n- k8 n& j6 M/ n' C{
2 P% e: f  Q# U0 y" d1 h; i        int max_num=INT_MAX;
        int len=right-left+1;
        int data_left=new int [mid-left+2];
. `* v6 \" l( S2 j1 t/ H+ w        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;
; U# o" y% H9 [; H9 o# i$ J! [        for(int k=mid+i;k<=right;k++)
1 x2 P. b3 b2 Z$ G1 A; v1 U                data_right[k-mid-1]=data[k];
* P' \( j9 M- l/ f        data_right[k-mid-1]=max_num;
5 j1 n1 k2 g+ O# t6 d- ~        for(int k=0;k<len;k++)
        {
" @& i) t- z4 e5 W" M: T# Y$ L                if(data_left<=data_right[j])
$ U& [6 F  l& P                        data[k+left]=data_left[i++];
, `/ ?( L+ Q+ ^* h0 D# L                else
" R( y7 z8 J- I                        data[k+left]=data_right[j++];
        }
' Q+ k/ U" k" r7 b}
+ b. q6 N4 t% }5 ?; X& g3 t
1 I7 b2 g7 d7 K9 G$ N
3 e/ F& _$ A7 _0 j

1047521767

涂真锦 发表于 2021-11-29 17:54
收藏，必须收藏啊

点赞
5 z( v! Y$ i5 E3 E& {  b* n2 q- r

涂真锦

收藏，必须收藏啊
) E  _$ S6 n: V8 P0 u5 Z. F, G6 G