排序算法总结（一）
访问www.tomcoding.com网站，学习Oracle内部数据结构，详细文档阐明，下载Oracle的exp/imp，DUL，logminer，ASM工具的源代码，学习高技术含量的内容。冒泡排序
这个算法可以说是排序算法中最著名的一个了，名字独特，也好理解，在一个数组中有n个元素，扫描整个数组中没有排序的元素，从第一个元素开始，每个元素与它后面的元素比较，数值小的放在前面，数值大的放在后面，那么经过第一轮扫描，最大的数值就放在了数组最后的位置，就像每个元素是一个气泡，最大的气泡开始浮到数组顶端。第二轮扫描，由于最大的元素已经找到，需要找第二大的元素，这时扫描的元素个数少了一个，变为n-1，经过第二轮扫描，第二大的元素放到了数组倒数第二的位置。依次类推，第三次扫描元素个数变为n-2，第三大的元素排到了倒数第三的位置。这样每次扫描的元素越来越少，最后扫描到未排序的元素只有一个时，排序就结束了，这时数组中的数值按照升序排列好了。
第0轮：扫描n-1个元素，从0开始到n-2，每个元素j与后一个元素j+1比较，小的在前，大的在后，假如不同等时，要把这两个元素交换位置。
第1轮：扫描n-2个元素，从0开始到n-3，每个元素j与后一个元素j+1比较。
第2轮：扫描n-3个元素，从0开始到n-4，每个元素j与后一个元素j+1比较。
第3轮：扫描n-4个元素，从0开始到n-5，每个元素j与后一个元素j+1比较。
……
第n-2轮：扫描1个元素，第0个和第1个元素比较。
第n-1轮：扫描0个元素，结束。其实在上一轮比较完，就可以结束了。
用C语言编写一个函数实现冒泡排序算法，i表示扫描的轮的序号，j表示每一轮中扫描的元素序号（数组下标）。
/* ai是要排序的整数数组指针
* n是数组中元素的个数
*/
void bubble_sort(int *ai, int n)
{
int i, j, k;
/* 循环n-1轮 */
for (i = 0; i < (n-1); i++) {
/* 每一轮，扫描n-1-i个元素 */
for (j = 0; j < (n-1-i); j++) {
if (ai > ai) {
/* 前一个元素比后一个大，交换位置，否则不消交换 */
k = ai;
ai = ai;
ai = k;
}
}
}
}
选择排序
这个也是经常用到的排序算法，乃至是最容易想到的算法，虽然不好确定它的名字。工作原理如下，把要排序的数组分成两部分，第一部分是排过序的元素集合，第二部分是没有排过序的元素集合，开始时第一部分的元素个数为0，第二部分为全部元素，算法要举行多轮选择，每一轮选择都是从第二部分元素中找到最小的元素，把这个元素放到第一部分的末端，这样经过多轮选择后，第一部分越来越大，第二部分越来越小，当第二部分元素数为0时，排序就结束了。
实现算法时也有两个关键点要确定，第一个是循环的轮数，假设数组中元素的个数是n，每一轮要找到一个最小数据，所以原则上应该找n轮，其实找到n-1轮时，最后一轮就剩下一个元素了，没有比较的必要了，所以循环的轮数为n-1。第二个是每轮查找元素的个数，看下表。
第0轮，扫描n-0个元素，从0到n-1
第1轮，扫描n-1个元素，从1到n-1
第2轮，扫描n-2个元素，从2到n-1
第3轮，扫描n-3个元素，从3到n-1
……
第n-2轮，扫描2个元素，从n-2到n-1
第n-1轮，扫描1个元素，从n-1到n-1
用C语言写一个函数实现这个算法。
/* ai 是要排序的整数数组
* n 是数组中元素的个数
*
* 函数中i，j是计数变量
* min_index是第二部分数组中最小值的元素下标
* min变量暂存第二部分中最小值
* tail是第一部分的尾部位置
* start是第二部分开始扫描的起始位置
*/
static void selection_sort(int *ai, int n)
{
int i, j, k, min_index;
int min;
int tail;
int start;
/* 开始时，第一部分没有元素，尾部在第0个元素 */
tail = 0;
for (i = 0; i < (n-1); i++) {
start = tail;
min = ai;
min_index = -1;
for (j = start; j < n; j++) {
if (ai < min) {
min_index = j;
min = ai;
}
}
if (min_index != -1) {
/* 找到了最小值，交换元素 */
k = ai;
ai = ai;
ai = k;
}
tail++;
}
}
这个函数看起来有些复杂，我们来简化一下。从上面看tail其实就是i的位置，start是i的下一个位置，min值是扫描第二部分的第一个元素，把这些简化后，得到下面的函数。
void selection_sort(int *ai, int n)
{
int i, j, k;
int min_index;
for (i = 0; i < (n-1); i++) {
min_index = i;
for (j = i+1; j < n; j++) {
if (ai < ai)
min_index = j;
}
if (min_index != i) {
/* 交换元素 */
k = ai;
ai = ai;
ai = k;
}
}
}
查抄排序结果
写一个函数来查抄一下排序后的元素顺序有没有错误，方法很简单，在数组中遍历一次，看看前一个元素是否比后一个元素大，假如大就阐明排序堕落了。
void check_result(int *ai, int n)
{
int i;
for (i=0; i<n-1; i++) {
if (ai > ai) {
fprintf(stderr, "error, element[%d]=%d, element[%d]=%d\n\n", i, ai, i+1, ai);
return;
}
}
fprintf(stdout, "element is sorted.\n\n");
}
写一个程序测试一下排序结果。
int main(int argc, char *argv[])
{
static int chaos = {23, 6, 235, 89, 4, 12, 76, 35, 129, 30, 77, 15, 61, 44, 49, 88};
int array;
fprintf(stdout, "test for bubble_sort function.\n\n");
memcpy(array, chaos, 16*sizeof(int));
bubble_sort(array, 16);
check_result(array, 16);
fprintf(stdout, "test for selection_sort function.\n\n");
memcpy(array, chaos, 16*sizeof(int));
selection_sort(array, 16);
check_result(array, 16);
return (0);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]