视频解析 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<n;i++) { Console.Write("<"+(i+1)+">"); string s1=Console.ReadLine(); a[i]=Int32.Parse(s1); }//<1>20 <2>20 <3>90 } //*************************显示数组元素************************* public void display() { Console.WriteLine(""); Console.WriteLine("-------------------------------------------"); Console.WriteLine("------------排序过后的元素-----------------"); Console.WriteLine("-------------------------------------------"); for(int j=0;j<n;j++) { Console.WriteLine(a[j]); } } /***************冒泡排序方法***************************/ public void BubbleSortArray() { //圈数1--->n-1 for(int i=1;i<=n-1;i++) //i:1;不是数组下标，是通道次数 { //里面做的工作是两个相邻数字的比较；如果不符合升序排列，则交换.j指数组下标. for(int j=0;j<n-i;j++) //注意：比较n-i次 { if(a[j]>a[j+1]) //则说明不符合升序排列,需要交换 { int temp; temp =a[j]; a[j]=a[j+1]; a[j+1]=temp; } }//内层交换结束 }//圈数循环结束. } /******************Main()方法*********************/ public static void Main(string[]args) { List myList=new List(); myList.read(); //读取数据元素 myList.BubbleSortArray(); //调用冒泡排序算法 myList.display(); //显示数组元素 Console.WriteLine("\n\n按任意键退出."); Console.Read(); } }
--------------------------
/* 描述：使用选择排序，来排列包含10个学生得分的整数数组,升序排列. */ using System; class Selection { //定义数组的大小 private int[]a=new int[20]; //数组元素的个数. private int n; //定义接受数组元素的函数 void read() { while(true) { Console.WriteLine("请输入数组元素的个数："); string s=Console.ReadLine(); n=Int32.Parse(s); if(n<=20) break; else Console.WriteLine("\n数组只能够接收20个元素.\n"); } Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------请输入数组元素---------"); Console.WriteLine("---------------------------------"); //用户输入数据 for(int i=0;i<n;i++) { Console.Write("<"+(i+1)+">"); string s1=Console.ReadLine(); a[i]=Int32.Parse(s1); } } //显示数组内容的函数 void display() { Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------排序后的数组元素-------"); Console.WriteLine("---------------------------------"); for(int j=0;j<n;j++) { Console.WriteLine(a[j]); } } /* 选择排序算法：每次选择最小值，将其依次往前排;借助于下标标记来实现. */ public void SelectionSortArray() { //外面进行了n-1圈 for(int i=0;i<n-1;i++) { //定义个指示最小值标记的变量 int min_index=i; //查找选择最小值所对应的标记（下标) for(int j=i+1;j<=n-1;j++) { //判断如果有值比，最小值下标对应的数还小，则将该值对应的下标给min_index if(a[j]<a[min_index]) min_index=j; }//结束寻找最小值下标 //交换:a[i]<-->a[min_index] swap(i,min_index); //调用交换方法. } } //交换两个值的方法 public void swap(int x,int y) { int temp; temp=a[x]; a[x]=a[y]; a[y]=temp; } //类的主方法 public static void Main() { Selection sec=new Selection(); sec.read(); sec.SelectionSortArray(); sec.display(); Console.WriteLine("\n\n请按任意键结束!."); Console.Read(); } }
---------------------
/* 描述：使用插入排序，来排列包含10个学生得分的整数数组。 */ using System; class Insertion { //定义数组的大小 private int[]a=new int[20]; //数组元素的个数. private int n; //定义接受数组元素的函数 void read() { while(true) { Console.WriteLine("请输入数组元素的个数："); string s=Console.ReadLine(); n=Int32.Parse(s); if(n<=20) break; else Console.WriteLine("\n数组只能够接收20个元素.\n"); } Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------请输入数组元素---------"); Console.WriteLine("---------------------------------"); //用户输入数据 for(int i=0;i<n;i++) { Console.Write("<"+(i+1)+">"); string s1=Console.ReadLine(); a[i]=Int32.Parse(s1); } } //显示数组内容的函数 void display() { Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------排序后的数组元素-------"); Console.WriteLine("---------------------------------"); for(int j=0;j<n;j++) { Console.WriteLine(a[j]); } } //****使用插入排序的方法 public void InsertionSortArray() { //重复n-1次来将为排序列表数据放入已排序列表 for(int i=1;i<n;i++) { int temp=a[i]; int j=i-1; //如果j>=0或大于临时值,则执行如下操作 while((j>=0)&&(a[j]>temp)) { a[j+1]=a[j]; j--; } a[j+1]=temp; } } //交换两个值的方法 public void swap(int x,int y) { int temp; temp=a[x]; a[x]=a[y]; a[y]=temp; } //类的主方法 public static void Main() { Insertion sec=new Insertion(); sec.read(); sec.InsertionSortArray(); sec.display(); Console.WriteLine("\n\n请按任意键结束!."); Console.Read(); } }
--------------------------------------------------------
/* 描述：使用插入排序，来排列包含10个学生得分的整数数组。 */ using System; class ShellSorter { //数组元素的个数. private static int n=0; //定义数组的大小 private int[]a; //定义接受数组元素的函数 void read() { while(true) { Console.WriteLine("请输入数组元素的个数："); string s=Console.ReadLine(); n=Int32.Parse(s); a=new int[n]; if(n<=20) break; else Console.WriteLine("\n数组只能够接收20个元素.\n"); } Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------请输入数组元素---------"); Console.WriteLine("---------------------------------"); //用户输入数据 for(int i=0;i<n;i++) { Console.Write("<"+(i+1)+">"); string s1=Console.ReadLine(); a[i]=Int32.Parse(s1); } } //显示数组内容的函数 void display() { Console.WriteLine(""); Console.WriteLine("---------------------------------"); Console.WriteLine("----------排序后的数组元素-------"); Console.WriteLine("---------------------------------"); for(int j=0;j<n;j++) { Console.Write(" "+a[j]); } } //****使用希尔排序的方法 public void ShellSort() { for (int step = a.Length/ 2; step >= 1; step = step / 2) { for (int i = step; i < a.Length; i+=step) { int temp = a[i]; int j = i - step; while (j >= 0 && temp < a[j]) { a[j + step] = a[j]; j-=step; } a[j + step] = temp; } } } //交换两个值的方法 public void swap(int x,int y) { int temp; temp=a[x]; a[x]=a[y]; a[y]=temp; } //类的主方法 public static void Main() { ShellSorter sec=new ShellSorter(); sec.read(); sec.ShellSort(); sec.display(); Console.WriteLine("\n\n请按任意键结束!."); Console.Read(); } }
