一、冒泡排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

1.动图演示

2.代码实现

// 冒泡排序
void Swap(int* px, int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
void BubbleSort(int* a, int n)
{
  int end = n;
  while (end > 0)
  {
    int exchange = 0;
    for (int j = 0; j < end - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        exchange = 1;
        Swap(&a[j], &a[j + 1]);
      }
    }
    --end;
    if (exchange == 0)
    {
      break;
    }
  }
  /*for (int i = 0; i < n - 1; i++)
  {
    for (int j = 0; j < n - i - 1; j++)
    {
      if (a[j] > a[j + 1])
      {
        Swap(&a[j], &a[j + 1]);
      }
    }
  }*/
}

二、快速排序

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

基本思想如下：

1. 递归实现

1.Hoare版本（含动图演示）

动图演示

代码实现

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (a[right] > a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (a[left] < a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}

上述代码存在两大缺陷:

场景1：

如果是一个有序的数组（升序），每个数都比第一个数大，小黄就没人管了，撒开腿就一直跑；

场景2：

如果这个数组元素都相同，小黄先跑，发现跑不动；（死循环）

针对刚才的代码很明显在这两种场景下一定会出问题；

如何解决：

1.确保 右边找小 或 左边找大 的时候，判断它（小黄或小白）的下标有没有越界；

2.要考虑元素相等的情况；

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}

单趟排序完成之后，比key大的数都放在右边，比key小的数都放在左边，只要以key为基准值，它的左子区间再有序，右子区间再有序，那么整体就有序了；这种问题和二叉树很类似；第一趟排序找了一个key，分成了左右区间，只要为左右区间各找一个key，不断的去划分，那么久把整个数组排序完成了；

int Partion1(int* a,int left,int right)
{
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
    int keyi = Partion1(a, left, right);/*hoare版本*/
        //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);//左子区间
    QuickSort(a, keyi + 1, right);//右子区间
  }
}

如何定位基准值（key）：

先看下面的图例，发现快排在针对无序的数组进行排序时，它的效率是很快的，但是在有序或接近有序的情况下，就会变得很糟糕；这里最关键的就是key的选择问题；也就是如何针对快排对于数组有序情况下选key的问题；

为了解决选key的问题，可以采用三数取中法；

三数取中法：最左边的数、中间数、最右边的数；

对这三个数进行比较，选出一个中间值(既不是最大也不是最小)，作为key；那么针对于有序的情况，就会瞬间变得很好，直接将数据二分；

快排完整动图

代码实现

/*hoare版本*/
//快排（递归）
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 1);
  if (a[left] < a[mid]) 
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else//a[left] > a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int Partion1(int* a,int left,int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int keyi = left;
  while (left < right)
  {
    //右边先走，找小
    while (left < right && a[right] >= a[keyi])
    {
      --right;
    }
    //左边再走，找大
    while (left < right && a[left] <= a[keyi])
    {
      ++left;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[left], &a[keyi]);
  return left;
}
//O(N*logN)
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion1(a, left, right);/*hoare版本*/
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}

在上面的代码中有这样一段代码：

    if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion1(a, left, right);/*hoare版本*/
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }

由于采用递归的方式进行快排，如果数据量很大，就会造成栈的溢出；为了解决这个问题，采用了一个小区间优化的方法，在不断划分区间去进行递归的时候，越往下划分区间越来越小，但是区间数量越来越多，递归次数也越来越多；我们采取当区间相差小于10（最低给10）时，直接让这些区间的数据进行直接插入排序；

2.挖坑法（含动图演示）

1.基本思路：

先将第一个变量存储在临时变量key中，右边先走，去找小扔到左边的坑，自己成为新的坑；然后左边再走，去找大扔到右边的坑( pivot )，自己成为新的坑( pivot )；直到两者相遇把保存的key的值放进坑( pivot )；

2.动图演示

下图为挖坑法的单趟演示，其完整排序和上面的快排完整版类似，需要划分左右子区间；进行递归调用

3.代码实现

//挖坑法
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 1);
  if (a[left] < a[mid]) 
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else//a[left] >= a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int Partion2(int* a, int left, int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int key = a[left];
  int pivot = left;
  while (left < right)
  {
    //右边找小，扔到左边的坑
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[pivot] = a[right];
    pivot = right;//自己形成新的坑
    //左边找大，扔到右边的坑
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[pivot] = a[left];
    pivot = left;//自己形成新的坑
  }
  a[pivot] = key;
  return pivot;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    //int keyi = Partion2(a, left, right);//挖坑法
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}

3.前后指针法（含动图演示）

1.基本思路：

前后指针法的基本思想其实和前面两种方法类似，cur去找小，prev去找大；也会得到key的左边是小值右边是大值；

2.代码实现

//前后指针法
//三数取中
int GetMidIndex(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid = left + ((right - left) >> 1);
  if (a[left] < a[mid]) 
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else//a[left] >= a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int Partion3(int* a, int left, int right)
{
  //三数取中
  int mini = GetMidIndex(a, left, right);
  Swap(&a[mini], &a[left]);
  int keyi = left;
  int prev = left;
  int cur = left +1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[cur], &a[prev]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  return prev;
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
    return;
  //小区间优化，当分割到小区间时，不在用递归思路让这段子区间有序
  //对于递归快排，减少递归次数
  if (right - left + 1 < 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  else
  {
    int keyi = Partion3(a, left, right);//前后指针法
    //区间划分[begin , keyi-1] keyi [keyi+1 , end]
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
  }
}

数据结构（初阶）—— 排序算法（下）（1）

一、冒泡排序

1.动图演示

2.代码实现

二、快速排序

1. 递归实现

1.Hoare版本（含动图演示）

2.挖坑法（含动图演示）

3.前后指针法（含动图演示）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构（初阶）—— 排序算法（下）（1）

一、冒泡排序

1.动图演示

2.代码实现

二、快速排序

1. 递归实现

1.Hoare版本（含动图演示）

2.挖坑法 （含动图演示）

3.前后指针法 （含动图演示）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

2.挖坑法（含动图演示）

3.前后指针法（含动图演示）