• 数据结构——排序

    目录

    1.排序概述

    1.排序的概念

    2.排序方法的分类 

    3.稳定排序与不稳定排序 

    4.存储结构

     代码示例：

    2.插入排序 

    1.直接插入排序 

    代码示例：

    性能分析 

    2.折半插入排序 

    代码示例 ：

    算法分析 

    3.希尔排序 

    代码示例：

    算法分析 

    3.交换排序

    1.冒泡排序

    冒泡排序原理

    代码示例：

     冒泡排序的改进

    代码示例：

    算法分析 

    2.快速排序 

    快排的原理

    代码示例： 

    算法分析 

    4.选择排序

    1.简单选择排序 

    排序原理 

    代码示例：

     算法分析

    2.堆排序

    排序原理 

    筛选过程代码示例：

    堆排序算法代码示例：

    算法性能分析 

    5.归并排序 

    算法分析 

    6.基数排序 

    算法分析 

    7.各种排序方法的综合比较 

    26ff58e595104fbcaab4eaf643596515.png

    1.排序概述

    1.排序的概念

    0a6a3556eb02458486e434c456b934fc.png

    cb3115366de04dc49a7e396e1c3ba666.png

    2.排序方法的分类 

    a6881d6ca1b840bb9f3395d64fd245bd.png

    fa0adcd4f86c44b19ab4f37d644cd264.png

    5ee36d7ac0b6414fb91bca612776a1db.png

    b650c0e31a1c47d08d0688cfd5c0caa4.png

    65d44a22a9fb42a2aa121adffaef4afb.png

    7f5584ddfd85465d8b3a9e3e4c7929d1.png

    3.稳定排序与不稳定排序 

    ee6641ab5c08400fb8fa2ddbbba60560.png

    a146d954a5ed48dbb7c36f4d7d372d81.png

    962e85dbf3b64659ab1d7a3b72ccc5ea.png

    25aecb9fa17a4ec09e75298b2fa4c887.png

    0b0cbf28e2e146f2b7d2b210d2a33b6b.png

    4.存储结构

    87702e60ad92475b91ce717ad83a4d15.png

     代码示例：

    1. #define maxsize 20
    2.  
    3. typedef struct {
    4. 	int key;
    5. }redtype;
    6.  
    7. typedef struct {
    8. 	redtype r[maxsize + 1];
    9. 	int len;
    10. }sqlist;

    2.插入排序 

    185e2bd5e47245fe84b837c69310fc0f.png

    886189863edb4ac5981998fc9a237a37.png

    acbd52a332b34151bab04fd6f8d029e2.png

    4ad635fdee0d48119bd07d95c5fe104c.png

    485c656a64f44989b26eb8474acf1073.png

    1.直接插入排序 

    026d9356387741c283c087e264686603.png

    590d28450f4b470a9ee92d438988cf90.png

    92f6499fffa34a41899aebe4e89f1130.png

    代码示例：

    1. void insertsort(sqlist &l) {
    2. 	int i,j;
    3. 	for(i = 2; i <= l.len; ++i) {
    4. 		if(l.r[i].key < l.r[i - 1].key){
    5. 			l.r[0] = l.r[i];
    6. 			for(j = i - 1; l.r[0].key < l.r[j].key; --j) {
    7. 				l.r[j + 1] = l.r[0];
    8. 			}
    9. 		}	
    10. 	}
    11. }

    性能分析 

    96cbc0b7d82e45b09b58cfdf6f6c8053.png

    d1841ddc54e04579ab2c4ef870b769d6.png

    6ab1476b89b848ea9f6102007d5993cf.png

    94fc5e9c762d4327a35cb18e6e337f31.png

    7d586466a7f0400fade3c0972a4531cf.png

    8f94a2b70a784c90897c9b13bf8af2ea.png

    2.折半插入排序 

    60a44f8b432641a08a504e4c97095465.png

    1d4f797c516544daa177df54d6ca82f8.png

    代码示例 ：

    1. void binsertsort(sqlist &l) {
    2. 	for(int i = 2; i <= l.len; ++i) {
    3. 		l.r[0] = l.r[i];
    4. 		int low = 1;
    5. 		int high = i - 1;
    6. 		while(low <= high) {
    7. 			int mid = (low + high) / 2;
    8. 			if(l.r[0].key < l.r[mid].key)
    9. 				high = mid - 1;
    10. 			else low = mid + 1;
    11. 		}
    12. 		for(int j = i - 1; j >= high + 1; --j) {
    13. 			l.r[high + 1] = l.r[0];
    14. 		}
    15. 	}
    16. }

    算法分析 

    9dafa52ec13349258d754bc1c4d838fc.png

    759d793985924404aafe002be5ec14b9.png

    5e4c7214a4da4916963937636a73cba6.png

    3.希尔排序 

    dcb7818d1c564c67b15f1a73db929f00.png

    d636af1f62e941a1b9ac2e8f41293d0d.png

    56c67546d1254989b3fe25120b65c212.png

    1261cc5c62a048b19058e5ada6d30bd4.png

    307b0088cf4947f186c4fc1851643235.png

    77b4cf3d0f914bf5bdd666f70c47aec0.png

    9448b5ecc4114ee1bd0e541a05a503bf.png

    代码示例：
    1. void shellinsert(sqlist &l, int dk) {
    2. 	int i,j;
    3. 	for(i = dk + 1; i <= l.len; ++i) {
    4. 		if(l.r[i].key < l.r[i - dk].key) {
    5. 			l.r[0] = l.r[i];
    6. 			for(j = i - dk; j > 0 && (l.r[0].key < l.r[j].key); j = j - dk) {
    7. 				l.r[j + dk] = l.r[i];
    8. 			}
    9. 			l.r[j + dk] = l.r[0];
    10. 		}
    11. 	}
    12. }
    13.  
    14. void shellsort(sqlist &l, int dlta[], int t) {
    15. 	for(int k = 0; k < t; ++k) {
    16. 		shellinsert(l, dlta[k]);
    17. 	}
    18. }

    算法分析 

    1f9d55942fd742a6a56a55de037eaf49.png

    734936cd4aa74b2ab1850bd6654c1827.png

    f32a477a9f774ace8218924c6e479408.png

    96f2edf6f24543e9b3ce75009e42a248.png

    4329ebbfead94215bee17a8f26e460c3.png

    3.交换排序

    1.冒泡排序

    冒泡排序原理

    代码示例：
    1. void bubblesort(sqlist &l) {
    2. 	int m,n,j;
    3. 	redtype x;
    4. 	for(m = 1; m <= n - 1; m++) {
    5. 		for(j = 1; j <= n - m; j++) {
    6. 			if(l.r[j].key > l.r[j + 1].key) {
    7. 				x = l.r[j];
    8. 				l.r[j] = l.r[j + 1];
    9. 				l.r[j + 1] = x;
    10. 			}
    11. 		}
    12. 	}
    13. }

     冒泡排序的改进

     

    代码示例：
    1. void bubblesort2(sqlist &l) {
    2. 	int m,n,j;
    3. 	int flag = 1;
    4. 	redtype x;
    5. 	for(m = 1; m <= n - 1 && flag == 1; m++) {
    6. 		flag = 0;
    7. 		for(j = 1; j <= n - m; j++) {
    8. 			if(l.r[j].key > l.r[j + 1].key) {
    9. 				flag = 1;
    10. 				x = l.r[j];
    11. 				l.r[j] = l.r[j + 1];
    12. 				l.r[j + 1] = x;
    13. 			}
    14. 		}
    15. 	}
    16. }

    算法分析 

     

     

    2.快速排序 

    快排的原理

     

     

    代码示例： 

    1. int partition(sqlist &l,int low,int high) {
    2. 	l.r[0] = l.r[low];
    3. 	int pivotkey = l.r[low].key;
    4. 	while(low < high) {
    5. 		while(low < high && l.r[high].key >= pivotkey)
    6. 			--high;
    7. 		l.r[low] = l.r[high];
    8. 		while(low < high && l.r[low].key <= pivotkey)
    9. 			++low;
    10. 		l.r[high] = l.r[low];
    11. 	}
    12. 	l.r[low] = l.r[0];
    13. 	return low;
    14. }
    15.  
    16. void qsort(sqlist &l,int low,int high) {
    17. 	if(low < high) {
    18. 		int pivotloc = partition(l,low,high);
    19. 		qsort(l,low,pivotloc - 1);
    20. 		qsort(l,pivotloc + 1,high);
    21. 	}
    22. }
    23.  
    24. int main() {
    25. 	sqlist l;
    26. 	qsort(l,1,l.len);
    27. 	return 0;
    28. }

    算法分析 

    90c1873c8a7c4acf8c7e92bc24cd09c3.png

    8b8b3bd8a65e47d599c656b676dfc9c5.png

    13cf3db8266d452d8140b1093ee51aed.png

    4d09cdfb78a24bef9906a3a0cf22d8c3.png

    6672b065f38d46b7a3aeb2fe85a1af9f.png

    4.选择排序

    1.简单选择排序 

    排序原理 

    7ba48362b46348c7890e15fe00456fe6.png

    cbfd538c1d424461a08884bc092b50b6.png

    0a5689374db142e491463c54bcf6b6f2.png

    803a489875b949ff9df6fb42a12691a4.png

    代码示例：
    1. void selectsort(sqlist &l) {
    2. 	int i,j,k;
    3. 	for(i = 1; i < l.len; ++i) {
    4. 		k = i;
    5. 		for(j = i + 1; j < l.len; j++) {
    6. 			if(l.r[j].key < l.r[k].key)
    7. 				k = j;
    8. 			if(k != i) {
    9. 				redtype temp = l.r[i];
    10. 				l.r[i] = l.r[k];
    11. 				l.r[k] = temp;
    12. 			}
    13. 		}
    14. 	}
    15. }

     算法分析

    d1ed3099b96344bcb7a87c4308efbb0e.png

    3c12b5644003436db641e2eb62d4028e.png

    2.堆排序

    排序原理 

    743e14a7042944a68c54a674cfbe0a75.png

    b90aa4e6086d452a840cb13d20e3c081.png

    7ac4fbd2abb04673a6411daab7812a24.png

    4090139f3f6f4a05a57f86945cfea359.png

    7636fc3a951647e5871c24c19136b187.png

    87fe8f340a434f6095e4f7858a22b99a.png

    b7271ab8660b4ebeae4abe6e1560d80b.png

    b800769bcefe4631819b8b9572efe1d8.png

    bcc48c95db58476b8e0534983cebff19.png

    筛选过程代码示例：

    1. void heapadjust(int r[],int s,int m) {
    2. 	int rc = r[s];
    3. 	for(int j = s * 2; j <= m; j *= 2) {
    4. 		if(j < m && r[j] < r[j + 1])
    5. 			++j;
    6. 		if(rc > r[j])
    7. 			break;
    8. 		r[s] = r[j];
    9. 		s = j;
    10. 	}
    11. 	r[s] = rc;
    12. }

    636b240aa16d4391a5ecfa01cc43d698.png

    70207128f9c8458bb1f778dd3ff69836.png

    e5ad7bfca8314bd8a98f13b0564aadbe.png

    780d3265a92041e9934feed54781d648.png

     42a2e1cd52ce4bd9ac7337f71edf79fb.png

    54c12bc7420e475195892a6f59470ae0.png

    671b234b104d4970bc514beb03f1e839.png

    7fd907d1fbe54490be3c9e2a4f1532fd.png

    堆排序算法代码示例：

    1. void heapsort(int r[]) {
    2. 	int i;
    3. 	int n = sizeof(r)/sizeof(r[0]);
    4. 	for(i = n / 2; i >= 1; i--) {
    5. 		heapadjust(r,i,n);
    6. 	}
    7. 	for(i = n; i > 1; i--) {
    8. 		swap(r[1],r[i]);
    9. 		heapadjust(r,1,i - 1);
    10. 	}
    11. }

    算法性能分析 

    33e63f5337f848e9a46d35f5458eb66d.png

    cf4b9b8572164bac940a23b4b4ca39ac.png

    5.归并排序 

    7660e760839e45ac80bd140be067aa07.png

    0dece99e617d4376b7ef6247febeda84.png

    bbbf91830c254d7d93ed95a47470c152.png

    b4ece3626bc245a2b9e69dbce4f0e323.png

    c30640a959c349dda45e30eff2cbe2e0.png

    算法分析 

    f6332296b9d64ce4866397264638221b.png

    1dd0ba25d9db4da3b0820859a33fa1ae.png

    6.基数排序 

    b0ad518217664f8a9eb910d1857158a1.png

    43011b47e221404a972efa8903701bbe.png

    0718705fc28e4f82a6c64422d8e0a5ea.png

    72302846dc774055bf1c068bc60a278b.png

    算法分析 

    ccb1fb093e9841e0b8507a83ce6a04f2.png

    ebcf09f8ab8e42e6b745610b9b8055e0.png

    de13a598f8f64ce28e99c2d2fe4546de.png

    7.各种排序方法的综合比较 

    aa551f2faad04ef6a7477b2667030af0.png

    b4a4db34d1de442cb96ce0a2543e8bd2.png

    9805bb05d08f46df9305b2c70df93d62.png

    fef8b796742f4d8abf1b6513cffce133.png

    0b86f45f30fb41eaa1535e5fe0470be7.png

    8.总的代码

    1. #include
    2.  
    3. #define maxsize 20
    4.  
    5. typedef struct {
    6. 	int key;
    7. }redtype;
    8.  
    9. typedef struct {
    10. 	redtype r[maxsize + 1];
    11. 	int len;
    12. }sqlist;
    13.  
    14. void insertsort(sqlist &l) {
    15. 	int i,j;
    16. 	for(i = 2; i <= l.len; ++i) {
    17. 		if(l.r[i].key < l.r[i - 1].key){
    18. 			l.r[0] = l.r[i];
    19. 			for(j = i - 1; l.r[0].key < l.r[j].key; --j) {
    20. 				l.r[j + 1] = l.r[0];
    21. 			}
    22. 		}	
    23. 	}
    24. }
    25.  
    26. void binsertsort(sqlist &l) {
    27. 	for(int i = 2; i <= l.len; ++i) {
    28. 		l.r[0] = l.r[i];
    29. 		int low = 1;
    30. 		int high = i - 1;
    31. 		while(low <= high) {
    32. 			int mid = (low + high) / 2;
    33. 			if(l.r[0].key < l.r[mid].key)
    34. 				high = mid - 1;
    35. 			else low = mid + 1;
    36. 		}
    37. 		for(int j = i - 1; j >= high + 1; --j) {
    38. 			l.r[high + 1] = l.r[0];
    39. 		}
    40. 	}
    41. }
    42.  
    43. void shellinsert(sqlist &l, int dk) {
    44. 	int i,j;
    45. 	for(i = dk + 1; i <= l.len; ++i) {
    46. 		if(l.r[i].key < l.r[i - dk].key) {
    47. 			l.r[0] = l.r[i];
    48. 			for(j = i - dk; j > 0 && (l.r[0].key < l.r[j].key); j = j - dk) {
    49. 				l.r[j + dk] = l.r[i];
    50. 			}
    51. 			l.r[j + dk] = l.r[0];
    52. 		}
    53. 	}
    54. }
    55.  
    56. void shellsort(sqlist &l, int dlta[], int t) {
    57. 	for(int k = 0; k < t; ++k) {
    58. 		shellinsert(l, dlta[k]);
    59. 	}
    60. }
    61.  
    62. void bubblesort(sqlist &l) {
    63. 	int m,n,j;
    64. 	redtype x;
    65. 	for(m = 1; m <= n - 1; m++) {
    66. 		for(j = 1; j <= n - m; j++) {
    67. 			if(l.r[j].key > l.r[j + 1].key) {
    68. 				x = l.r[j];
    69. 				l.r[j] = l.r[j + 1];
    70. 				l.r[j + 1] = x;
    71. 			}
    72. 		}
    73. 	}
    74. }
    75.  
    76. void bubblesort2(sqlist &l) {
    77. 	int m,n,j;
    78. 	int flag = 1;
    79. 	redtype x;
    80. 	for(m = 1; m <= n - 1 && flag == 1; m++) {
    81. 		flag = 0;
    82. 		for(j = 1; j <= n - m; j++) {
    83. 			if(l.r[j].key > l.r[j + 1].key) {
    84. 				flag = 1;
    85. 				x = l.r[j];
    86. 				l.r[j] = l.r[j + 1];
    87. 				l.r[j + 1] = x;
    88. 			}
    89. 		}
    90. 	}
    91. }
    92.  
    93. int partition(sqlist &l,int low,int high) {
    94. 	l.r[0] = l.r[low];
    95. 	int pivotkey = l.r[low].key;
    96. 	while(low < high) {
    97. 		while(low < high && l.r[high].key >= pivotkey)
    98. 			--high;
    99. 		l.r[low] = l.r[high];
    100. 		while(low < high && l.r[low].key <= pivotkey)
    101. 			++low;
    102. 		l.r[high] = l.r[low];
    103. 	}
    104. 	l.r[low] = l.r[0];
    105. 	return low;
    106. }
    107.  
    108. void qsort(sqlist &l,int low,int high) {
    109. 	if(low < high) {
    110. 		int pivotloc = partition(l,low,high);
    111. 		qsort(l,low,pivotloc - 1);
    112. 		qsort(l,pivotloc + 1,high);
    113. 	}
    114. }
    115.  
    116. int main() {
    117. 	sqlist l;
    118. 	qsort(l,1,l.len);
    119. 	return 0;
    120. }
    121.  
    122. void selectsort(sqlist &l) {
    123. 	int i,j,k;
    124. 	for(i = 1; i < l.len; ++i) {
    125. 		k = i;
    126. 		for(j = i + 1; j < l.len; j++) {
    127. 			if(l.r[j].key < l.r[k].key)
    128. 				k = j;
    129. 			if(k != i) {
    130. 				redtype temp = l.r[i];
    131. 				l.r[i] = l.r[k];
    132. 				l.r[k] = temp;
    133. 			}
    134. 		}
    135. 	}
    136. }
    137.  
    138. void heapadjust(int r[],int s,int m) {
    139. 	int rc = r[s];
    140. 	for(int j = s * 2; j <= m; j *= 2) {
    141. 		if(j < m && r[j] < r[j + 1])
    142. 			++j;
    143. 		if(rc > r[j])
    144. 			break;
    145. 		r[s] = r[j];
    146. 		s = j;
    147. 	}
    148. 	r[s] = rc;
    149. }
    150.  
    151. void heapsort(int r[]) {
    152. 	int i;
    153. 	int n = sizeof(r)/sizeof(r[0]);
    154. 	for(i = n / 2; i >= 1; i--) {
    155. 		heapadjust(r,i,n);
    156. 	}
    157. 	for(i = n; i > 1; i--) {
    158. 		swap(r[1],r[i]);
    159. 		heapadjust(r,1,i - 1);
    160. 	}
    161. }
    162.

     

  • 相关阅读:
    华为云云耀云服务器L实例评测｜使用Linux系统与Docker部署.net/c#项目
    Pytest 的高级用法之插件开发
    阿里开源玄铁RISC-V系列处理器，推动RISC-V架构走向成熟
    实体解析实施的复杂性
    C语言—指针入门
    java判断空的方法
    Linux mmap原理
    【无标题】
    MySQL函数
    【计算机网络】IP协议第二讲（Mac帧、IP地址、碰撞检测、ARP协议介绍）
  • 原文地址：https://blog.csdn.net/2301_79431343/article/details/137049637