前言

此篇的文章主要是博主为了方便自己复习所以字数很多.大家想看那个看看就好,哪里不会可以私信博主.

总体表格

912. 排序数组 - 力扣—可以用这个来测试自己的排序函数是否正确,虽然大部分会超时🤪.

排序定义

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序时使用的Swap函数如下:

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

冒泡排序

冒泡排序是一种非常容易理解的排序

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

空间复杂度：O(1)

稳定性：稳定

最早学会的排序,以易懂和稳定著称.

冒泡排序的思想如下:

通过将最大的数值向后移动到排序区间的最后来进行排序.

代码如下:

void BubbleSort(int* a, int n)//a是要排序的数组,n是a数组的大小
{
  for (int i = n; i >= 0; i--)
  {
  for (int j = 1; j < i; j++)
  {
    if (a[j - 1] > a[j])
    {
    Swap(&a[j - 1], &a[j]);
    }
  }
  }
}

第一个for循环用来控制我们要排序的空间(及i的数值),如刚开始时我们要排序的空间是整个n空间

然后经过第二个for循环后我们将最大的数值一直向后排,排到要排序空间的最后方

然后通过缩减要排序空间知道排序空间为0即排序完毕.

插入排序

元素集合越接近有序，直接插入排序算法的时间效率越高

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

空间复杂度：O(1)，它是一种稳定的排序算法

稳定性：稳定

//直接插入排序
void InsertSort(int* a, int n)
{
  //直接插入排序:通过将一个数组分成有序和无序两种状态,然后通过将无序部分一个个的进入
  //有序的部分并且让进入的那个元素融入到有序的中即一个个的进行比较然后放到相应的位置
  //即可
  for (int i = 0; i < n - 1; i++)//因为i是赋值给end的所以只需到n-2即可
  {
    int end = i;//有序区间的结束位置
    int tmp = a[end + 1];//tmp为要插入的无序区间部分
    while (end >= 0)
    {
      if (a[end] >= tmp)
      {
        a[end + 1] = a[end];
        end--;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;//end+1的原因是我们上面的end--使我们应该插入tmp的位置后移了一个单位
  }
}

上述代码的注释基本讲解完毕.

直接插入的排序思想如下:

我们将一个数组分为有序部分和无序部分两种状况.

刚开始时有序部分内容仅有下标为0的数组值(及0<=有序区间<=end—end为有序区间结束位置)

然后我们将end+1的位置插入到我们的有序空间内.

插入过程为下面的while区间所示通过将有序空间内的元素与tmp的值进行比较然后不断移动给我们的tmp部分留下位置最后在循环结束时将tmp插入的正确的位置即可.

然后有序空间就增加了1无序空间就减小了一个单位.

一直到end位置为n-2及将n-1下标位置插入到有序空间就结束循环.

我们走一遍我们的程序

开始时我们的i=0;此时end=0;(及我们的有序区间是0~0及下标为0的元素就是我们的有序区间—只有一个元素的时候我们就不用追究他的有序还是无序了.)然后我们把tmp插入到我们的有序区间内及(将end+1位置的元素插入到我们的有序区间内).然后我们进入我们的while循环内.每当我们发现a[end]>tmp的时候我们就将这个end向后移动直到我们找到a[end]<tmp就跳出循环将tmp插入到哪里即可.

比如我们要将已经排序部分的有序空间1 3 5 插入2. 然后进入while循环

一次循环时end指向5进行if判断后有序空间变成了 1 3 5 5;

然后end--让end 指向3再进行if判断有序空间就变成1 3 3 5;

然后end--让end指向1时进行if判断后发现a[end]<tmp;进入else分支.

break跳出while后end还是指向1我们要插入tmp的位置应该是无意义的及end+1的位置.

希尔排序

时间复杂度: O(n1.25)~O(1.6*n1.25)—这个复杂度是大佬们求出的,会在希尔排序的末端把大佬们的原话复制出来🤓.

空间复杂度:O(1);

稳定性: 不稳定

希尔排序是用插入的思想但是先将数组分为有间隔的不同的小数组,先对这些有间隔的小数组进行排序(及预排序)然后再对整个数组进行间隔为1(及正常插入排序)的排序.

这样使用的原因是因为我们的插入排序可以在数组为有序的时候极快的排序.所以希尔排序其实就是多了预排序的插入排序

void ShellSort(int* a, int n)
{
  int gap = n;//gap为排序的间隔,初始化为n是为了下面/3后保证gap既不大于n又足够大.(也可能跟效率有关)
  while (gap > 1)//当gap为1的时候走完下面的操作后才跳出循环
  {
  gap = gap / 3 + 1;// 这个/3也可以除其他的而且会影响效率但是还没有最好的固定值出现,+1是为了防止gap为0我们需要保证gap最小为1
  for (int i = 0; i < n - gap; i++)//因为i是赋值给end的所以只需到n-gap-1即可,不然就越界了.
  {
    int end = i;
    int tmp = a[end + gap];
    while (end >= 0)
    {
    if (a[end] >= tmp)
    {
      a[end + gap] = a[end];//以gap为间隔分成组来进行的所以+gap
      end -= gap;//在gap不为1的时候是预排序,相当于间隔为gap的插入排序
    }
    else
    {
      break;
    }
    }
    a[end + gap] = tmp;
  }
  }
}

如果可以直接看代码+注释解决就不用看下面的解释了.

我们用gap作为间隔.第一次进入while循环时gap=gap/3+1了这个+1是为了保证我们的gap最小为1,因为我们需要在gap为1的时候进行一次排序(及插入排序)

还是搞个例子听听吧:

如:1,4,5,2,3,7,6,9,8

n=9;

进入程序:

gap = 9;

进入while

gap=9/3+1=3+1=4;

我们就以4为间隔进行以预排序

以4为间隔我们可以将数组分为1,3,8;4,7;5,6;2,9;3,8;这几组我们对每一组都进行一次插入排序

如对第一组就可以理解为将3插入1这个有序部分然后将8插入到1,3这个有序部分内.(例子不太好,预排没展现出来=-=).

然后再次调整gap;

这次有gap = 4/3+1 =2;再以2为一组分几组.进行预排

排完后再次调整gap = 2/3+1 = 1;

当gap为1的时候就和普通插入排序相同了,但是经历了预排的数组更加接近有序时间复杂度也就会更低.

选择排序

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

空间复杂度：O(1)

稳定性：不稳定

其实这玩意没啥好讲的,就从数组中选出最大和最小的数然后分别放在数组的最后和最先方,或者只选出一个最大或最小的放在最前或最后.

很好理解没啥可讲的就直接上代码了.

//每次只弄一个最大的放在数组最后
void SelectSort1(int* a, int n)
{
  for (int i = n - 1; i >= 0; --i)
  {
  int big = 0;
  int j = 0;
  while (j <= i)
  {
    if (a[j] > a[big])
    {
    big = j;
    }
    j++;
  }
  Swap(&a[big], &a[i]);
  }
}
void SelectSort2(int* a, int n)
{
  int left = 0;
  int right = n - 1;
  while (left < right)
  {
  int min = left;
  int big = left;
  for (int i = left + 1; i <= right; i++)
  {
    if (a[i] > a[big])
    big = i;
    if (a[i] < a[min])
    min = i;
  }
  Swap(&a[left], &a[min]);
  if (big == left)//当big与left相同时因为前面已经将left的值交换走所以我们真正想得到的值其实在min的位置
    big = min;
  Swap(&a[big], &a[right]);
  right--;
  left++;
  }
}