视频解析 https://edu.csdn.net/course/play/7813
假定，你要为你的生日聚会邀请你的朋友和亲戚。对此，你需要给他们打电 话。 你正在拥有 10,000 条记录的电话本中查找名为 Steve 的电话号码。 然而，电话本中的记录是以随意顺序存储的。 要在这样一个目录中查找你朋友的电话号码，你需要按顺序在目录中浏览每 个条目。 这将非常耗时， 你如何解决此问题呢？
节省时间和高效搜索数据的简单解决方案是排序。
排序 是按照某些预定义的顺序或序列排列数据的过程。 此顺序可以是升序 或降序。
如果数据被排序，则可以直接转到存储以 ‘ S ’ 开头的姓名部分，因此减少了要 遍历的记录数。
选择排序算法
通过使用一算法实现在程序中排序。
一些排序算法有：
冒泡（Bubble）排序
选择排序
插入排序
壳（Shell）排序
合并排序
快速排序
堆排序
要选择合适的算法，你需要考虑以下方面：
执行时间
存储空间
编程工作
冒泡排序算法：
是最简单的排序算法之一
此算法具有二次方程增长阶，因此适合仅排序小列表
通过列表重复扫描、比较相邻元素和按错误顺序交换，此算法会有作用 .
编写一算法以实现冒泡排序。
冒 泡排序的算法是：
1.设置通道(圈数) = 1。
2.重复步骤3 区分0到n – 1通道中的j。
1.如果索引j处的元素大于索引j + 1处的元素，则交换这两个元素。
3.按1递增通道;圈数加1
4.如果通道 <= n-1，则转到第2步。
排序算法的效率按照比较次数来测量。
在 冒 泡排序中，通道 1 内有 n – 1 次比较，通道 2 中有 n – 2 次比较，依此类推。
比较总数 = (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1 = n(n – 1)/2 。
n(n – 1)/2 是 O(n2) 阶的级数。 因此， 冒 泡排序算法是阶 O(n2) 的算法。
什么是冒泡排序算法的增长阶？
答案：
n – 1 次比较
答案：
冒泡排序算法具有二次方增长阶
当实现冒泡排序算法时，在通道1中将执行多少次比较？
答案：
n – 1 次比较
使用选择排序来排序数据
选择排序算法：
选择排序还具有二次方程增长阶，且因此仅适用于排序小的列表。
选择排序通过列表反复扫描，每次扫描选择一项，然后将这一项移动到列表中 正确的位置。
要理解选择排序算法的实现，考虑数组中存储的未排序的数字列表。每次都寻找最小值，将最小值往前放
编写一算法以实现选择排序。
选择排序的算法：
1. 重复步骤 2 和 3 区分 0 到 n -2 通道中的 j
2. 找出 arr[j] 到 arr[n – 1] 中的最小值 ：
a. 设置 min_index = j
b. 重复步骤 c 区分 j + 1 到 n – 1 的 i
c. 如果 arr[i] < arr[min_index]:
i. min_index = i
3. 将 arr[j] 与 arr[min_index] 交换
在选择排序中， 在查找最小元素的通道 1 中有 n – 1 次比较。 在查找第二个最 小元素的通道 2 中有 n -2 次比较，依此类推。
比较总数 = (n – 1) + (n – 2) + (n – 3) + … + 3 + 2 + 1 = n(n – 1)/2
n(n – 1)/2 是 O(n2) 阶的级数。 因此，选择排序算法是阶 O(n2) 的算法。
插入排序算法：
具有二次方程增长阶，且因此仅用于排序小列表。
如果需要排序的列表几乎已经排序，则插入排序比冒泡排序和选择排序更有效 率。
要理解插入排序算法的实现，考虑数组中存储的未排序的数字列表。
要使用插入排序算法排序此列表：
你需要将列表分为两个子列表，即排序和未排序。
若要通过使用插入排序排序大小为n的列表，您需要执行(n– 1) 次通道。
最佳用例效率：
当列表已经被排序时产生最佳用例。
在这种情况下，您必须在每个通道中仅做一次比较。
在 n – 1 次通道中，您将需要做 n – 1 次比较。
插入排序的最佳用例效率是 O(n) 阶的。
最糟用例效率 ：
当列表按反向顺序排序时产生最糟用例效率。
在这种情况下，您需要在第 1 个通道中做 1 次比较，在第二个通道中做 2 次比较， 在第 3 个通道中做 3 次比较，在第 n – 1 个通道中做 n – 1 次比较。
插入排序的最糟用例效率是 O(n2) 阶的。
销售经理对 2004-2006 念市场上最佳冷饮销售员进行调查。 David 是一名软 件开发人员，他有一个冷饮品牌及其销售数据的文件。 David 必须向销售经 理提供排序好的数据。 文件总的数据或多或少都要进行排序。 存储此数据 最有效率的排序算法是哪个？为什么？
记录是以随意顺序存储的。
答案：
当列表部分排序时，插入排序提供了比泡泡排序和选择排序更好的有效。因此David应使用插入排序算法。
壳排序算法：
只要此列表已经部分排序且造成平均用例中的无效解决方案，则插入算法是高 效算法。
为了克服此限制，计算机科学家 D.L. Shell 提议改进插入排序算法。
新的算法称为壳（ Shell ）排序，是按照他的姓名命名的。
壳排序：
通过按若干位置的 距离 形成 多个子列表 分隔元素并进行比较来改进插入排序算 法
对 每个子列表 应用 插入排序 使元素朝着其正确的位置移动
帮助元素快速靠近正确的位置，因此减少了比较的次数
小结
在本章中，你已经学到：
排序是按照某些预定义的顺序或关键值排列数据的过程。 此顺序可以是升序或 降序。
用于排序数据有各种排序算法。 其中一些如下：
冒 泡排序
选择排序
插入排序
壳排序
合并排序
快速排序
堆排序
若要选择合适的算法，您需要考虑以下内容：
执行时间
存储空间
编程工作
冒泡排序和选择排序算法具有二次方程增长阶，且因此仅适用于排序小的列表。
插入排序执行不同次数的比较，这取决于最初的元素分阶。 当元素已经处于排 序阶，则插入排序需要进行极少比较。
如果需要排序的列表几乎已经排序，则插入排序比冒泡排序和选择排序更有效率。
通过比较按若干位置的距离分隔的元素，壳排序改善了插入排序 。 这帮助元素快 速靠近正确的位置，因此减少了比较的次数。
/**********************************************************/
/*描述：编写程序将10个学生的得分存储到数组中。通过使用冒泡排序算法，来排序数组中的元素，排序数组后，显示排序后数组的元素*/
using System;
class List
{
//定义长度为20的整型数组
private int[]a=new int[20]; //20是最大长度.
//数组的个数
private int n;
//定义一个方法读取数据元素到数组
public void read()
{
//获得
while(true)
{
Console.WriteLine("请输入数组元素的个数<20之内>：");
string s=Console.ReadLine();
n=Int32.Parse(s);//转换为整型.Convert.ToInt32(s)
if(n<=20)
break; //跳出循环
else
Console.WriteLine("\n数组只能够容纳20个数组元素.\n");
}//while结束.
Console.WriteLine("");
Console.WriteLine("----------------------------------");
Console.WriteLine("-----请输入数组元素---------------");
Console.WriteLine("----------------------------------");
//用户将数句元素输入数组
for(int i=0;i
关注
打赏
![]()
1688896170
查看更多评论
