正文
算法：冒泡排序（Bubble Sort）、插入排序（Insertion Sort）和选择排序（Selection Sort）总结
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
背景
这两天温习了 5 中排序算法，之前也都看过它们的实现，因为没有深入分析的缘故，一直记不住谁是谁，本文就记录一下我学习的一些心得。
三种排序算法可以总结为如下：
- 都将数组分为已排序部分和未排序部分。
- 冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行 交换 ，将最大元素交换到最右端。
- 插入排序将已排序部分定义在左端，将未排序部分元的第一个元素 插入 到已排序部分合适的位置。
- 选择排序将已排序部分定义在左端，然后 选择 未排序部分的最小元素和未排序部分的第一个元素交换。
冒泡排序
代码
public static void Sort(T[] items)
{
if (items.Length < )
{
return;
} int swappedTimes;
do
{
swappedTimes = ;
// 重复的遍历数组。
for (var i = ; i < items.Length; i++)
{
// 每次遍历都比较两个元素，如果顺序不正确就把他们交换一下。
if (items[i - ].CompareTo(items[i]) > )
{
Swap(items, i - , i);
swappedTimes++;
}
}
} while (swappedTimes > );// 如果遍历后只交换了 1 次或 0 次，排序结束。
}
示例
【4，3，2，1】
【3，4，2，1】
【3，2，4，1】
【3，2，1，4】
【2，3，1，4】
【2，1，3，4】
【1，2，3，4】
插入排序
代码
public static void Sort(T[] items)
{
for (
var sortedRangeEndIndex = ;
sortedRangeEndIndex < items.Length;
sortedRangeEndIndex++)
{
if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - ]) < )
{
int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]);
Insert(items, sortedRangeEndIndex, insertIndex);
}
}
} private static int FindInsertionIndex(T[] items, T valueToInsert)
{
for (var i = ; i < items.Length; i++)
{
if (items[i].CompareTo(valueToInsert) > )
{
return i;
}
} throw new InvalidOperationException();
} private static void Insert(T[] items, int indexInsertingFrom, int indexInsertingAt)
{
var temp = items[indexInsertingFrom]; for (var i = indexInsertingFrom; i > indexInsertingAt; i--)
{
items[i] = items[i - ];
} items[indexInsertingAt] = temp;
}
示例
【4，3，2，1】
【3，4，2，1】
【2，3，4，1】
【1，2，3，4】
选择排序
代码
public static void Sort(T[] items)
{
for (
var sortedRangeEndIndex = ;
sortedRangeEndIndex < items.Length;
sortedRangeEndIndex++)
{
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEndIndex);
Swap(items, sortedRangeEndIndex, nextIndex);
}
} private static int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEndIndex)
{
T currentSmallItem = items[sortedRangeEndIndex];
int currentSmllIndex = sortedRangeEndIndex; for (var i = sortedRangeEndIndex + ; i < items.Length; i++)
{
if (currentSmallItem.CompareTo(items[i]) > )
{
currentSmallItem = items[i];
currentSmllIndex = i;
}
} return currentSmllIndex;
}
示例
【4，3，2，1】
【1，3，2，4】
【1，2，3，4】
【1，2，3，4】
备注
每周坚持学习数据结构和算法中。。。
