请选择 进入手机版 | 继续访问电脑版
查看: 588|回复: 0

[云计算] c语言实现基本排序算法

688

主题

688

帖子

2083

积分

猿er

Rank: 1

积分
2083
发表于 2016-8-14 17:58:25
c语言实现基本排序算法
  1. /*************************************************************************
  2. > File Name: sort-algorithm.c
  3. > Author: wustrive
  4. > Mail: [email protected]
  5. > Created Time: Tue 18 Mar 2014 12:00:48 PM CST
  6. ************************************************************************/
  7. #include<stdio.h>
  8. /*希尔(Shell)排序法(又称宿小增量排序,是1959年由D.L.Shell提出来的)*/
  9. void shellsort(int v[],int n){
  10. int gap,i,j,temp;
  11. for(gap = n/2; gap > 0; gap /= 2){
  12. for(i = gap; i < n; i++){
  13. for(j = i-gap; (j >= 0)&&(v[j] > v[j+gap]); j -= gap){
  14. temp = v[j];
  15. v[j] = v[j+gap];
  16. v[j+gap] = temp;
  17. }
  18. }
  19. }
  20. }
  21. /*二分插入法*/
  22. void HalfInsertSort(int a[],int len){
  23. int i, j, temp;
  24. int low, high, mid;
  25. for(i = 0; i < len; i++){
  26. temp = a[i];
  27. low = 0;
  28. high = i-1;
  29. while(low <= high){ //12548756
  30. mid = (low + high)/2;
  31. if(a[mid] > temp){
  32. high = mid - 1;
  33. }else{
  34. low = mid + 1;
  35. }
  36. }
  37. for(j = i-1; j > high; j--){
  38. a[j+1] = a[j];
  39. }
  40. a[high+1] = temp;
  41. }
  42. }
  43. /*直接插入排序 */
  44. void InsertionSort(int input[], int len){
  45. int i, j, temp;
  46. for(i = 1; i < len; i++){
  47. temp = input[i];
  48. for(j = i-1; j > -1&&input[j]>temp; j--){
  49. input[j + 1] = input[j];
  50. input[j] = temp;
  51. }
  52. }
  53. }
  54. /*带哨兵的直接插入排序*/
  55. /**
  56. ** 带哨兵的直接插入排序,数组的第一个元素不用于存储有效数据
  57. ** 将input[0]作为哨兵,可以避免判定input[j]中,数组是否越界
  58. ** 因为在j--的过程中,当j减小到0时,变成了input[0]与input[0]
  59. ** 自身进行比较,很明显这个时候说明位置i之前的数字都比input[i]小
  60. ** 位置i上的数字不需要移动,直接进入下一轮的插入比较。
  61. *
  62. **/
  63. void InsertionSortWithPiquet(int input[], int len){
  64. int i, j;
  65. for(i = 2; i < len; i++){
  66. input[0] = input[i];
  67. for(j = i-1; input[j] > input[0]; j--){
  68. input[j+1] = input[j];
  69. input[j] = input[0];
  70. }
  71. }
  72. }
  73. /*冒泡排序*/
  74. void Bublesort(int a[], int n){
  75. int i, j, k;
  76. for(j = 0; j < n; j++){
  77. for(i = 0; i < n-j; i++){
  78. if(a[i] > a[i+1]){
  79. k = a[i];
  80. a[i] = a[i+1];
  81. a[i+1] = k;
  82. }
  83. }
  84. }
  85. }
  86. /*选择排序*/
  87. void Selectsort(int a[], int n){
  88. int i, j, temp;
  89. for(i = 0; i < n; i++){
  90. for(j = i + 1; j <= n; j++){
  91. if(a[i] > a[j]){
  92. temp = a[i];
  93. a[i] = a[j];
  94. a[j] = temp;
  95. }
  96. }
  97. }
  98. }
  99. /*快速排序*/
  100. void quick_sort(int data[], int low, int high){
  101. int mid;
  102. if(low < high){
  103. int Partition(int data[], int low, int high);
  104. mid = Partition(data, low, high);
  105. quick_sort(data, low, mid-1);
  106. quick_sort(data, mid+1, high);
  107. }
  108. }
  109. int Partition(int data[], int low, int high){
  110. int mid;
  111. data[0] = data[low];
  112. mid = data[low];
  113. while(low < high){
  114. while((low < high) && (data[high]) >= mid){
  115. --high;
  116. }
  117. data[low] = data[high];
  118. while((low < high) && (data[low] < mid)){
  119. ++low;
  120. }
  121. data[high] = data[low];
  122. }
  123. data[low] = data[0];
  124. return low;
  125. }
  126. int main(){
  127. int v[] = {0,2,3,4,5,2,3,4,1,7,-33,2};
  128. //shellsort(v,7);
  129. int len = sizeof(v)/sizeof(int); //数组长度
  130. //HalfInsertSort(v,len);
  131. //InsertionSort(v,len);
  132. //InsertionSortWithPiquet(v,len);
  133. //Bublesort(v,len);
  134. //quick_sort(v,0,len);
  135. Selectsort(v,len);
  136. for(int i = 0; i < len; i++){
  137. printf("%d ",v[i]);
  138. }
  139. }
复制代码



上一篇:单片机实时时钟
下一篇:冒泡排序
回复

使用道具 举报