1. 如何分析一个排序算法好坏

时间复杂度、比较和交换次数、原地排序（空间复杂度为(1)）、排序稳定性（相等元素之间的位置先后顺序不变）。

有序度：是数组中具有有序关系的元素对的个数

逆序度：和有序度相反。

选择排序是不稳定排序，所以应用最少。

2. 插入排序比冒泡排序哪个好？

插入排序好。原因有如下两点：

• 冒泡和插入虽然时间复杂度都是O(n2) ，元素移动次数都是等于逆序度，但是冒泡排序比插入排序多了三个赋值操作，性能有损耗，如下代码：

//冒泡排序数据交换 
if(a[j] > a[j+1]) { 
   int tmp = a[j];     
   a[j]  = a[j+1];     
   a[j+1]  = tmp;     
   flag  = true;     
 }   
​
//插入排序数据交换:  
if (a[j] > value) {     
  a[j+1]  = a[j];         
}

• 插入排序比冒泡排序有更多的优化空间，比如希尔排序。

3. 常见的排序算法总结

4. 排序算法原理描述

• 冒泡排序

  移动相邻位置的两个数据，重复执行。

• 插入排序

  把数组分为两个区间，已排序和未排序区间。把数据从未排序区间插入已排序区间的合适位置。

• 选择排序

  分已排序和未排序区间，从未排序中找到最小的元素，放到已排序区间的额末尾。原地排序、不稳定排序、最好最坏平均时间复杂度都是O(n2)。

• 归并排序Merge Sort

  分治思想。假如把数组下标从x到y开始排序，不断的把数组一分为二，直到x>=y，结束。

  然后merge。建立一个临时数组，大小和要比较的数组大小相同，也就是A[x,y]。我们用两个游标 i 和 j，分别指向 A[x...q] 和 A[q+1...y] 的第一个元素。比较这两个元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放 入到临时数组 tmp，并且 i 后移一位，否则将 A[j] 放入到数组 tmp，j 后移一位。

  继续上述比较过程，直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数 据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。 最后再把临时数组 tmp 中的数据拷贝到原数组 A[x...y] 中。

  稳定排序算法。时间复杂度都是O(nlogn) ，与原始数据是否有序无关。不是原地排序算法。

• 快速排序 Quicksort

  从数组下标p到r，任意选一个数据作为pivot（分区点，一般选p到r最后一个），将小于pivot的数据放左边，大于放右边。然后将pivot左侧和右侧继续按照此方式排序，直到区间为1。

• 桶排序（Bucket sort）

  将数据分成若干个有顺序的桶，每个桶内单独排序，然后依次取出就是有顺序了。

• 计数排序(Counting sort)

  找出数组中最大的元素k，然后分成k个桶，每个桶内数据是相同的，桶之间就是排序好的数据。和桶排序的的大小力度不同。

• 基数排序(Radix sort)

  对排序数据有要求，数据分隔不同的位，比较完前面的大小，数据后面的位数就不需要比较了。