文章目录

概念

将一个数据插入到一个有序数列中的合适位置，使新的序列仍然有序。

插入排序方法

我们可将数组中的第一个元素看成一个有序数列，然后将后面的数据依次插入，直至整个数列有序。

图解：

代码：

void InsertSort(int arr[],int l)
{
  for (int i = 0; i < l - 1; i++)
  {
    int end = i;
    int tmp = arr[end + 1];
    while (end >= 0)
    {
      if (tmp < arr[end])
      {
        arr[end + 1] = arr[end];
        end--;
      }
      else
      {
        break;
      }
    }
    arr[end + 1] = tmp;
  }
}

时间复杂度：O(n^2)

希尔排序

概念

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

思想

希尔排序，又称缩小增量法。其基本思想是：

1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

图解

代码

//希尔排序
void ShellSort(int arr[],int l)
{
  int gap = l;
  while (gap > 1)
  {
    gap = gap / 2;
    for (int i = 0; i < l - gap; i++)
    {
      int end = i;
      int tmp = arr[end + gap];
      while (end >= 0)
      {
        if (tmp < arr[end])
        {
          arr[end + gap] = arr[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      arr[end + gap] = tmp;
    }
  }
}

选择排序

直接选择排序

概念

通过循环遍历，选出数组中最小的数放在数列开头(选出最大的数放在数列末尾)，重复这个步骤直至数列有序。

图解

代码：

void SelectSort(int arr[],int L)
{
  int begin = 0;
  while (begin<L-1)
  {
    int mini = begin;
    for (int i = begin; i < L ; i++)
    {
      if (arr[mini] > arr[i])
      {
        mini = i;
      }
    }
    Swap(&arr[mini],&arr[begin]);
    begin++;
  }
}

代码优化

我们在一次循环中同时选出一个最大的和一个最小的，将最小的放最前面，将最大的放最后面，这样代码的效率会将近提高一倍。

void SelectSort(int arr[],int L)
{
  int begin = 0;
  int end = L - 1;
  while (begin < end)
  {
    int maxi = begin;
    int mini = begin;
    for (int i = begin; i <= end; i++)
    {
      if (arr[i] > arr[maxi])
      {
        maxi = i;
      }
      if (arr[i] < arr[mini])
      {
        mini = i;
      }
    }
    int max = arr[maxi];
    int min = arr[mini];
    Swap(&arr[maxi], &arr[end]);
    if (mini == end)
    {
      mini = maxi;
    }
    Swap(&arr[mini], &arr[begin]);
    end--;
    begin++;
  }
}

时间复杂度：O(n^2)

堆排序

概念

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。

堆的两个特性

结构性:堆是用数组表示的完全二叉树,我们可以用数组下标来表示父子结点的关系。

这里随便给出一个数组：

将数组以完全二叉树的形式表示出来：

我们可以推出父子结点与二叉树的关系:

LeftChild = Parent* 2 - 1

RightChild = Parent* 2 - 2

Parent = (Chird - 1) / 2

有序性:

任意一个结点的值都大于或者等于左右子树的结点的值(或者左右结点不存在)，称为 “最大堆(MaxHeap)”
,也称大顶堆。
任意一个结点的值都小于或等于左右子树的结点的值((或者左右结点不存在))，称为 “最小堆(MinHeap)”
,也称小顶堆。

堆排序中的三个操作
向下调整算法
建立最小(最大)堆
堆排序

向下调整算法

当一个结点的左右子树都是小堆(大堆)时，可以使用向下调整算法。

上图中，初始时，27的左右子树都是最小堆，我们就可以使用向下调整算法，将27放在合适的位置，首先选出左右子树中较小的那一个，和27比较，如果比27小就进行交换，然后继续往下调，如果比27大，说明已经找到了27合适的位置，不需要继续往下调。

如果是最小堆，经过向下调整算法，根结点会是堆中最小的值；

如果是最大堆，经过向下调整算法，根节点会是堆中最大的值。

代码：

//最小堆的向下调整算法
void Adjustdown(int arr[],int L,int root)
{
  int parent = root;
  int child = parent * 2 + 1;//先默认child是左孩子
  while (child < L)
  {
    //选左右孩子中较小的一个
    //若child >= L-1说明右孩子不存在
    if (child < L-1 && arr[child + 1] > arr[child])
    {
      child += 1;
    }
    if (arr[parent] < arr[child])
    {
      Swap(&arr[parent], &arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

建立最小(最大)堆

有了向下调整算法，我们就可以将一个无序数组变成最小(最大)堆。向下调整算法使用条件是左右子树必须是最小(最大)堆，一个无序数组构成的满二叉树如果从根节点出发的肯定不满足，但是满二叉树的叶子结点的父节点一定满足(即从叶子结点出发)。

最后一个叶子结点下标就是数组的最后一个元素L - 1，它的父节点就是 [(L - 1) -1] / 2 , 然后依次向上建堆。

图解：

a.假定给定无序序列如下：

b.由最后一个叶子结点的父节点开始，自下而上，自左而右的进行向下调整算法。

此时，我们成功的建立了一个最大堆

代码：

void HeapGreat(int arr[], int L)
{
  for (int i = (L - 2) / 2; i >= 0; i--)
  {
    Adjustdown(arr, L, i);
  }
}

若数组为 arr[ ] = { 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1}

建堆之后的结果为：

堆排序

我们可以通过建最大堆找到数组中最大的元素，通过建最小堆找到数组中最小的元素。

如果要将无序数组排成升序的化，我们需要建最大堆，因为建最大堆可以找到最大的元素，我们可以将找到的最大元素与数组末尾的元素交换位置，然后不在将这个数看入堆中。重复以上操作，直至堆中只剩一个元素，这时数组已经有序。

代码：

void HeapSort(int arr[],int L)
{
  //建堆
  for (int i = (L - 2) / 2; i >= 0; i--)
  {
    Adjustdown(arr, L, i);
  }
  int newL = L;
  //
  while (newL > 0)
  {
    Swap(&arr[0], &arr[newL-1]);
    newL--;
    Adjustdown(arr, newL, 0);
  }
}

时间复杂度

建堆复杂度：O(N)

排序复杂度：O(logN)

总复杂度：O(logN)

交换排序

冒泡排序

动图演示

代码

void BubbleSort(int arr[],int L)
{
  int Flag = 1;
  for (int i = 0; i < L&&Flag; i++)
  {
    Flag = 0;
    for (int j = 1; j < L - i; j++)
    {
      if (arr[j] < arr[j - 1])
      {
        Swap(&arr[j], &arr[j - 1]);
        Flag = 1;
      }
    }
  }
}

注意：程序中标记变量Flag的作用，如果某趟所有相邻的数都不需要交换，则Flag置为0，表示所有的数都已全部有序，后面不需要进行，冒泡排序可以提起结束。

快速排序

基本思想

任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

挖坑法

挖坑法的单趟排序的基本步骤如下：

1、选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。

2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）。

3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

动态演示

代码

void QuickSort(int arr[],int L,int R )
{
  if (L >= R)
  {
    return;
  }
  int begin = L;
  int end = R;
  int Pivot = begin;
  int key = arr[Pivot];
  while(begin < end)
  {
    //右边找小
    //这里的 = 不能去掉，不然如果arr[end] = arr[begin]就不会进入内循环但也出不了外面循环
    while(end > begin && arr[end] >= key)
    {
      end--;
    }
    //将小的放到左边的坑里，自己形成新的坑
    arr[Pivot] = arr[end];
    Pivot = end;
    //左边找大
    while (end > begin && arr[begin] <= key)
    {
      begin++;
    }
    //将大的放到右边的坑里，自己形成新的坑
    arr[Pivot] = arr[begin];
    Pivot = begin;
  }
  //begin与end相遇，将key放到坑里
  arr[Pivot] = key;
  QuickSort(arr,0,Pivot-1);
  QuickSort(arr,Pivot+1,R);
}

左右指针法

思路如下：

1.选择一个值作为基准值key(一般选最左边或最右边，在这里选最左边)。

2.定义L，R（分别为待排序序列最左边与最右边元素的下标)，L从左往右走，R从右往左走(若选最左边为key，R先走；选最右边为key，L先走)。

3.R从右往左走遇到比key小的停下来，接着L从左往右走，遇到比key大的停下来。然后交换R，L对应数组中的值。

4.重复上一步操作，直至L，R二者相遇。将相遇点对应的值与key对应的值交换，此时相遇点左边的值均小于相遇点所对应的值，右边的值均大于相遇点所对应的值。

5.相遇点将待排序序列分为两个子序列，用递归的方式重复上述操作。

6.当左右序列只有一个元素的时候排序完成。

动态演示

代码

void QuickSort(int arr[],int L,int R)
{
  if (L >= R) return;
  int begin = L;
  int end = R;
  int key = L;
  while (end > begin)
  {
    while (end > begin && arr[end] >= arr[key])
    {
      end--;
    }
    while (end > begin && arr[begin] <= arr[key])
    {
      begin++;
    }
    Swap(&arr[begin], &arr[end]);
  }
  Swap(&arr[key], &arr[begin]);
  QuickSort(arr,L,begin-1);
  QuickSort(arr,begin+1,R);
}

前后指针法

动态演示

代码

void QuickSort(int arr[],int L,int R)
{
  if (L >= R) return;
  int key = L;
  int cur = L+1;
  int prev = L;
  while (cur <= R)
  {
    if (arr[cur] < arr[key])
    {
      prev++;
      Swap(&arr[cur],&arr[prev]);
    }
    cur++;
  }
  Swap(&arr[key], &arr[prev]);
  QuickSort(arr,L,prev-1);
  QuickSort(arr,prev+1,R);
}

非递归法

上面的三种方法都是使用递归的方式实现的快速排序，但是递归也有着明显的缺陷，栈帧深度太深，栈空间不够用，可能会溢出。

我们可以使用一种叫栈的数据结构，来模拟递归。

思路：

将待排序序列的第一个数和最后一个数的下标入栈。
获取栈中的第一个元素®然后让它出栈，再获取栈中一个元素(L)然后让它出栈，进行一次单趟排序，然后判断左右两个子序列是否需要排序，若需要再将该序列的第一个数下标和最后一个数的下标入栈。
重复以上操作，直至栈为空。

代码

void QuickSort(int arr[],int L)
{
  //如果序列长度小于2，不需要进行排序
  if(L<2) return;
  Stack ps;//定义了一个栈
  StackInit(&ps);//初始化栈
  StackPush(&ps,0);//数组中第一个数的下标入栈
  StackPush(&ps,L-1);//数组中最后一个数的下标入栈
  //当栈不为空时进行循环
  while (!StackEmpty(&ps))
  {
    //获得栈顶元素
    int end = StackTop(&ps);
    //弹栈
    StackPop(&ps);
    int Right = end;
    //获得栈顶元素
    int begin = StackTop(&ps);
    //弹栈
    StackPop(&ps);
    int Left = begin;
    int key = begin;
    //快排的单趟排序
    while (begin < end)
    {
      while (begin < end && arr[end] >= arr[key])
      {
        end--;
      }
      while (begin < end && arr[begin] <= arr[key])
      {
        begin++;
      }
      Swap(&arr[end], &arr[begin]);
    }
    Swap(&arr[key], &arr[begin]);
    //如果左序列元素个数大于1，左序列首尾下标入栈
    if ( Left< begin-1)
    {
      StackPush(&ps, Left);
      StackPush(&ps, begin-1);
    }
    //如果左序列元素个数大于1，左序列首尾下标入栈
    if (begin+1 < Right)
    {
      StackPush(&ps, begin+1);
      StackPush(&ps, Right);
    }
  }
  StackDestory(&ps);
}

优点

递归的方法它会占用一个名为栈的空间，一般计算机中栈的空间很小，当递归次数过多时，就有可能栈溢出。如果我们自己模拟实现栈，在循环中占用的是堆空间，堆要比栈大很多。

快排优化

快排最理想的情况下，每次选key都能选到大小排在数列中间的数，这样快排的时间复杂度就是 O(NlogN) 。最坏的情况就是每次选key都是序列中最大的，或者是最小的，这样时间复杂度就上升到O(N^2)，为了避免这种最坏的情况，尽量接近最好的情况，我们在key时可以采用三数取中的方式。

三数取中

//三数取中
int GetMidIndex(int arr[],int L,int R)
{
  int Mid = (L + R) >> 1;
  if (arr[L] > arr[R])
  {
    if (arr[Mid] > arr[L])  return L;
    else if (arr[Mid] < arr[R]) return R;
    else return Mid;
  }
  else
  {
    if (arr[Mid] > arr[R])  return R;
    else if (arr[Mid] < arr[L]) return L;
    else return Mid;
  }
}

优化代码

void QuickSort(int arr[],int L,int R )
{
  if (L >= R)
  {
    return;
  }
  Swap(&arr[L],&arr[GetMidIndex(arr,L,R)]);
  int begin = L;
  int end = R;
  int Pivot = begin;
  int key = arr[Pivot];
  while(begin < end)
  {
    //右边找小
    while(end > begin && arr[end] > key)
    {
      end--;
    }
    //将小的放到左边的坑里，自己形成新的坑
    arr[Pivot] = arr[end];
    Pivot = end;
    //左边找大
    while (end > begin && arr[begin] < key)
    {
      begin++;
    }
    //将大的放到右边的坑里，自己形成新的坑
    arr[Pivot] = arr[begin];
    Pivot = begin;
  }
  //begin与end相遇，将key放到坑里
  arr[Pivot] = key;
  QuickSort(arr,0,Pivot-1);
  QuickSort(arr,Pivot+1,R);
}

小区间优化

快速排序在排数量较大的序列时效率很高，但是随着递归的深入，递归次数也呈2

的倍数增长。

比如说通过快速排序排列100w(约等于2^20)个数时，要经过 200w（2^20 + 2^19 + …… + 2^0)次递归，快排的最后一层要进行100w次递归，倒数第二层要进行50w次递归，倒数第三层要进行25w次递归，倒数第四层要进行12.5w次递归，刚最后四组递归加起来已经187.5w次，占了总递归次数的绝大多数。为了减少递归次数，我们可以进行小区间优化，当进入快排这个函数的序列长度小于10时，我们就可以采用其他的排序方式，短序列排序我们可以使用直接插入排序。

优化代码

void QuickSort(int arr[],int L,int R )
{
  if (L >= R)
  {
    return;
  }
  Swap(&arr[L],&arr[GetMidIndex(arr,L,R)]);
  int begin = L;
  int end = R;
  int Pivot = begin;
  int key = arr[Pivot];
  while(begin < end)
  {
    //右边找小
    while(end > begin && arr[end] > key)
    {
      end--;
    }
    //将小的放到左边的坑里，自己形成新的坑
    arr[Pivot] = arr[end];
    Pivot = end;
    //左边找大
    while (end > begin && arr[begin] < key)
    {
      begin++;
    }
    //将大的放到右边的坑里，自己形成新的坑
    arr[Pivot] = arr[begin];
    Pivot = begin;
  }
  //begin与end相遇，将key放到坑里
  arr[Pivot] = key;
  if (Pivot - L <= 10)
  {
    InsertSort(arr + L, Pivot - L);
  }
  else
  {
    QuickSort(arr, L, Pivot - 1);
  }
  if (R - Pivot <= 10)
  {
    InsertSort(arr+Pivot+1,R-Pivot);
  }
  else
  {
    QuickSort(arr, Pivot + 1, R);
  }
}

归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；

归并排序可以大致分为两个步骤：分解序列至子序列有序，合并子序列得到新的有序数列。如下图：

动态演示

代码

void _MergeSort(int arr[],int Left,int Right ,int tmp[])
{
  if (Left >= Right)
  {
    return;
  }
  int Mid = (Left + Right) / 2;
  _MergeSort(arr, Left, Mid, tmp);
  _MergeSort(arr, Mid + 1, Right, tmp);
  int begin1 = Left;
  int end1 = Mid;
  int begin2 = Mid+1;
  int end2 = Right;
  int cur = Left;
  while (begin1 <= end1&&begin2 <= end2)
  {
    if (arr[begin1] > arr[begin2])
    {
      tmp[cur++] = arr[begin2++];
    }
    else
    {
      tmp[cur++] = arr[begin1++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[cur++] = arr[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[cur++] = arr[begin2++];
  }
  for (int i = Left; i <= Right; i++)
  {
    arr[i] = tmp[i];
  }
}
void MergeSort(int arr[],int L)
{
  int* tmp = (int*)malloc(sizeof(int) * L);
  _MergeSort(arr,0,L-1,tmp);
  free(tmp);
}

时间复杂度：O( NlogN ) 空间复杂度：O(N)

数据结构——排序算法

文章目录

插入排序

直接插入排序

希尔排序

选择排序

直接选择排序

堆排序

交换排序

冒泡排序

快速排序

挖坑法

左右指针法

前后指针法

非递归法

快排优化

归并排序

热门文章

最新文章

相关课程

相关电子书

相关实验场景