【数据结构】八大排序（中）

3.直接选择排序

1.排序思想

直接选择排序是一种非常暴力排序，就是直接遍历数据，然后选出最大或者最小的数据，然后放在序列的起始位置。然后继续遍历剩下的部分数据，直到所有数据全部排完。

动图演示：

优化方案

上述演示的是没有优化过的算法，那么我们有没有什么优化方案呢？答案是肯定的，我们来思考一下，我们每次遍历都是为了找到该数据的最值（最大或者最小），一组数据中其实是有两个最值的----最大和最小，那么我们为了减少遍历的次数，是不是可以考虑一下每次遍历都找两个最值呢，当然可以。那么优化方案也就显而易见了。每次遍历的时候找到最大值和最小值的位置，然后把最大值放在该序列的尾部，最小值放在该序列的头部。

2.代码实现

未优化版本

void SelectSort(int* a, int n)
{
  int begin = 0;
  while (begin < n)
  {
    int tmpi = begin;
    for (int i = begin + 1; i < n; ++i)
    {
      if (a[i] < a[tmpi])
      {
        tmpi = i;
      }
    }
    Swap(&a[tmpi], &a[begin]);
    ++begin;
  }
}

优化后版本

void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    //优化：每次选出最大的和最小的，放在数组两侧
    int mini = begin, maxi = begin;
    for (int i = begin + 1; i <= end; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    Swap(&a[begin], &a[mini]);
    //交换之后maxi的位置可能会发生改变，需要修正
    if (maxi == begin)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}

3.复杂度

时间复杂度：

最坏情况

每次选数的时候都需要改变我们上一次对选出的数记录的下标，所以是O(N²)

最好情况

由于选择排序的特性，我们每次都会选出最值出来，所以数据原本的顺序对复杂度本身没有影响，所以也是O(N²)

空间复杂度

由于没有开辟新的空间，因此空间复杂度为O(1).

4.特性总结

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

4.堆排序

堆排序的相关知识已经在之前的博客里面详细介绍过了，这里就不过多赘述。这里放个传送门，有兴趣的可以看一看

4.特性总结

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

5.冒泡排序

1.排序思想

单趟排序中，每次比较两个相邻数据，将较大的那个放在后面，单趟排序完成后，最大的数就会在最后面，然后继续排序，直到所有的数据全部有序。

动图演示

2.代码实现

void BubbleSort(int* a, int n)
{
  for (int j = 0; j < n; j++)
  {
    int flag = 1;
    for (int i = 1; i < n - j; i++)
    {
      if (a[i - 1] > a[i])
      {
        Swap(&a[i - 1], &a[i]);
        flag = 0;
      }
    }
    if (flag)//优化点
    {
      break;
    }
  }
}

可以注意到上面的代码中我们加了一个优化点，我们在第一层循环内加了一个flag变量，用来判断每趟排序中是否执行交换操作，如果不执行交换操作的话，那么就可以证明未排序的部分本身已经有序了，直接结束排序操作即可，减少代码执行次数。

3.复杂度

时间复杂度

最坏情况

最坏情况就是每次都要执行交换操作，那么执行次数就是等差数列1+2+3+…+n-1，所以复杂度为O(N²)

最好情况

最好情况就是在第一次进入循环的时候就执行跳出操作，此时的时间复杂度访问哦O(1)

空间复杂度

由于没有开辟新的空间，因此空间复杂度为O(1).

4.特性总结

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

6.快速排序(重要)

1.排序思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

由于快速排序是二叉树结构的排序，所以快速排序就有递归和非递归两种方式，这里为了便于理清思路，我们从递归方式开始。

1.1 快排的递归实现

在经历这么多年的改进之后，快排有了三种单趟排法，虽然最终都是为了实现key去到他该去的位置。下面我们依次介绍这三种方法。

（1）hoare方法

先找出一个key（我们这里使用数据的第一个元素），然后定义两个下标，LR，R先走，找到小于key的数就停下，然后L走，找到大于key的数就将两个数交换，然后R继续移动，直到L和R相遇，由于R先走，所以最后R停下的位置就一定是小于key的，所以最后交换key和相遇位置。此时一趟排序就已经实现了。这时key这个元素就已经到了它最终应该在的位置了，然后只要保证key左边和右边的数据都是有序的，就能够保证整个数组有序，这时我们就可以使用递归的思想来排序左右的子串。

动图演示

优化选key

上述算法在最好的情况下就是每次选的key都是中位数，然后每次单趟排序都能够将数组分为基本相等的两份，这样的话递归深度就是logN，元素个数为N，所以时间复杂度就是N*logN（如下图1），但是如果非常不幸，我们选的key每次都是在首元素附近（如下图2），那么递归深度就接近与N，那么此时的时间复杂度就是N2。所以为了优化选key，有大佬提出了三种方法

1. 随机选数 – 这样使得每次 key 都为最小值的概率变得很小；
2. 选中间下标做 key – 专门针对有序进行优化；
3. 三数取中 – 取 left、right、mid 三个下标对应数值的中间值做 key。

这里我们采用第三种方法——三数取中。

int GetMidIndex(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] > a[mid])
  {
    if (a[mid] > a[right])
    {
      return mid; 
    }
    else if (a[left] > a[right])
    {
      return right;
    }
    else
      return left;
  }
  else//a[left] <= a[mid]
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
      return right;
  }
}