排序有多种,里面的算法很巧妙,不写例子,只敲些核心代码。总体的有插入,选择,交换,分配,归并五种。有些没解释的是我感觉很难或者很偏。
一、插入
1.直接插入
最直接明了,依次拿出排序码中的每一个,与前面的数比较大小,插入相应的位置。直至所有的数字比较完毕。
int i,j,n;//n为排序码个数 data[n]为整个排序码组 Node temp;for(i = 1; i < n; ++i){ temp = data[i]; for(j = i-1; temp.value < data[i].value && j >= 0; j--) data[j+1] = data[j];//从取出的数字后面开始往前面取,比该数字大的往前移 if(j != i -1) data[j+1] = temp; //如果循环中取出的数字保持原位不动 则不用更改 }
2.二分法插入
不用依次对比,如果前面的排好序,只需要找到前面排序码组的中间数,数大则在中间的前面,反之即后。
int i,j,n,left,right,middle;//n为排序码个数 data[n]为整个排序码组 Node temp;for(i = 1; i < n; i++){ temp = data[i]; left = 0; right = i-1; while(left <= right){ middle = (left + right )/2; if(temp.value < data[middle].value) right = middle -1; left = middle + 1; } for(j = i-1; j >= left ; j--) data[j+1] = data[j];/ if(left != i -1) data[left] = temp; //将找到的这个位置放进temp }
3.表插入排序。
4.shell排序。
这个是D.L.Shell提出,而他的时间复杂度的东西在《计算机程序设计艺术》有提到,盖茨说过,如果把这一套书读懂,可以直接把简历发给他。
二、选择排序
1、直接排序。
最直接的方法,挑出排序码数组最小的数,放在第一位。再在剩余的数中挑出最小,放在第二位,很是直接,很简单。
2.堆排序。
三、交换排序。
1.冒泡排序。
很经典,像鱼泡一样的东西。
int i,j,n,turn;//n为排序码个数 data[n]为整个排序码组 Node temp;for(i = 1; i < n; ++i){ turn = 1; for(j = 0; j < n -i -1 ; j++){ temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; trun = 0; } if(turn) break;//当已经排好序后,后面无需再比较 }
2.快速排序。
四、分配排序
1.基数排序
五、归并排序
1.内排序
和shell排序很像,但是shell是以一个数字进行跳跃对比,而内排序是一块和一块对比。
2.外排序。
复杂。。。。。。