四大排序

时间：2022-12-21 15:55:57

*** 以下排序皆以升序为例***

插入排序

1.1 直接插入排序

1.1.1 单趟排序思想（三种情况）

  1. 对于第一张图片中的数据，我们设置一个tmp保存最后一个数据，设置end表示5的下标。在这串数据中可以看到，数据已经是升序了，我们要对6这个数据进行排序，就是拿tmp和end下标位置的数据比较，在这里tmp不小于end，那么就不需要做出任何改动

在这种图片中我们可以观察到，3最终是要放到2下标处的，我们现在开始对3进行排序。​​if(tmp < arr[end])​​我们就让​​arr[end+1]=arr[end]​​也就是把前面的数据往后挪，给日后tmp找到了属于自己的位置时留一个位置，此时第一次走，3是比6小的，那么下标为5的位置上就赋值成6，因为tmp=3，所以不必担心会被覆盖数据。然后再对end--。让tmp与前面的数据接着比对，重复上面的操作，直到tmp与下标为2比较时，tmp比2大，停止遍历，直接让​​arr[end+1]=tmp​​，至此让3找到了自己应该在的升序位置。

四大排序

在这张图片中我们可以看到，最终1是要放到0下标处的 。我们仍然重复上一张图片里的步骤，两者唯一的不同就是，当end==0时，比对完成，end变成-1，此时仍然是执行​​arr[end+1]=tmp​​,这可以解决end下标为-1的问题。

四大排序

1.1.2 单趟排序的代码

int end;
int tmp=arr[end+1];

//当end<0或者tmp大于arr[end]的时候说明tmp找到了自己的位置
while(end >= 0)
{
  //如果当前排序的数据小于其它数据，就挪动数组内的元素顺序，使其下标向后移
  if(tmp < arr[end])
  {
    //挪动数据
    arr[end+1]=arr[end];
    end--;
  }
  else
  {
    break;
  }
}
//把tmp放在自己该在的位置
arr[end+1]=tmp;

1.1.3 完整直接插入排序思想

完整的插入排序的思想就是，每一次单趟插入排序把前面的数据排好顺序，后面在排序的时候，只要tmp>arr[end]，就代表前面每一个数都比tmp要小，tmp也可以依此找到自己的位置了。比如：

在这张图片中，第一次进行排序，我们把1和9排好升序

四大排序


进行第二次排序时，数据就变成了下图所示，再重复单趟排序

四大排序


进行第三次排序时，数据变成了这样，也就是说，在执行单趟循环的时候，5和9比完，把9赋值给下标为3的位置，然后和2比，5比2大，因为前面的数都比2小，之前已经排过序了，所以结束循环，此时end下标为1，arr[end+1]=tmp。这样就让tmp找到了位置。

四大排序

1.1.4 代码实现

void InsertSort(int* arr,int n)//n代表数组元素个数
{
  for(int i=0;i<k-1;i++)//i必须要小于k-1，否则end+1会导致越界
  {
    int end = i;
    int tmp=arr[end+1];

    //当end<0或者tmp大于arr[end]的时候说明tmp找到了自己的位置
    while(end >= 0)
    {
      //如果当前排序的数据小于其它数据，就挪动数组内的元素顺序，使其下标向后移
      if(tmp < arr[end])
      {
        //挪动数据
        arr[end+1]=arr[end];
        end--;
      }
      else
      {
        break;
        //由于之前已经把前面的数据都排过序，
        //所以如果大于，那么说明前面的数都小于tmp
      }
    }
    //把tmp放在自己该在的位置
    arr[end+1]=tmp;
  }
}

1.2 希尔排序

1.2.1 思想

希尔排序实际就是直接插入排序的优化。在希尔排序中，我们选取一个间距对整个数组进行分组，对每一组内的元素分别进行排序，然后不断缩小间距，直到间距为1，就变成了直接插入排序，我们称这个过程为预排序，而由于多次的预排序，数组元素已经接近有序，此时直接插入的效率大大提升。

比如：设置gap变量为间距，设置gap=5

四大排序

1.2.2 代码实现

void ShellSort(int*arr, int k)
{
  int gap = k;
  //循环中所有的+-gap的操作，都对应着直接插入排序中的end+1和end--操作。
  //触类旁通就好
  while (gap > 1)
  {
    //下面这层循环就是单趟排序，在某一个gap值下进行的单趟排序，
    //实现了让数据更加有序的目的
    //每一次进入这个循环都会使数据更加有序
    gap /= 2;
    //除以2能够保证最后gap==1，
    //也就保证了最后一次可以实现接近有序的直接插入排序
    for (int i = 0; i < k - gap; i++)
    {
      int end = i;//让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;
    }
  }
}

