- 在线时间
- 514 小时
- 最后登录
- 2023-12-1
- 注册时间
- 2018-7-17
- 听众数
- 15
- 收听数
- 0
- 能力
- 0 分
- 体力
- 39461 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 12534
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1388
- 主题
- 1158
- 精华
- 0
- 分享
- 0
- 好友
- 15
TA的每日心情 | 开心 2023-7-31 10:17 |
---|
签到天数: 198 天 [LV.7]常住居民III
- 自我介绍
- 数学中国浅夏
|
无C不行,废物一个,算法导论:C语言0 C0 a- Y: N- _; c
直接插入排序法 原理:从无序数列向左遍历,从有序数组向左比较 J' z% V* l( Y- Z4 t
//插入排序法
' N& g9 B6 s2 e9 P" R W6 Qvoid straightsort(int*arr,int len)! k! s. k4 N- N4 J# u( a7 i/ X
{" n0 L" E" Z( d
int temp,i,j;
) k' c& S) I- {+ Y for(i=1;i<len;i++)//将首元素看成有序数组,i=1表示从第二个元素开始排序
+ c6 t4 C2 N% p/ ?* f; ?5 B { }+ A3 B2 {5 E$ C
temp=arr;//temp存放待插入元素
% B; ^; o6 U2 \+ ` for(j=i-1;j>=0&&arr[j]>temp;j--)//待插入元素向左比较,arr[j]代表已经排序的有序数组,满足j>=0,且arr[j]>temp
( D b' K* f- \# m {. ?( K0 E& M/ x- Q5 K
arr[j+1]=arr[j];//若条件成立,则将已排序数组向右移位,arr[j]最大可达arr处,即temp处1 C! K: ?' F4 o O
}; _$ ?/ B; B5 k1 B
arr[j+1]=temp;//当循环不成立或循环终止,此时arr[j]<=temp(或j=-1,所有有序数组都大于待排元素,)temp应位于arr[j+1]处,j随temp左移而发生变化(减小)$ p( u0 |0 Q4 D: }5 Q$ Z
}
$ K& d, b# @+ c6 e z}
: O. n7 r( R* m. L; N" r4 f
7 a: A$ F7 A' I$ S! K归并排序法 将一个数组从中间分为两部分,再分别对两部分进行排序(递归),最后将排好序的两部分对比合并
7 \9 K6 o# K0 n5 i7 y//归并排序法
# ]; @4 _4 a3 \4 ?void merge_sort(float data[],int left,int right,float sorted_data[])2 m% j/ S2 a* x5 v. D9 d6 Q0 N
{
% a& E6 g2 I$ P# h8 `, b) J3 B if(left<right)//排除原数组出现只有一个数据的情况(left=right)3 D- l& z3 M2 R' L* @) g3 v1 M8 e/ f9 r
{4 R! r6 H2 x' j
int mid=(left+right)/2;
% o& U- s7 v" j5 G/ g; A merge_sort(data,left,mid,sorted_data);
( G. G1 Y! @, X+ W merge_sort(data,min+1,right,sorted_data);
4 R8 k8 E/ B# I; h3 u5 G merge_array(data,left,mid,right,sorted_data);
' [; p* J* m7 u1 P# z }
* ^ t( o4 }; G; S( o \$ l}" t+ X1 T3 O4 F g0 R& s& x Y
void merge_array(float data[],int left,int mid,int right,float temp[])//data[]即待排子数组,直接用子数组排序,但将子数组分为两部分,temp[]即临时数组
7 E# g$ [ l* ~3 N8 e, E{
, n! X5 L3 o( K$ d int i=left,j=mid+1;7 P- ?8 y: |3 ?! {( K8 N) ~
int k=0;
; j; K% ]+ ^" P' Y' v0 ~ while(i<=mid&&j<=right)//循环条件,将较小数组放入临时数组temp[]中,同时i变为data[i+1]或j变为data[j+1]
# T$ n% l* k3 `* n5 I4 E {) S4 H+ s: N) D- `( ~
if(data<=data[j])
" c; K z1 L0 K! g L. ? {, j+ h2 M, t/ C# C/ `
temp[k++]=data[i++];
" v0 r7 q3 e! U9 J }: [1 S5 K# N4 J$ w' ~
else2 O, d9 `3 H( E2 i; ]1 M( U
temp[k++]=data[j++];
0 x3 I% P; u. r' |9 A }
& C4 W2 P. _! P1 G4 O while(i<=mid)//以下两个while代表可能出现的特殊情况:i/j所在数组已经全部完成排序,但另一数组仍有>=1的元素未放入临时数组中
/ Y( g7 {: K: F& r; Q# l temp[k++]=data[i++];
4 [: l& E( D# }0 I while(j<=right)
4 h2 `9 Q1 v% C temp[k++]=data[j++];6 H7 O8 |) f' E, D. h
for(i=0;i<k;i++)//将临时数组中的元素全部放入原数组中,k=right-left,k代表了数组长度) d9 n9 D: E# A# W1 K1 M5 o
data[left+i]=temp;
/ P2 N2 k1 v4 X+ E0 X3 G# y}
* O1 A' z0 W) z$ L- v; X# avoid merge_array(float data[],int left,int mid,int right,float temp[])//哨兵简化
, J* k7 c h9 u5 ]% u+ a) L{0 Y. ~6 R0 k# r; T9 @
int max_num=INT_MAX;
7 V2 h8 G5 V6 o0 J8 x int len=right-left+1; o; Y5 w/ [- D6 }
int data_left=new int [mid-left+2];' y" t& o6 d6 u$ [* c+ p
int data_right=new int [right-mid+1];
. J. `6 x2 L* f) |% [* @ int i=0,j=0,k=0;
7 q! z9 B4 f, Q, b7 x7 z6 O for(int k=left;k<=mid;k++)# R3 h0 {; [; Z) |1 n0 J+ s- b; |
data_left[k-left]=data[k];9 ^6 x% H2 ^- x2 V( N
data_left[k-left]=max_num;5 ]# x, w% U* i. w
for(int k=mid+i;k<=right;k++)2 W- d m0 W& \7 o l8 j
data_right[k-mid-1]=data[k];
- B0 \. i- t- n0 \* I! G { data_right[k-mid-1]=max_num;
# w/ d2 q9 U/ K9 e/ K for(int k=0;k<len;k++)
& }) U3 r% K; p/ p) P. O. j5 o {
$ Q" w* [* i- u7 T3 z( q* E if(data_left<=data_right[j])( j/ r' H% |1 m: i) L) I
data[k+left]=data_left[i++];- j/ n1 v) w2 L
else2 |$ j8 d& F3 x6 O, X
data[k+left]=data_right[j++];
3 k R! A% O6 Q" ~* B }, X. ~8 V; ^$ H8 j# A
}
( N6 U3 [, v/ ]7 b( D6 Y6 u$ X+ q( ?7 `! E+ c4 v/ Y6 ~$ O
- G- h. f" Z* e) C: P8 l |
zan
|