c语言以ascii字符堆排序,c语言练习

经常练练，有易于身心健康，避免出没遇到熊。

1 请编写函数fun，对长度为7个字符的字符串，除首、尾字符外，将其余5个字符按ASCII码降序排列。

例如，若原来的字符串为CEAedca，则排序后输出为CedcEAa。

注意：部分源程序给出如下。

请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入所编写的若干语句。

#include

#include

#include

void fun( char *s,int num)

{

char c, *p_start;

int i, j;

p_start = s + 1;

方式一 错误1：

c = *p_start;

for (i = 0; i < 4; i++)

{

for (j = 0; j < 5 - i - 1; j++)

{

if (*(p_start + j) < *(p_start + j + 1))

{

c = *(p_start + j + 1);

*(p_start + j + 1) = *(p_start + j);

*(p_start + j) = c;

}

}

}

方式二 错误1：

c = *p_start;

for (i = 0; i < 4; i++)

{

for (j = 0; j < 5 - i - 1; j++)

{

if (c < *(p_start + j + 1))

{

*(p_start + j) =   *(p_start + j + 1) ;

*(p_start + j + 1) =c;

} else

c = *(p_start + j + 1);//c 保持为最小

}

}

方式二 正确1：

c = *p_start;

for (i = 0; i < 4; i++)

{

for (j = 0; j < 5 - i - 1; j++)

{

if (c < *(p_start + j + 1))//我这种冒泡是把小的泡泡冒出去，标准的是把小的保持不动。

{

c = *(p_start + j + 1);

*(p_start + j + 1) = *(p_start + j);

*(p_start + j) = c;

}

c = *(p_start + j + 1);

}

}

方式二正确2：其实我觉得这个更像冒泡，这边是把最小的推到最右边，标准冒泡是每个人来跟自己比，并把最大的留下，不形象。

for (i = 0; i < 4; i++)

{

c = *p_start;

for (j = 0; j < 5 - i - 1; j++)

{

if (c < *(p_start + j + 1))

{

*(p_start + j) =   *(p_start + j + 1) ;

*(p_start + j + 1) = c;

} else

c = *(p_start + j + 1);

}

}

}

标准冒泡：

void fun2( char *s,int num)

{

char temp;

int i, j;

char *arr = s + 1;

for (i = 0; i < 5 - 1; i++)

{

for (j = i + 1; j < 5; j++)

{

if (arr[i] < arr[j])

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

}

printf("After sorting, the strings is : %sn", s);

}

选择排序：

思想：n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前

无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和

R(i..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

常见的选择排序细分为 简单选择排序、树形选择排序( 锦标赛排序)、 堆排序。上述算法仅是 简单选择排序的步骤。

通俗的解释：

对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

void fun3( char *s,int num)

{

char temp;

int i, j, k;

char *arr = s + 1;

for (i = 0; i < 5 - 1; i++)

{

k = i;

for (j = i + 1; j < 5; j++)

{

if (arr[k]< arr[j]) //这边把k误写为i 就直接错了。这个比较跟 冒泡是一模一样。

{

k = j;

}

}

if (i != k)

{

temp = arr[k];

arr[k] = arr[i];

arr[i] = temp;

}

}

}

插入排序：

包括： 直接插入排序，二分插入排序(又称折半插入排序)， 链表插入排序， 希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲，就是两个相等的数不会交换位置) 。

将n个元素的数列分为已有序和无序两个部分，如

插入排序过程示例 下所示：

{{a1}，{a2，a3，a4，…，an}}

{

{a1⑴，a2⑴}

，{a3⑴，a4⑴ …，an⑴}}

//红色有序

…

{{a1(n-1)，a2(n-1) ，…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素

从后往前逐个进行比较

，找出插入位置，将该元素插入到有序数列的合适位置中。

算法设计有很多方法。插入排序使用的是增量(incremental)方法；在排好子 数组A[1..j-1]后，将A[j]插入，形成排好序的子数组A[1..j]；

步骤

⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；

⒉处理第i个元素时(i=2,3，…，n)，数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。

用ai与ai-1

，a i-2，…，a1进行比较，找出合适的位置将ai插入；

⒊重复第二步，共进行n-i次插入处理，数列全部有序。

正确插入：

void fun444( char *s,int num)

{

char temp;

int i = 0, j, k = 0;

char *arr = s + 1;

//这个不是最优化

for (i = 0; i < 5 - 1; i++)

{

for (j = i + 1; j > 0;j--) //在这边将要循环到0， 这个是浪费。

{

if (arr[j - 1] <  arr[j])

{

temp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = temp;

}

}

}

//这个是标准的：

}

插入排序错误代码：

void fun4( char *s,int num)

{

char temp;

int i = 0, j, k = 0;

char *arr = s + 1;

for (i = 0; i < 5 - 1; i++)

{

for (j = i + 1; j > 0; j--)

{

if (arr[j - 1] >  arr[i + 1])

{

k = j - 1 ;

break;

}

}

if (k < i && k == 0)

{

temp = arr[i+1];

for(k = i ; k > 0; k--)

{

arr[k + 1] = arr[k];

}

arr[k] = temp;

}

else if (k < i && k > 0 )

{

temp = arr[i+1];

for(j = i ; j > k; j--)

{

arr[j + 1] = arr[j];

}

arr[j] = temp;

}

}

}

===================

main()

{

char s[10];

printf(“输入7个字符的字符串:”);

gets(s);

fun(s,7);

printf(“n%s”, s);

}