选择排序

2.1 直接选择排序

2.1.1思想

在数据中遍历，选出最小的数据和最大的数据，然后把它们分别放在元素集合中的最前面和最后面，每一遍遍历过后，集合的宽度减2，重复以上步骤。思想很简单，实现起来也很简单。

2.1.2 代码实现

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void SelectSort(int* arr, int k)
{
  //一次选择排序两个数据，分别放在最前面和最后面
  int begin = 0; int end = k-1;

  //找下标
  while (begin < end)
  {
    int min = begin; int max = begin;
    for (int i = begin + 1; i <= end; i++)
    {
      if (arr[min] > arr[i])
      {
        min = i;
      }
      if (arr[max] < arr[i])
      {
        max = i;
      }
    }

    //最后找到最大和最小的数的下标，交换

    if (max == begin)
    {
      ////判断max原来的值是否会被第一个Swap覆盖，如果==begin说明会被覆盖，
      //那么把min位置给max就可以得到交换位置后的数据
      max = min;
    }
    Swap(&arr[begin], &arr[min]);
    Swap(&arr[end], &arr[max]);

    //一次循环排完了两个数
    begin++;
    end--;
  }
}

2.2 堆排序

2.2.1 建立什么样的堆

​​要学习堆排序，先学习了解什么是堆​​ 堆排序需要了解建堆这个数据结构，了解建堆算法。如果堆学好了，才能看得懂博主写的堆排序是个什么东西。没有学好堆，不要看这里的堆排序。

先说结论：升序建大堆，降序建小堆

为什么升序建小堆不好：
排升序建小堆的话，堆顶数据为最小的数据，但因为堆的性质是，如果是小堆，只能保证孩子一定大于父亲，不能保证孩子和兄弟之间是按从小到大排列的。所以接下来我们需要不断地选出次小的数据来达到排序的目的。那么选出次小的数据的思路有两种：

  1. 把堆顶数据删除，存到一个数组里，然后再对剩下的数据进行调整。对于这种思路，我们需要明白有两个弊端：
  • 删除堆顶数据之后，我们需要对整个数组进行调整，要把整个数组的内容往前移动，这是对性能的浪费。
  • 挪动数组数据后，我们对应的逻辑关系也就乱了，如下图，如果我们选出最小数据15，然后把15删除掉，就得出右图，我们可以看到，右图中的父子关系已经混乱，不再是一个小堆。这时就需要重新建堆,浪费空间，需要重新开数组。这也意味着，每一次要选出次大的数据都要重新建堆，这又是一次性能的浪费。
  • 这个思路需要开新空间存删掉的堆顶数据。

所以这个思路并不好。

四大排序

  1. 把堆顶数据删掉，把堆底数据换到堆顶，然后向下调整，原来的堆顶数据开新空间存入数组，解决了关系会乱的问题，不需要重新建堆，但同样的，这个思路的缺点是开了新空间，空间复杂度为O(N)。
    要做，我们就要做最优的！！！

为什么排升序建大堆好：
建大堆，意味着最大的数在堆顶，此时我们把堆顶与堆底对调，然后排除堆底数据，如下第1,2张图，在选出次大的数据时，我们把堆底的65排除在外，15处才算做堆底。然后向下调整，选出次大的数据。重复以上步骤，每一次的向下调整之后我们都把次大的数交换在了当时的堆底。最后就可以实现堆顶是最小的数，整个堆都是有序的。

四大排序

四大排序

2.2.2 代码实现

//排升序
void Swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Heapsort()
{
    int arr[] = {15,18,19,37,25,28,34,65,27,49};
    int n = sizeof(arr) / sizeof(arr[0]);
    Heap php;
    //建堆O(N)
    HeapCreat(&php, arr, n);

    //O(N*log N)
    for (int end = n-1; end > 0; end--)
    {
        Swap(&php.a[0], &php.a[end]);//交换堆顶堆底数据
        AdjustDown(0, php.a, end);//调整选出次大的数
    }
}

交换排序

3.1 快速排序

快速排序这里介绍三种实现思路，分别是hoare版，挖坑法以及快慢指针法

