十大经典排序算法（附自实现排序算法演示软件）

自己使用 Unity 实现的一个排序算法演示系统：https://github.com/czc1999/sorting-visualization

基本概念

稳定性的概念：假定在待排序的序列中，等于，且在之前，而在排序后的序列中，保证仍在之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定性的意义：如果只是简单的进行数字的排序，那么稳定性没什么意义。但是，比如对不同班级的同学，先按照分数排序，再按照班级排序，这时稳定的排序就能保证按班级排完序，分数依然有序，也就是相同班级的所有同学的相对次序是不变的。即：以某种关键字的方式排序后，能不影响到其他关键字原来排序的结果。

冒泡排序

简单冒泡排序

实现方式有多种，常见的以下两种。

根据次第关系，从前往后，依次比较相邻的两个元素，将较大的元素向后移，每轮遍历把最小数移动到无序部分的最后一个，重复该操作，直至数组有序

平均时间复杂度： $O(n^2)$

空间复杂度： $O (1)$

稳定性：稳定

根据下标关系，每轮遍历把最小数移动到无序部分的最后一个

鸡尾酒排序（双向冒泡排序）

冒泡排序的轻微变形。不同的地方在于大循环下第一个循环是从开始扫到结束，将最大的归到最后；第二个循环是从倒数第二个位置往开始端扫，将最小的归到开始的位置，而冒泡排序则仅仅从低到高去比较序列里的每个元素。可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对（由低到高），对于一些特殊数据，如（49,38,65,97,76,13,27,14,10），鸡尾酒排序只要访问一次序列就可以完成排序，但如果使用冒泡排序需要八次。

复杂度，稳定性无变化

选择排序

简单选择排序

起初整个数组都是无序的，遍历一轮找出最小元素，与无序部分首部元素（数组的第一个元素）交换，此时第一个元素已经是有序的了，再从剩余元素中找最小元素，与无序部分首部元素（数组的第二个元素）交换，以此类推，直至数组有序

平均时间复杂度： $O(n^2)$

空间复杂度： $O (1)$

稳定性：不稳定

优化选择排序

每一轮遍历找出无序部分的最小和最大的元素，分别放至无序部分的头部和尾部