根据时间复杂度的不同，主流的排序算法可以分为3大类：
1. 时间复杂度为O(n2)的排序算法
冒泡排序
选择排序
插入排序
希尔排序(希尔排序比较特殊，它的性能略优于O(n2)，但是又比不上 O(nlogn)，姑且将它归为本类)
2. 时间复杂度为O(nlogn)的排序算法
快速排序
归并排序
堆排序
3. 时间复杂度为线性的排序算法
计数排序
桶排序
基数排序
此外排序算法还可以根据其稳定性，划分为稳定排序和不稳定排序
即如果值相同的元素在排序后仍保持着排序前的顺序，则这样的排序算法是稳定排序，如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序，
栗子：
冒泡排序
如需要从小到大排序一个无序序数列 5,8,6,3,9,2,1,7
按照冒泡排序的思想：**把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或者等于右侧相邻元素时，位置不变。**详细过程如下：
这时，元素 9 作为数列中最大的元素，就来到了最右侧，冒泡排序第一轮结束，数列最右侧元素 9 的位置，可以认为是一个有序区域，有序区域目前只有一个元素
接下来进行第二轮排序：
第二轮结束后，数列右侧有序区域有了两个元素，
第三轮至第七轮的状态如下：
这就是冒泡排序的整体思路，
冒泡排序是一种稳定排序，值相等的元素，并不会打乱原有的顺序，该算法要遍历n -1 轮，每一轮都要遍历 n - 1 - 有序区域长度个元素， 所以时间复杂度为 O(n2)
代码实现
1 function bubbleSort(list:Array<number>) { 2 // 注意 这里是 < length - 1 也就是说遍历次数为 n-1 3 for (let i = 0; i < list.length - 1; i++) { 4 // 这里 < length -1的原因同上 - i的原因是 有序区 5 for (let j = 0; j < list.length - i -1; j++) { 6 if( list[j] > list[j+1]) { 7 let temp = list[j]; 8 list[j] = list[j+1]; 9 list[j+1] = temp 10 11 12 } 13 } 14 } 15 return list 16 } 17
优化1-标识是否已经有序
回顾刚才数列 5,8,6,3,9,2,1,7 的排序细节，经过 第 6 轮排序后，执行 第 7 轮的时候，其实整个数列已经是有序的了，但是还是执行了第 7 轮，
在这种情况下，其实可以添加一个标识，如果一轮下来未执行交换，那么可以确定数列已经有序，就可以提前结束遍历了
优化代码如下
1 // 是否有序标识优化 2 function bubbleSortTwo(list:Array<number>) { 3 // 注意 这里是 < length - 1 也就是说遍历次数为 n-1 4 for (let i = 0; i < list.length - 1; i++) { 5 // 这里 < length -1的原因同上 - i的原因是 有序区 6 7 let isSorted = true // 有序标识 每一轮都为true 8 for (let j = 0; j < list.length - i -1; j++) { 9 if( list[j] > list[j+1]) { 10 let temp = list[j]; 11 list[j] = list[j+1]; 12 list[j+1] = temp 13 // 如果有交换发生，则不是有序的 14 isSorted = false 15 } 16 } 17 if(isSorted) { 18 break 19 } 20 } 21 return list 22 } 23
优化2-标记有序区
为了说明问题，我们准备一个新的数列，
这个数列的特点是：前半部分元素 3，4，2，1 是无序的，后半部分元素 5，6，7，8是升序排列的，并且后半部分元素中的最小值也大于前半部分元素的最小值
下边按照冒泡排序的思路来进行排序
第一轮：
元素 4 和元素 5 比较，发现 4 < 5，所以位置不变
元素 5 和元素 6 比较，发现 5 < 6，所以位置不变
元素 6 和元素 7 比较，发现 6 < 7，所以位置不变
元素 7 和元素 8 比较，发现 7 < 8，所以位置不变
第一轮结束，数列中的有序区包含 1 个元素
第二轮:
元素 3 和元素 2 比较，3 > 2，所以交换，元素 3 和元素 1 比较，发现 3 > 1，所以交换
元素 3 和元素 4 比较，发现 3 < 4，所以位置不变
元素 4 和元素 5 比较，发现 4 < 5，所以位置不变
元素 5 和元素 6 比较，发现 5 < 6，所以位置不变
元素 6 和元素 7 比较，发现 6 < 7，所以位置不变
元素 7 和元素 8 比较，发现 7 < 8，所以位置不变
等等，已经发现问题了，后边许多元素已经是有序的了，但是还是进行了多余的比较
这个问题的关键在于，对于有序区的界定，按照现有的逻辑，有序区的的长度和轮数是相等的，例如：第一轮结束后，有序区的长度为 1，第二轮结束后，有序区的长度为 2
实际上，数列真正的有序区可能会大于这个长度，如上述例子，在第一轮结束后，数列的后五个元素其实是已经有序的，因此后边的多次元素比较是多余的，
那么我们可以在每一轮排序后，记录下最后一次元素交互的位置，设该位置为有序区的边界，代码如下：
1 function bubbleSortThree(list:Array<number>) { 2 // 记录边界位置 3 let sortBorder = list.length - 1; 4 //记录最后一次交换的位置 5 let lastExcChangeIndex = 0; 6 7 8 // 注意 这里是 < length - 1 也就是说遍历次数为 n-1 9 for (let i = 0; i < list.length - 1; i++) { 10 let isSorted = true; // 有序标识 每一轮都为true 11 for (let j = 0; j < sortBorder; j++) { 12 if( list[j] > list[j+1]) { 13 let temp = list[j]; 14 list[j] = list[j+1]; 15 list[j+1] = temp; 16 // 如果有交换发生，则不是有序的 17 isSorted = false; 18 // 把边界更新为最后一次交换元素的位置 19 lastExcChangeIndex = j 20 } 21 } 22 sortBorder = lastExcChangeIndex 23 if(isSorted) { 24 break 25 } 26 } 27 return list 28 } 29
优化3-鸡尾酒排序
首先还是一个例子说明问题，比如有一个数列 2,3,4,5,6,7,8,1，如果按照冒泡排序的思想，排序过程如下：
元素 2,3,4,5,6,7,8已经有顺序了，却还要进行7轮排序，
冒泡排序的每一轮都是从左到右来比较元素，进行单向比较，而鸡尾酒排序的元素比较和交换是双向的
对于这个数列，我们来看一下鸡尾酒排序
第一轮(和冒泡排序一样)：
第二轮开始不一样，我们反过来，从右往左比较进行交换
第三轮，1和2比较，位置不变，2和3比较，位置不变，3和4比较，位置不变，4和5比较，位置不变，5和6比较，位置不变，6和7比较，位置不变，7和8比较，位置不变，没有元素进行交换，证明已经有序，排序结束
代码如下:
1 function bubbleSortFour(list:Array<number>) { 2 // 外层总轮数 这里取一半 floor 3 let outLength = Math.floor(list.length/2) 4 for (let i = 0; i < outLength; i++) { 5 let sorted = true; // 有序标识 6 for (let j = i; j < list.length - 1 - i; j++) { 7 if(list[j] > list[j + 1]){ 8 let temp = list[j]; 9 list[j] = list[j + 1]; 10 list[j + 1] = temp 11 sorted = false 12 } 13 } 14 if(sorted){ 15 break 16 } 17 18 19 sorted = true; 20 // 从右往左 比较 21 for (let j = list.length - 1 - i; j > i ; j--) { 22 if(list[j] < list[j - 1]){ 23 let temp = list[j]; 24 list[j] = list[j - 1]; 25 list[j - 1] = temp; 26 sorted = false; 27 } 28 } 29 if(sorted) { 30 break 31 } 32 } 33 return list 34 } 35
增加有序边界代码如下
1 function bubbleSortFive(list:Array<number>) { 2 let leftSortBorder = 0; 3 let leftLastSortIndex= 0; 4 let rightSortBorder = list.length - 1; 5 let rightLastSortIndex = 0; 6 // 外层总轮数 这里取一半 floor 7 let outLength = Math.floor(list.length/2) 8 for (let i = 0; i < outLength; i++) { 9 let sorted = true; // 有序标识 10 for (let j = leftSortBorder; j < rightSortBorder; j++) { 11 if(list[j] > list[j + 1]){ 12 let temp = list[j]; 13 list[j] = list[j + 1]; 14 list[j + 1] = temp 15 sorted = false; 16 // 记录右边界 17 rightLastSortIndex = j; 18 } 19 } 20 // 赋值右边界 21 rightSortBorder = rightLastSortIndex 22 if(sorted){ 23 break 24 } 25 26 27 sorted = true; 28 // 从右往左 比较 29 for (let j = rightSortBorder; j > leftSortBorder ; j--) { 30 if(list[j] < list[j - 1]){ 31 let temp = list[j]; 32 list[j] = list[j - 1]; 33 list[j - 1] = temp; 34 sorted = false; 35 // 记录左边界 36 leftLastSortIndex = j - 1; 37 } 38 } 39 // 赋值左边界 40 leftSortBorder = leftLastSortIndex 41 if(sorted) { 42 break 43 } 44 } 45 return list 46 } 47
摘要总结自: 漫画算法 小灰的算法之旅