首页 / C# / C# 数据结构--排序[上]
C# 数据结构--排序[上]
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C# 数据结构--排序[上]，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2480字，纯文字阅读大概需要4分钟。
内容图文
概述 |
看了几天的排序内容，现在和大家分享一些常见的排序方法。
啥是排序？
个人理解的排序：通过对数组中的值进行对比，交换位置最终得到一个有序的数组。排序分为内存排序和外部排序。本次分享排序方法都为内存排序。
啥是排序的稳定性？
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
常见排序：
冒泡排序，选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序。
来张图展示一下种排序的关系：
冒泡排序（Bubble Sort） |
排序思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
复杂度：O(n^2)。
稳定性：稳定。
冒泡排序是我最早接触的排序算法，理解起来比较简单。排序入门级，容易理解，通过不断交换位置来排序。
代码实例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int temp;
for (int i = 0; i < list.Length; i++)
{
for (int j = i + 1; j < list.Length; j++)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
Console.WriteLine("冒泡排序的结果:{0}", string.Join(",", list));
第一个for循环取数据中一个值list[i]，第二个for循环已第一个for循环中的下一个值(j=i+1)开始取值list[j]。然后依次对比两值的大小list[i] > list[j]，如果数组中前面的值大于后面的值，替换他两的位置。始终保持数组中左边的值小于右边的值。
冒泡排序还有其他很多版本这里就不一一分享。
选择排序 (Simple Selection Sort) |
排序思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
复杂度：O(n^2)。
稳定性：稳定。
代码实例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int minIndex, temp;
for (int i = 0; i < list.Length; i++)
{
minIndex = i; /*把当前循环的值认为是最小值*/for (int j = i + 1; j < list.Length; j++)
{
if (list[j] < list[minIndex])
{
minIndex = j; /*进过N次循环我们找到最小值并赋值给minIndex*/
}
}
if (minIndex!=i)
{
temp = list[minIndex]; /*把当前循环出的最小值和list[i]替换。实现左边数据比右边数据要小*/
list[minIndex] = list[i];
list[i] = temp;
}
}
Console.WriteLine("选择排序的结果:{0}", string.Join(",", list));
第一个for循环数组中元素list[i],把当前循环的值默认为是最小值。记录下标赋值给minIndex。第二个for循环已第一个for循环中的下一个值(j=i+1)开始取值list[j]。然后依次和list[minIndex]对比，如果list[j]<list[minIndex]把循环中j的下标赋值给minIndex(保持minIndex为循环中最小值的下标)。到第二个for循环结束，然后替换当前循环的值list[i]和list[minIndex]的位置。始终保持数组中左边的值小于右边的值。
选择排序相对冒泡排序交换位置次数少，排序性能略优冒泡排序。
直接插入排序 (Straight Insertion Sort) |
排序思想：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
复杂度：O(n^2)。
稳定性：稳定。
代码实例：
int[] list = { 50, 10, 90, 30, 70, 40, 20 };
int temp, j;
for (int i = 1; i < list.Length; i++) /*从数据第二位开始循环 [无序序列] */
{
if (list[i] < list[i - 1])
{
temp = list[i];
for (j = i - 1; j >= 0 && temp < list[j]; j--) /*[有序序列] */
{
list[j + 1] = list[j];
}
list[j + 1] = temp;
}
}
Console.WriteLine("直接插入排序的结果:{0}", string.Join(",", list));
第一个for循环(从数组第二位置开始循环)数组中元素list[i]，如果循环的当前值list[i]比数组中上一个值list[i-1]要小,声明临时变量temp记录list[i]。然后根据第一个for循环的i值，反向循环数组,查询小于list[i]的下标位置。然后替换list[j+1]的值。
原文：http://www.cnblogs.com/caokai520/p/4350644.html
内容总结
以上是互联网集市为您收集整理的C# 数据结构--排序[上]全部内容，希望文章能够帮你解决C# 数据结构--排序[上]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。