十大排序算法之总结与回顾

注：所有图片均来自于网络
一、冒泡排序（BubbleSort)

1. 原理：比较相邻两元素之间的大小，若右边的小于左边的，则交换两元素的顺序，循环执行此过程，直到排序完成。
2. 性质：稳定，时间复杂度：O(n²)，空间复杂度：O(1)。
   

二、桶排序（BucketSort)

1. 原理：以元素的值为坐标存入相应的桶中，元素出现一次，则对应的桶的值就+1，最后按顺序取出所有元素。
2. 性质：稳定；空间复杂度：O(n+k)；空间复杂度：O(n+k)
   

三、选择排序（SelectSort)

1. 原理：在序列中找到最小的那个元素，把它放大到数组的最前面，在剩下的序列中找到最小的元素，把它放到第二位，如此循环执行下去，直到所有元素排序完毕。
2. 性质：不稳定；空间复杂度：O(1)，时间复杂度：O(n²)
   

四、插入排序（InsertSort）

1. 原理：从第一个元素开始排列，第一个元素是有序的，然后将第二个元素插入进来，给两个元素排序，然后将第三个元素插入进来，给他们再次排序，如此反复执行，直到所有元素排序完毕。
2. 性质：稳定；空间复杂度：O(1)；时间复杂度：O(n²)
   

五、希尔排序（ShellSort）

1. 原理：对序列进行分组，以gap=size()/2为增量，对每组中的元素进行插入排序，然后将增量gap/2，对每组中的元素再次进行插入排序，知道增量等于1，排序完成。
2. 性质：不稳定；空间复杂度O(1)；时间复杂度：O(nlogⁿ)
   

六、归并排序（MergeSort)

1. 原理：采用分-治的思想，将序列中的元素采用二分法分到每组元素只有一个，然后逐层向上合并分组，并将分组排序，知道最后排序完毕，采用递归的写法，两个函数。
2. 性质：稳定；空间复杂度：O(n)；时间复杂度：O(nlogⁿ)
   

七、快速排序（QuickSort）

1. 原理：设定一个基准值，将大于基准值得数转移到基准值的右边，小于基准值的元素转移到基准值得左边，然后分别在左右两边各另选一个基准值，重复上述操作，直到i,j相遇（i,j分别为指向序列左边和右边的哨兵）
2. 性质：不稳定；空间复杂度：O(logⁿ)；时间复杂度：O(nlogⁿ)
   

八、计数排序（CountingSort）

1. 原理：类似于桶排序，换成了max-min+1个桶，缩小了所需要的内存空间。
2. 稳定；空间复杂度：O(k)；时间复杂度：O(n+k)
   

九、基数排序（RadixSort）

1. 原理：找出序列中最大值元素的位数，从低位到高位逐位排序。
2. 性质：稳定；空间复杂度：O(n+k)；时间复杂度：O(n*k)
   

十、堆排序（HeapSort）

1. 采用完全二叉树，从低到高排序，每次都找出最大的元素，有三个函数，一个交换两个数的位置、第二个用来排序、第三个用来循环控制排序并交换头尾值。
2. 性质：不稳定；空间复杂度：O(1)；时间复杂度：O(nlogⁿ)
   

十一、列表