3.1.1 hoare版

3.1.1.1 思想

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

单趟排序

如下方动图，选取最左边的数据或者最右边的数据为key，此处以最左处为key，右边先走找比key位置处的6小的值，找到了或遇到了左边的小人就停下来，然后左边再走，找比6大的值，找到了或遇到了右边的小人就停下来。当左右两个小人都找到了自己要找的数时，交换两数，再重复以上步骤，直到两小人相遇，把key位置的值与相遇位置的值相交换，至此完成单趟排序。

四大排序

最后我们可以看到，在经历上方动图所示的排序后，我们达到了两个效果:

  • 分割出了左右两个区间，6 的左边都是比它小的值，右边都是比它大的值。
  • key位置的 6 到了它该在的位置.

    这就完成了快速排序的第一趟排序。之后分别对 6 左边的数据序列和右边的数据序列重复此步骤就可以完成全部数据的排序。这就是子问题，用一样的方式不断递归知道该区间只剩一个数。

多趟

由下方的图我们可以看到，在每一个数都找到了自己的位置后，排序实际就已经完成了。

这其实就是一颗完全二叉树，我们按照完全二叉树的递归方式就可以把数据排好了

四大排序

3.1.1.2 小问题

为什么能够保证最后和key交换的的位置就是key应该在的位置

这里给出思路，既然已经看到这个地方了，如果前面的都看懂了说明是有能力独立解决这个问题的，如果没有解决，请看下方的思路，这个问题并不难，画画图就可以解决，祝好运！

四大排序

3.1.1.3 对以上思想的优化
3.1.1.3.1 三数取中

首先我们求算一下快速排序的时间复杂度

在单趟排序中，我们只需遍历完整个循环就可以排好一个数，所以单趟的排序时间复杂度是O(N)。所以接下来，时间复杂度最好与最坏就取决于我们到底要走多少次单趟循环才能把所有数排完。

  • 最好的情况：什么是最好的情况？我们前面讲思想的时候提到，通过不断的对剩下的区间进行排序达到整个数据集合排序的目的，这也就是不断缩小问题规模形成子问题的方法，也就是递归。那么，递归的深度也就很大程度上决定了我们这个程序性能的高下。在进行单趟排序中，我们是左右两边互相靠近的，都在移动。那也就是说，理想状态就是二者在中间位置相遇是最好的，逻辑图可以想象为一个满二叉树，这种情况下的每一次单趟排序具体的时间复杂度是N/2。而如果相遇位置靠右或者靠左，就意味着程序的递归深度要增加，性能自然也就不是最优。
    如下图，每一次选key，key最后的位置都在数据集合的中间，这样就把数据集合分成了一颗完全二叉树的形式进行递归。完全二叉树递归深度为logN，每一层都有接近N个值，因为每一趟排序都会减少一个数据。又因为每一层要遍历接近N次，所以最后的时间复杂度就是O(N * logN)。
    - 最坏的情况：数据集合是有序的。如下图，这就意味着每一次选key，都只能选出一个key所在的位置，无法分割区间。也就是说，我们需要进行N次单趟循环。所以最坏的时间复杂度是O(N²)

    通过上方的时间复杂度的求算我们知道，影响快速排序性能的实际问题其实是key的选取，key选的差，时间复杂度就靠近O(N²），所以我们需要使起到分割区间作用的key尽量靠近中间位置。由此，诞生出了三数取中。

三数取中的思想

从选key下手，我们选三个数，一个为最左边，一个最右边，一个数据集合的中间位置，我们从这里面选取一个中间大的数据当做key，以此来尽量避免key分割出的区间很不均衡的问题。

下面是三数取中的代码实现

int GetMidIndex(int* arr, int left, int right)
{
  int mid = left + (right - left) / 2;

  if ((arr[left]<arr[right] 
    && arr[left] > arr[mid]) 
    ||(arr[left] > arr[right] 
    && arr[left] < arr[mid]))
  {
    return left;
  }
  if ((arr[right]<arr[left] 
    && arr[right] > arr[mid]) 
    ||(arr[mid] > arr[right] 
    && arr[left] < arr[right]))
  {
    return right;
  }
  return mid;
}
3.1.1.3.2 小区间优化

通过下方这张图，结合二叉树的相关知识我们可以知道，递归往下，二叉树的最后一层就占了一半的递归调用，倒数3层差不多就占了80%多的递归。而在最后的几层递归中，我们实际待排的数据量是比较少的，这个时候用快排的优势就体现不出来了，因为每一次递归开辟栈帧销毁栈帧是会消耗性能的，同时递归层数过多可能导致栈溢出。这也就是小区间优化存在的意义。在数据量小的时候，我们采取直接插入排序的方法，减少了80%的递归，极大地优化了程序。

四大排序

代码放在下方的多趟hoare代码实现里

3.1.1.3.3 三路并排

三数取中只能帮助我们尽量选出一个好的key，但当大量数据重复时，三数取中也会无能为力。因为在数据大量重复时，分割出的区间会很不均衡，比如​​{2,2,3,2,2,3,2,2}​​​逻辑图也不会是我们上面的完全二叉树了,性能极大地下滑。为了解决这个问题，三路并排就出现了。

其主要的思路就是把与key相同的数据往中间靠，比key小的数据往左，比key大的数据往右。目的就是不让与key相同的数据再次参与排序，极大地优化了性能。

单趟三路并排：

四大排序

最后

四大排序

void QuickThreeSort(int* arr, int begin, int end)//末尾数据下标
{
  //如果右边<=左边说明只剩1个数据了
  if (begin >= end)
  {
    return;
  }

  int left = begin;
  int right = end;
  int cur = begin + 1;
  //把得到的key的位置放到最左边
  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);
  int key = arr[begin];
  int keyi = begin;

  //小区间优化
  if (end - begin > 10)
  {
    //单趟，排序主体
    while (cur <= right)
    {
      if (arr[cur] < key)
      {
        Swap(&arr[left++], &arr[cur++]);
      }
      else if (arr[cur] > key)
      {
        Swap(&arr[cur], &arr[right--]);
      }
      else
        cur++;
    }

    QuickPoint(arr, begin, left-1);
    QuickPoint(arr, right+1, end);

  }
  else//直接插入排序
  {
    InsertSort(arr + begin, end - begin + 1);
  }
}
3.1.1.4 代码实现

