问题标题: 算法(可回答部分)

排    序

1. 选择排序

1. 基本思想：选择排序是把一组数据中正确的选择出来，排在最前面。每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。
2. 排序过程：

初始关键字   [49 38 65 97 76 13 27 49]

第一趟排序后 13 [38 65 97 76 13 27 49]

第二趟排序后 13 27 [65 97 76 13 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [76 97 65 49]

第五趟排序后 13 27 38 49 49 [97 65 76]

第六趟排序后 13 27 38 49 49 65 [97 76]

第七趟排序后 13 27 38 49 49 65 76 [97]

最后排序结果 13 27 38 49 49 65 76 97

总结：每一次选择一个最大（或最小）排在最前面，下一次就不处理这个数据了。

 

（3）参考程序：

#include<bits/stdc++.h>

using namespace std;

int main()

{

   int n,a[101];

   cin>>n;

   for(int i=1;i<=n;i++)

   cin>>a[i];

   for(int i=1;i<=n-1;i++)

   for(int j=i+1;j<=n;j++)

   if(a[i]>a[j])

   swap(a[i],a[j]);

   for(int i=1;i<=n;i++)

   cout<<a[i]<<" ";

   return 0;

}

 

2. 冒泡排序

1. 基本思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对（高在前，矮在后），若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，……，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。

 

（2）排序过程：

   例如有6个元素需要排序：6 5 3 4 1 2

第一趟排序：

5   6   3   4   1   2

5   3   6   4   1   2

 

第一趟结束，最后的6固定下来。

5   3   4   6   1   2

 

5   3   4   1   6   2

5   3   4   1   2   6

 

第二趟排序：  5   3   4   1   2   6

3   5   4   1   2   6

 

第二趟结束，5固定下来。

3   4   5   1   2   6

 

3   4   1   5   2   6

3   4   1   2   5   6

 

以此类推，完成所有排序。

总结：每隔一个，两两一比，把最后一个固定下来，把正确的冒泡出来，放到最后面。

（3）参考程序：

#include<bits/stdc++.h>

using namespace std;

int main()

{

   int n,a[1001];

   cin>>n;

   for(int i=1;i<=n;i++)

   cin>>a[i];

   for(int i=n-1;i>=1;i--)

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

   if(a[j]>a[j+1])

   swap(a[j],a[j+1]);

   for(int i=1;i<=n;i++)

   cout<<a[i]<<" ";

   return 0;

}

 

3. 插入排序

1. 基本思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这种排序方法即插入排序。
2. 排序过程：

     第0步：[36] 25 48 12 65 43 20 58

第1步：[25 36] 48 12 65 43 20 58

第2步：[25 36 48] 12 65 43 20 58

第3步：[12 25 36 48] 65 43 20 58

第4步：[12 25 36 48 65] 43 20 58

第5步：[12 25 36 43 48 65] 20 58

第6步：[12 20 25 36 43 48 65] 58

第7步：[12 20 25 36 43 48 58 65]

总结：分批次读入排序，读一个排好序，再读一个，把读进来的数据，插入到适合的位置。

（3）参考程序：

{

   int t,j,k,n,a[1001];

   cin>>n;

   for(int i=0;i<n;i++)

   cin>>a[i];

   for(int i=0;i<n;i++)

   {

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

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

     break;

     if(j!=i-1)

     {

        t=a[i];

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

        a[k+1]=a[k];

        a[k+1]=t;

     }

   }

   for(int i=0;i<n;i++)

   cout<<a[i]<<" ";

   return 0;

}

4. 桶排序

1. 基本思想：若待排序的值在一个明显有限范围内（整形）时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。
2. 排序过程：

原数：

10

2 3 1 2 4 55 3 55 3 2

排序后:

1 2 2 2 3 3 3 4 55 55

总结：用标记来做排序，如果这个数被输入了，就在他的标记数据加1，用桶排序必须知道这个排序数列的最大值。

3. 参考程序：

int a[1001];

int f[1001];

int main()

{

   int t,j,k,n;

   cin>>n;

   for(int i=1;i<=n;i++)

   {

     cin>>a[i];

     f[a[i]]++;

   }

   for(int i=1;i<=100;i++)

   {

     while(f[i]>0)

     {

        cout<<i<<" ";

        f[i]--;

     }

   }

   return 0;

}

5. 快速排序

1. 基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2. 排序过程：

输入：

5

3 4 1 5 2

 

1 3

1 4 3 5 2

2 1

1 4 3 5 2

2 5

1 2 3 5 4

3 3

1 2 3 5 4

4 5

1 2 3 4 5

我自己总结的，杜绝抄袭！！！

望采纳！

 

 

 

1

可以采纳楼上。

一贴多问

……………………