以下是几种基本的排序算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 |
#include <stdio.h> //冒泡排序 /* 气泡排序法 顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法， 将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。 基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生 任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如： 排序前：95 27 90 49 80 58 6 9 18 50 27 90 49 80 58 6 9 18 50 [95] 95浮出 27 49 80 58 6 9 18 50 [90 95] 90浮出 27 49 58 6 9 18 50 [80 90 95] 80浮出 27 49 6 9 18 50 [58 80 90 95] ...... 27 6 9 18 49 [50 58 80 90 95] ...... 6 9 18 27 [49 50 58 80 90 95] ...... 6 9 18 [27 49 50 58 80 90 95] 由于接下来不会再发生交换动作，排序提早结束 */ void BubbleSort(int data[],int len) { int temp; int i,j; for(i=0;i<len;i++) { for(j=0;j<len-i-1;j++) { if(data[j]>data[j+1]) { temp = data[j+1]; data[j+1] = data[j]; data[j] = temp; } } } } //选择排序 /* 将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个 最小值，并放入前端已排序部份的最后一个，例如： 排序前：70 80 31 37 10 1 48 60 33 80 [1] 80 31 37 10 70 48 60 33 80 选出最小值1 [1 10] 31 37 80 70 48 60 33 80 选出最小值10 [1 10 31] 37 80 70 48 60 33 80 选出最小值31 [1 10 31 33] 80 70 48 60 37 80 ...... [1 10 31 33 37] 70 48 60 80 80 ...... [1 10 31 33 37 48] 70 60 80 80 ...... [1 10 31 33 37 48 60] 70 80 80 ...... [1 10 31 33 37 48 60 70] 80 80 ...... [1 10 31 33 37 48 60 70 80] 80 ...... */ void selectSort(int data[],int len) { int i,j; int temp; for(i = 0;i<len;i++) { for(j = i+1;j<len;j++) { if (data[i]>data[j]) { temp = data[j]; data[j] = data[i]; data[i] = temp; } } } } // 快速排序快 // 速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边 // 数列进行排序，而影响快速排序法效率的正是轴心的选择。 // 令索引 i 从数列左方往右方找，直到找到大于 s 的数 // 令索引 j 从数列左右方往左方找，直到找到小于 s 的数 // 如果 i >= j，则离开回圈 // 如果 i < j，则交换索引i与j两处的值 // 将左侧的轴与 j 进行交换 // 对轴左边进行递回 // 对轴右边进行递回 /* [41] 24 76* 11 45 64 21 69 19 36* [41] 24 36 11 45* 64 21 69 19* 76 [41] 24 36 11 19 64* 21* 69 45 76 [41] 24 36 11 19 21 64 69 45 76 21 24 36 11 19 [41] 64 69 45 76 */ void quickSort(int data[],int left,int right) { int i= 0,j=0,s=0; int temp; //int len = sizeof(data)/sizeof(int); int len = right+1; if (left < right) { s = data[left]; i = left; j = right+1; while (1) { //向右查找,查找右边比s小的 while ((i+1) < len && data[++i] < s); //向左查找，查找左边比s大的 while ((j-1)> -1 && data[--j] > s); if (i >= j) break; //交换数据 把右边小的交换到左边，把左边大的交换到右边 temp = data[i]; data[i] = data[j]; data[j] = temp; } data[left] = data[j]; data[j] = s; quickSort(data,left,j-1); //左边递归 quickSort(data,j+1,right); //右边递归 } } //插入排序 /* 像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一 堆牌的适当位置，例如： 排序前：92 77 67 8 6 84 55 85 43 67 [77 92] 67 8 6 84 55 85 43 67 将77插入92前 [67 77 92] 8 6 84 55 85 43 67 将67插入77前 [8 67 77 92] 6 84 55 85 43 67 将8插入67前 [6 8 67 77 92] 84 55 85 43 67 将6插入8前 [6 8 67 77 84 92] 55 85 43 67 将84插入92前 [6 8 55 67 77 84 92] 85 43 67 将55插入67前 [6 8 55 67 77 84 85 92] 43 67 ...... [6 8 43 55 67 77 84 85 92] 67 ...... [6 8 43 55 67 67 77 84 85 92] ...... */ void insertSort(int data[],int len) { int temp; int i,j; for (i = 1 ;i<len;i++) { for (j=0;j<i;j++) { if (data[j]>data[i]) { temp = data[i]; data[i] = data[j]; data[j] = temp; } } } } //希尔（Shell）排序法（又称宿小增量排序，是1959年由D.L.Shell提出来的） /* 希尔排序属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序； 然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。 http://www.cnblogs.com/cj723/archive/2011/04/20/2021648.html */ void shellSort(int data[],int len) { int gap,i,j,temp; for(gap = len;gap>0;gap=gap/2) { for(i = gap;i<len;i++) { for(j=i-gap;(j>=0)&&(data[j]>data[j+gap]);j=j-gap) { temp = data[j]; data[j] = data[j+gap]; data[j+gap] = temp; } } } } int main(void) { int i = 0; int data[] = {10,9,8,7,6,3,5,1,2,4}; int len = sizeof(data)/sizeof(int); //BubbleSort(data,len); //selectSort(data,len); //quickSort(data,0,len-1); //insertSort(data,len); shellSort(data,len); for(i = 0;i<10;i++) { printf("%d ",data[i]); } printf("\n"); return 0; } |