在看懂前面的思想后，试着自己实现一下代码再来看博主的代码有什么不一样。用这个思想
实现代码会有一些坑。写完代码去代码尾部看坑。

单趟

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void QuickSort(int *arr,int n)
{
  int left =0; int right = n-1;
  int key = left; 

  while (left < right)
  {
    //右边先走，找小
    while (left < right && arr[right] >= arr[key])
    {
      --right;
    }
    //左边后走，找大
    while (left < right && arr[left] <= arr[key])
    {
      ++left;
    }
    //交换比key位置大的和比key位置小的数
    Swap(&arr[left], &arr[right]);
  }
  //交换key位置的数和相遇位置的数，完成单趟
  Swap(&arr[left], &arr[key]);
}

坑1：如果数据集合是这样的：{3,5,7,8,4,3,10}。设左边是key，我们就需要考虑到数据集合中有数字是和key位置相同的，对于这串数据，我们要考虑到的是当某个位置的数字是和key位置相同，那么这意味着如果按照上面的思想我们右边找小，比key要大，我们就right - 1，当碰到 3 了，我们就停下来了，此时就会陷入死循环。所以我们在代码中要找小找大，就要找纯粹的大和小，与key处元素相等就跳过。
坑2：如果数据集合是这样的：{1,2,3,4,5,6,7,8}。设左边是key，右边的数全比 1 要大，因为右边先走，此时如果不限定条件让left<right,数组就会越界。

多趟

void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void QuickHoare(int* arr, int begin, int end)//end是最后一个数据的下标
{
  //如果右边<=左边说明只剩1个数据了
  if (begin >= end)
  {
    return;
  }

  int left = begin; int right = end ;
  //三数取中后把得到的key的位置放到最左边
  Swap(&arr[GetMidIndex(arr, begin, right)], &arr[begin]);
  int key = begin;

  //小区间优化
  if (end - begin > 10)
  {
    //单趟，排序主体
    while (left < right)
    {
      //右边先走，找小
      while (left < right && arr[right] >= arr[key])
      {
        --right;
      }
      //左边后走，找大
      while (left < right && arr[left] <= arr[key])
      {
        ++left;
      }
      Swap(&arr[left], &arr[right]);
    }
    Swap(&arr[left], &arr[key]);

    QuickHoare(arr, begin, left-1);
    QuickHoare(arr, left + 1, end);
  }
  else//直接插入排序
  {
    InsertSort(arr + left, end - begin +1);
  }
}

