排序算法总结

1.冒泡排序——把大的数向前移动，好像水中的气泡，随着慢慢向水面浮起会逐渐增大。

        时间复杂度O(N²)，空间复杂度O(1)，步骤：

        ①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

        ②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。

        ③、针对所有的元素重复以上的步骤，除了最后一个。

        ④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

 

2.选择排序——每一次从待排序的数据中选出最小的，存放在最前面，直到全部排完。

        时间复杂度O(N²)，空间复杂度O(1)，步骤：

        ①、从待排序序列中，找到关键字最小的元素

        ②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换

        ③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复①、②步，直到排序结束

 

3.插入排序——每一步将一个待排序的数据，插入到前面已经排好的有序序列中，直到完成所有元素。

        时间复杂度O(N²)，空间复杂度O(1)

 

4.希尔排序

        时间复杂度O(NlogN)，空间复杂度O(1)

        在插入排序中，如果一个很小的数在很靠近右边的位置，那么想让这个很小的数插入到左边已排好序列，那么序列中的数据项都必须向右移动一位，这个步骤就是将近执行了N次复制，虽然不是每个数据项都必须移动N个位置，但是每个数据项平均移动了N/2次，总共就是N²/2。希尔排序是基于插入排序的，它在插入排序中增加了一个新特性，大大的提高了插入排序的执行效率。希尔排序通过加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们上面说的简单的直接插入排序。

        一种希尔的变形方法是用2.2来整除获取每一个间隔，对于n=100的数组，会产生序列45，20，9,4,1。

 

5.快速排序——快速排序是对冒泡排序的一种改进，由C. A. R. Hoare在1962年提出的一种划分交换排序，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。

         时间复杂度O(NlogN)，空间复杂度O(1)，步骤：

         ①、先通过第一趟排序，将数组原地划分为两部分，其中一部分的所有数据都小于另一部分的所有数据。原数组被划分为2份

　　 ②、通过递归的处理， 再对原数组分割的两部分分别划分为两部分，同样是使得其中一部分的所有数据都小于另一部分的所有数据。 这个时候原数组被划分为了4份

　　 ③、就1,2被划分后的最小单元子数组来看，它们仍然是无序的，但是！ 它们所组成的原数组却逐渐向有序的方向前进。

　　 ④、这样不断划分到最后，数组就被划分为多个由一个元素或多个相同元素组成的单元，这样数组就有序了。

        具体来说就是设置基准元素，左右游标：

      基准元素：它是将数组划分为两个子数组的过程中，用于界定大小的值，以它为判断标准，将小于它的数组元素“划分”到一个“小数值的数组”中，而将大于它的数组元素“划分”到一个“大数值的数组”中，这样，我们就将数组分割为两个子数组，而其中一个子数组的元素恒小于另一个子数组里的元素。

　　左游标：它一开始指向待分割数组最左侧的数组元素，在排序的过程中，它将向右移动。左游标向右扫描， 跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素， 在那个位置停下。

　　右游标：它一开始指向待分割数组最右侧的数组元素，在排序的过程中，它将向左移动。右游标向左扫描， 跨过所有大于基准元素的数组元素, 直到遇到一个小于或等于基准元素的数组元素，在那个位置停下。

      当左右游标相遇了，那么此时说明探测结束，将相遇位置和基准元素位置进行交换。

      基准元素设定：为了找到一个数组中的中值数据，一般是取数组中第一个、中间的、最后一个，选择这三个数中位于中间的数。

        

6.归并排序——归并两个有序数组A和B，就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。

        时间复杂度O(NlogN)，空间复杂度O(N)，说明：把一个数组分成两半，排序每一半，把每一半都分为四分之一，对每个四分之一进行排序，然后把它们归并成一个有序的一半。类似的，如何给每个四分之一数组排序呢？把每个四分之一分成八分之一，对每个八分之一进行排序，以此类推，反复的分割数组，直到得到的子数组是一个数据项，那这就是这个递归算法的边界值，也就是假定一个数据项的元素是有序的。

 

7.桶排序

        时间复杂度O(N)，空间复杂度O(N)，桶排序需要两个辅助空间：桶空间和桶内的元素链表空间。精髓就是将待排序数据按区间切分装入桶，然后在桶内进行插入排序，最后按序合并桶内数据即可。缺点：需要已知最大最小值，且数据均匀分布的。优点：算法简单。

 

8.基数排序

         时间复杂度O(N)，空间复杂度O(N)，其实也是桶排序，不同的是桶划分的方法是按基数，如10进制数则可划分为0，1，2，3，4，5，6，7，8，9共10个桶，先按待排序数据的个位数把数据放入各个桶中，然后按桶序取出到序列中，此时序列中的数据的个位数已经是有序的了，然后再把序列中的数按十位数把数据依次放入对应的桶中，然后按桶的次序再取出到序列中，此时序列中的数据的十位数和个位数都已经是有序的了，以此类推，直到所有的基数都排完。优点：桶内不需要插入排序，算法更简单。缺点：待排序数据的位数需大致相同。

 

9.计数排序

          时间复杂度O(N)，空间复杂度O(N)，对于整数排序，先获取待排序数据的最大最小值min，max，生成计数数组int[max-min+1]，int[0]=min，int[max-min]=max；然后遍历待排序数据，每遍历一个数据再技术数组对应的小标数据中加1，最后遍历计数数组得出排序结果。