3.2.1 挖坑法

3.2.1.1 思想

挖坑法的思想其实和hoare大佬的思想很像，就是把key位置的数据保存起来，把key位置当做坑，然后key在左就右边先走，key在右就左边先走。

如下图：这里以左边为key，右边先走找小，每停一次把停住的位置的数据放到坑位上，然后另外一边再走。重复以上步骤，两者相遇的位置就是key应该在的位置。

四大排序

3.2.1.2 代码实现
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
//挖坑
void QuickHole(int* arr, int begin, int end)//end是最后一个数据的下标
{
  //如果右边<=左边说明只剩1个数据了
  if (begin >= end )
  {
    return;
  }

  int left = begin; int right = end;
  //三数取中后把得到的key的位置放到最左边
  Swap(&arr[GetMidIndex(arr, begin, right)], &arr[begin]);
  int key = arr[begin];

  //小区间优化
  if (end - begin > 10)
  {
    //单趟，排序主体
    while (left < right)
    {
      //右边先走，找小
      while (left < right && arr[right] >= key)
      {
        --right;
      }
      arr[left] = arr[right];
      //左边后走，找大
      while (left < right && arr[left] <= key)
      {
        ++left;
      }
      arr[right] = arr[left];
    }
    arr[left] = key;
    //递归小区间
    QuickHoare(arr, begin, left-1);
    QuickHoare(arr, left + 1, end);
  }
  else//直接插入排序
  {
    InsertSort(arr + left, end - begin + 1);
  }
}

3.3.1 快慢指针法

3.3.1.1 思想

同样是选key，一样的操作，实现交换的细节不一样而已。我们要做的就是用cur指针找比key小的数据，找到后停下来，然后++prev，交换prev和cur位置的值。最后cur遍历完整个数据集合时，prev所在的位置就是key应该在的位置。下面动态展示单趟排序的操作细节

开始：

四大排序

最后：

四大排序

3.3.1.2 代码实现
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
void QuickPoint(int* arr, int begin, int end)//end为末尾数据的下标
{
  //如果右边<=左边说明只剩1个数据了
  if (begin >= end)
  {
    return;
  }

  //快慢下标
  int prev = begin;
  int cur  = begin + 1;
  //三数取中后把得到的key的位置放到最左边
  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);
  int key = begin;

  //小区间优化
  if (end - begin > 10)
  {
    //单趟，排序主体
    while (cur <= end)
    {
      if (arr[cur] < arr[key] && ++prev != cur)
      {
        Swap(&arr[prev], &arr[cur]);
      }
      cur++;
    }
    Swap(&arr[prev], &arr[key]);

    //递归小区间
    QuickPoint(arr, begin, prev-1);
    QuickPoint(arr, prev + 1, end);

  }
  else//直接插入排序
  {
    InsertSort(arr + begin, end - begin + 1);
  }
}

3.4 快排的非递归实现

3.4.1 思想

我们知道，递归调用的过程是，开始调用创建一块栈空间，调用结束销毁这片栈空间。所以可以使用栈这个数据结构入栈与出栈的操作来模拟递归的调用,入栈对应着递归调用，把区间传给递归的函数，出栈对应着销毁栈帧，在出栈的时候我们拿到区间下标，对这段区间进行排序。

创建好栈后，我们把待排序的区间的下标入栈，再把区间对应的下标出栈进行排序，这就是单趟的排序。单趟排完后我们可以拿到起到分割区间作用的key位置的下标，这里称keyi，进行区间的划分：

​​​[begin,keyi-1] keyi [keyi+1,end]​​​,然后再对两区间入栈。重复以上步骤，我们就可以实现利用栈模拟递归调用。

因为博主的实现思路是先把左区间排完再拍右区间，根据栈的后入先出特点，我们先入右区间再入左区间，然后再对要排序的区间进行出栈操作。不断循环以上操作，实现快排的非递归！！！

四大排序

3.4.2 代码实现
void Swap(int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int SinglePassSort(int* arr, int begin, int end)
{
  //快慢下标
  int prev = begin;
  int cur = begin;

  //三数取中，把得到的key的位置放到最左边
  Swap(&arr[GetMidIndex(arr, begin, end)], &arr[begin]);
  int key = begin;

  while (cur <= end)
  {
    if (arr[cur] < arr[key] && ++prev != cur)
    {
      Swap(&arr[prev], &arr[cur]);
    }
    cur++;
  }
  Swap(&arr[prev], &arr[key]);
  return prev;
}
void QuickSortNonR(int* arr, int begin, int end)//end是末尾数据的下标
{
  ST* st = (ST*)malloc(sizeof(ST));
  StackInit(st);
  Stackpush(st, begin);//把最前面的数据的下标入栈
  Stackpush(st, end);//把最后一个数据的下标入栈


  while (!IsEmpty(st))//栈不为空说明排序没有完成，里面的判断是判断栈是否为空
  {
    int end = StackTop(st);  //end就是最后的数据的下标，根据入栈的顺序来
    Stackpop(st); //出栈
    int begin = StackTop(st);//begin就是头部的数据的下标
    Stackpop(st);//出栈

    //提取出之前写的单趟排序的代码进行排序
    int keyi = SinglePassSort(arr, begin, end);

    if ( keyi + 1 < end)
    {
      //入右区间
      Stackpush(st, keyi + 1);
      Stackpush(st, end);
    }
    if ( begin < keyi-1)
    {
      //入左区间
      Stackpush(st, begin);
      Stackpush(st, keyi - 1);
    }
  }

  StackDestory(st);
  free(st);
  st = NULL;
}

归并排序

4.1 递归实现

4.1.1 思想

如果两个左右两个区间有序，那么把左区间和右区间合并在一起，使其变得有序，这就是归并的意思。那么问题就在于左右区间是无序的怎么办？我们仍然采用分治的思想，将左右区间不断分割，直到只剩一个数据，一个数据我们就认为它是有序的，这就对应下图的分解。分解完成后，我们开始合并，把左右区间的数据排序合并在一起。最终完成整个数据集合的排序。

四大排序

4.1.2 实现

要注意一个点，我们不能在原数组进行排序合并，如果在原数组进行合并，合并过程会导致原数组中的数据被覆盖，创建一个数组来解决这个问题会很妙。

void _MergeSort(int* arr, int begin, int end, int* tmp)//end是最后元素的下标
{
  //递归结束条件,一个数据不再需要分解
  if (begin >= end)
  {
    return;
  }

  //分割左右区间
  int mid = begin + (end - begin) / 2;
  int begin1 = begin; int end1 = mid;
  int begin2 = mid + 1; int end2 = end;

  _MergeSort(arr, begin1, end1, tmp);
  _MergeSort(arr, begin2, end2, tmp);


  //合并区间并交换
  int i = begin;
  //两区间合并，数据先放到tmp数组中，比对完后面拷贝回原数组
  while (begin1 <= end1 && begin2 <= end2)//左右任意一个区间走完了就停下
  {
    if(arr[begin1] < arr[begin2])
    {
      tmp[i++] = arr[begin1++];
    }
    else
    {
      tmp[i++] = arr[begin2++];
    }
  }
  //把剩下没有拷贝的数据拷贝进tmp
  while (begin1 <= end1)
  {
    tmp[i++] = arr[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = arr[begin2++];
  }

  //拷贝到原数组中
  memcpy(arr+begin, tmp+begin, sizeof(int)*(end-begin+1));
}
void MergeSort(int* arr, int n)//n是数组元素个数
{
  int* tmp = (int*)malloc(sizeof(int) * n);//创建用来交换的数组
  if (tmp == NULL)
  {
    perror("MergeSort malloc");
    exit(-1);
  }

  //创建一个子函数，避免在这里面递归每次都要动态开辟一个tmp数组
  _MergeSort(arr, 0, n-1, tmp);

  free(tmp);
  tmp = NULL;
}

4.2 非递归实现

4.2.1 思路

我们知道，归并的思路就是把左右区间各取一半，两区间如果有序就把两区间合并使其有序。那么我们的非递归就是从最小的问题出发，先一个一个数进行归并，再两个两个数归并，依次增大归并的数据量，直到把最后的最大的两个区间归并完，数据就变得整体有序了。这和递归是相反的思路，递归是一步一步缩小区间，非递归是一步一步扩大区间。

如下图：

四大排序

4.2.2 代码实现

需要注意几个点

  • 每一个rangeN间距下，循环遍历数组 i 的取值以及范围
  • 每一个rangeN间距下，待归并的左右区间是否存在
    如：
void MergeSortNonR(int* arr, int begin, int end)//end是元素个数
{
  int* tmp = (int*)malloc(sizeof(int)* (end+1));//创建用来交换的数组
  if (tmp == NULL)
  {
    perror("MergeSort malloc");
    exit(-1);
  }

  int rangeN = 1;

  //rangeN 为元素个数一半之前都进行归并,
  while (rangeN<end)
  {
    for (int i = 0; i < end; i += rangeN * 2)
    {
      int begin1 = i; int end1 = i + rangeN - 1;
      int begin2 = i + rangeN; int end2 = begin2 + rangeN - 1;

      //确认哪段区间越界，如果是左区间则不参与归并，右区间还要分情况
      if (end1>=end)
      {
        break;//无论是end1还是begin2越界，我们都无法进行归并，直接退出
      }
      if (begin2 >= end)
      {
        break;
      }
      if (end2 >= end)
      {
        end2 = end - 1; //如果是end2越界，我们把end2改成end-1就行，
                  //把剩下的数据归并排序
      }

      int j = i;
      //两区间合并，数据先放到tmp数组中，比对完后面拷贝回原数组
      while (begin1 <= end1 && begin2 <= end2)//左右任意一个区间走完就停下
      {
        if (arr[begin1] < arr[begin2])
        {
          tmp[j++] = arr[begin1++];
        }
        else
        {
          tmp[j++] = arr[begin2++];
        }
      }
      //把剩下没有拷贝的数据拷贝进tmp
      while (begin1 <= end1)
      {
        tmp[j++] = arr[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = arr[begin2++];
      }

      //拷贝到原数组中
      memcpy(arr + i, tmp + i, sizeof(int)*(end2-i+1));
    }
    rangeN *= 2;
  }
}

总结

四大排序

5.1 时间复杂度

直接插入排序

最坏的情况下：逆序的情况就是最坏的情况，这意味着每一次进行单趟排序，tmp都要循环至最前面进行交换，时间复杂度时O(N²)。
最好的情况：有序或者接近有序。这意味着单趟排序时每一个tmp代表的值要进行的循环只有1次或者接近1次，时间复杂度为O(N)。
我们一般默认最坏的情况是时间复杂度，所以是O（N²）。

希尔排序

希尔排序的时间复杂度以我的能力实在没法儿求，需要高深的数学知识很强的数理能力。

因为gap的取值有很多种方法，也没有一个公认的时间复杂度。

四大排序

直接选择排序

典型的O（N²），每次排序要遍历一遍数组选出数据，要遍历N次。

堆排序

堆排序的时间复杂度需要了解建堆的过程，了解建堆算法。如果堆这个数据结构学好了，才能看得懂博主写的是什么。没有学好堆，不要看这里的堆排序。
O(N* logN)，向下调整是O（logN），要调整N次，所以是O(N* logN)。

快速排序

O(N* logn)，在3.1.1.3.1中我求算了快排在没有优化前的时间复杂度，而在三数取中优化后，我们快排最后取出的数会是一个比较均衡的数，也就是说，可以默认快排的时间复杂度接近最好的情况。

归并排序

归并排序实际上就是快速排序的最优情况，每一次都二等分数据集合，想象逻辑图是一颗完全二叉树，我们可以得出深度是logN，每层遍历N次，所以时间复杂度是O(N* logN)

5.2 空间复杂度

不重要，不解释，也不难。递归就算递归的深度，深度就是空间复杂度。求时间和空间这个在博主的​​时间复杂度空间复杂度求算博客​​中讲的很清楚。

5.3 稳定性

5.3.1 什么是稳定性

假设一场考试中有三人先后交卷，第一个交卷的为92分，第二个交卷的91分，第三个交卷的也是91分，这时我们要对他们进行的成绩排先后顺序，把92排在最前，这没问题。第二个和第三个同分，但第二个比第三个先交卷，如果我们把第三个交卷的人排在第二就不合理了，这时我们把可以保证相同数据的相对顺序的排序称稳定性好。
比如​​​ 1 5 4 7 4 9​​，排升序，可以让第1个 4 排在第 2 个4前面的排序就是稳定性好。如果后面那个4排到前面去了说明稳定性不好。

5.3.2 各排序的稳定性分析

这里只分析选择排序，因为一些书和资料对它的稳定性分析有争议

选择排序稳定性分析

这里采用一次找一个数的排序来分析稳定性，一次找一个数都保证不了，一次找两个数就更不能保证稳定性了。如图：

四大排序

标签：

相关文章